はじめに
AtCoder Beginner Contest 303の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc303
問題A
両方の文字列の1をlに、0をoに変換した文字列が一致する場合、似た文字列となります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
var T = Scanner.Scan<string>();
string F(string str) => str.Replace('1', 'l').Replace('0', 'o');
var answer = F(S) == F(T);
Console.WriteLine(answer ? "Yes" : "No");
}
問題B
G[x][y]を番号xと番号yの人が隣り合ったことがあるかを判定するbool行列、A[i][j]をu、A[i][j+1]をvすると、G[u][v]とG[v][u]をtrueにすることができます。
そして、u<vとなる組み合わせのうちG[u][v]がfalseである組み合わせの数が答えとなります。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var A = new int[M][].Select(_ => Scanner.ScanEnumerable<int>().ToArray()).ToArray();
var G = new bool[N, N];
for (var i = 0; i < M; i++)
{
for (var j = 0; j + 1 < N; j++)
{
var u = A[i][j] - 1;
var v = A[i][j + 1] - 1;
G[u, v] = true;
G[v, u] = true;
}
}
var answer = 0;
for (var i = 0; i < N; i++)
{
for (var j = i + 1; j < N; j++)
{
if (!G[i, j]) answer++;
}
}
Console.WriteLine(answer);
}
問題C
問題文の通りにシミュレーションを行います。
ただし、|x|,|y|<=2e5であるため、アイテムの位置を二次元座標を配列として管理してしまうと、計算量がO(Max(|x|,|y|)^2)となり実行時間制限に間に合いません。
そのため、アイテムの位置をSetやHashSetなどで管理することで、時間計算量O(Nlog(M))やO(N)で解くことができます。
public static void Solve()
{
var (N, M, H, K) = Scanner.Scan<int, int, int, int>();
var S = Scanner.Scan<string>();
var items = new HashSet<(int X, int Y)>();
for (var i = 0; i < M; i++)
{
var (x, y) = Scanner.Scan<int, int>();
items.Add((x, y));
}
(int Nx, int Ny) F(int x, int y, char c)
{
return c switch
{
'R' => (x + 1, y),
'L' => (x - 1, y),
'U' => (x, y + 1),
'D' => (x, y - 1),
_ => (x, y),
};
}
var (cx, cy) = (0, 0);
foreach (var c in S)
{
(cx, cy) = F(cx, cy, c);
H--;
if (H < 0)
{
Console.WriteLine("No");
return;
}
if (items.Contains((cx, cy)) && H < K)
{
items.Remove((cx, cy));
H = K;
}
}
Console.WriteLine("Yes");
}
問題D
次のような動的計画法を解きます。
dp[i,f] := i番目の文字を入力するときにCapsLockキーのランプがf(OFF|ON)のときの最短の時間
4種類の操作があり得ます。
- Xミリ秒でaキーを押す
- Yミリ秒でShiftキーとaキーを押す
- Zミリ秒でCapsLockキーを押した後にaキーを押す
- Zミリ秒でCapsLockキーを押した後にShiftキーとaキーを押す
遷移としては次のようになります。
初期値
dp[0,OFF] = 0
dp[1,ON] = INF
S[i]がaのとき
dp[i+1,OFF] = Min(dp[i+1,OFF], dp[i,OFF]+X)
dp[i+1,ON] = Min(dp[i+1,ON], dp[i,ON] +Y)
dp[i+1,ON] = Min(dp[i+1,ON], dp[i,OFF]+Z+Y)
dp[i+1,OFF] = Min(dp[i+1,OFF], dp[i,ON] +Z+X)
S[i]がAのとき
dp[i+1,OFF] = Min(dp[i+1,OFF], dp[i,OFF]+Y)
dp[i+1,ON] = Min(dp[i+1,ON], dp[i,ON] +Y)
dp[i+1,ON] = Min(dp[i+1,ON], dp[i,OFF]+Z+X)
dp[i+1,OFF] = Min(dp[i+1,OFF], dp[i,ON] +Z+Y)
まとめると次のようになります。
S[i]がaのときf=0,Aのときf=1とする
dp[i+1,f] = Min(dp[i+1,f], dp[i,f] +X)
dp[i+1,f^1] = Min(dp[i+1,f^1], dp[i,f^1]+Y)
dp[i+1,f] = Min(dp[i+1,f], dp[i,f^1]+Z+X)
dp[i+1,f^1] = Min(dp[i+1,f^1], dp[i,f] +Z+Y)
N文字目まで入力後のMin(dp[N,OFF],dp[N,ON])が答えとなります。
public static void Solve()
{
var (X, Y, Z) = Scanner.Scan<long, long, long>();
var S = Scanner.Scan<string>();
var N = S.Length;
var dp = new long[N + 1, 2];
const long Inf = (long)1e18;
for (var i = 0; i <= N; i++)
{
dp[i, 0] = dp[i, 1] = Inf;
}
dp[0, 0] = 0;
for (var i = 0; i < N; i++)
{
var f = S[i] == 'a' ? 0 : 1;
var g = f ^ 1;
dp[i + 1, f] = Math.Min(dp[i + 1, f], dp[i, f] + X);
dp[i + 1, g] = Math.Min(dp[i + 1, g], dp[i, g] + Y);
dp[i + 1, f] = Math.Min(dp[i + 1, f], dp[i, g] + Z + X);
dp[i + 1, g] = Math.Min(dp[i + 1, g], dp[i, f] + Z + Y);
}
var answer = Math.Min(dp[N, 0], dp[N, 1]);
Console.WriteLine(answer);
}
問題E
星の中心となる頂点は、葉となる頂点と辺で結ばれている頂点になります。
また、星の中心となる頂点と辺で結ばれている頂点はすべて葉である必要があります。
そのため、葉となる頂点uを順番に見ていき、その葉を含む星の中心となる頂点vと辺で結ばれている頂点wに結ばれている辺のうち、v以外の辺を全て取り除くことで、vの辺の数がレベルとなる星にすることができます。
また、グラフは木であるため、wと結ばれている辺を削除した頂点xは新しく葉となります。
u -- v -- w
|
z -- y -- x
public static void Solve()
{
var N = Scanner.Scan<int>();
var deg = new int[N];
var G = new HashSet<int>[N].Select(x => new HashSet<int>()).ToArray();
for (var i = 0; i < N - 1; i++)
{
var (u, v) = Scanner.Scan<int, int>();
u--;
v--;
G[u].Add(v);
G[v].Add(u);
deg[u]++;
deg[v]++;
}
var queue = new Queue<int>();
for (var i = 0; i < N; i++)
{
if (deg[i] == 1) queue.Enqueue(i);
}
var answer = new List<int>();
while (queue.Count > 0)
{
var u = queue.Dequeue();
if (G[u].Count < 1) continue;
var v = G[u].First();
var vd = G[v].Count;
answer.Add(vd);
var removed = new List<(int, int)>();
foreach (var w in G[v])
{
foreach (var x in G[w])
{
removed.Add((w, x));
deg[w]--;
deg[x]--;
queue.Enqueue(x);
}
}
foreach (var (x, y) in removed)
{
G[x].Remove(y);
G[y].Remove(x);
}
}
answer.Sort();
Console.WriteLine(string.Join(" ", answer));
}