はじめに
AtCoder Beginner Contest 277の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc277
問題A
A[i]を順にみていき、A[i]==Xとなる位置が答えとなります。
public static void Solve()
{
var (N, X) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var answer = 0;
for (var i = 0; i < N; i++)
{
if (A[i] == X) answer = i + 1;
}
Console.WriteLine(answer);
}
問題B
一つ一つの文字を条件式として判別しても答えを求めることが可能ですが、2文字目の判定の対象が多いので、配列やHashSet等のデータ構造に集合として値を用意し、その集合に含まれているかどうかを判定することで、簡単に記述することができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var answer = true;
var F = new HashSet<char> { 'H', 'D', 'C', 'S' };
var G = new HashSet<char> { 'A', '2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K' };
var memo = new HashSet<string>();
for (var i = 0; i < N; i++)
{
var s = Scanner.Scan<string>();
answer &= F.Contains(s[0]);
answer &= G.Contains(s[1]);
answer &= !memo.Contains(s);
memo.Add(s);
}
Console.WriteLine(answer ? "Yes" : "No");
}
問題C
階層を頂点としたグラフを構築し、深さ優先探索や幅優先探索を行うことで、行くことができる階層を探索して最高の階層を求めます。
階層をそのまま頂点としたグラフを配列で構築してしまうと、はしごがつながっていない階層含めて1e9もの空間計算量が必要になってしまい、実行時間制限に間に合わなくなってしまいます。
そこで、頂点を圧縮したり、辞書などのデータ構造を用いることで、はしごがつながっていない階層を無視することができ、最大でも4e5程度の空間計算量で収まり、実行時間制限内に処理することができるようになります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var G = new Dictionary<int, List<int>>();
for (var i = 0; i < N; i++)
{
var (a, b) = Scanner.Scan<int, int>();
if (!G.ContainsKey(a)) G[a] = new List<int>();
if (!G.ContainsKey(b)) G[b] = new List<int>();
G[a].Add(b);
G[b].Add(a);
}
var used = new HashSet<int> { 1 };
var queue = new Queue<int>();
queue.Enqueue(1);
while (queue.Count > 0)
{
var u = queue.Dequeue();
if (!G.ContainsKey(u)) continue;
foreach (var v in G[u])
{
if (used.Contains(v)) continue;
used.Add(v);
queue.Enqueue(v);
}
}
var answer = used.Max();
Console.WriteLine(answer);
}
問題D
操作について、あるカードの整数vをテーブルに置いたとき、次に出すことができるカードはvまたは(v+1)%Mであることから、整数vのカードを出した時は、整数vのカードを全て出すことができます。
そのため、カードの整数ごとに出すことのできる枚数や総和を辞書などでまとめあげることができます。
整数vとvを出した時の総和sのペアをPとし、Pをvでソートすると、P[i+1].v%M==(P[i].v+1)%Mとなる区間の総和が出すことができるカードの総和となります。
この区間の総和は尺取り法で求めることができ、その最大値をAの総和から引いたものが答えとなります。
また、v==M-1のとき(v+1)%Mは0になり、円環になることがあるので注意が必要です。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
long sum = 0;
var dict = new Dictionary<int, long>();
foreach (var a in A)
{
if (!dict.ContainsKey(a)) dict[a] = 0;
dict[a] += a;
sum += a;
}
var K = dict.Count;
var B = new List<(int V, long S)>(dict.Select(kv => (kv.Key, kv.Value)));
B.Sort();
var l = 0;
var r = 0;
const long inf = (long)1e18;
var answer = inf;
while (l < K)
{
r = l;
var s = B[r].S;
while (r + 1 < l + K && (B[(r + 1) % K].V % M) == (B[r % K].V + 1) % M)
{
s += B[(r + 1) % K].S;
r++;
}
answer = Math.Min(answer, sum - s);
l = r + 1;
}
Console.WriteLine(answer);
}
問題E
スイッチは2回押すと元の状態に戻るので、スイッチの状態2通りについての各頂点のコストを管理し、現在のスイッチの状態を持ちながら幅優先探索を行うことで、答えを求めることができます。
public static void Solve()
{
var (N, M, K) = Scanner.Scan<int, int, int>();
var G = new List<(int U, int A)>[N];
G = new List<(int U, int A)>[N].Select(x => new List<(int U, int A)>()).ToArray();
for (var i = 0; i < M; i++)
{
var (u, v, a) = Scanner.Scan<int, int, int>();
u--;
v--;
G[u].Add((v, a));
G[v].Add((u, a));
}
var T = new HashSet<int>();
if (K > 0)
{
var S = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
T = new HashSet<int>(S);
}
const int inf = (int)1e9;
var costs = new int[2][].Select(_ => new int[N]).ToArray();
Array.Fill(costs[0], inf);
Array.Fill(costs[1], inf);
costs[0][0] = 0;
var queue = new Queue<(int T, int U, long Cost)>();
queue.Enqueue((0, 0, 0));
while (queue.Count > 0)
{
var (ut, u, uc) = queue.Dequeue();
var vt = ut;
for (var i = 0; i < 2; i++)
{
foreach (var (v, a) in G[u])
{
if (a == vt) continue;
var c = costs[ut][u] + 1;
if (costs[vt][v] <= c) continue;
costs[vt][v] = c;
queue.Enqueue((vt, v, c));
}
if (T.Contains(u)) vt = ut ^ 1;
else break;
}
}
var answer = Math.Min(costs[0][N - 1], costs[1][N - 1]);
if (answer == inf) answer = -1;
Console.WriteLine(answer);
}