はじめに
AtCoder Beginner Contest 344の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
Scannerクラス
public static class Scanner
{
public static T Scan<T>() where T : IConvertible => Convert<T>(ScanStringArray()[0]);
public static (T1, T2) Scan<T1, T2>() where T1 : IConvertible where T2 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]));
}
public static (T1, T2, T3) Scan<T1, T2, T3>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]));
}
public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]));
}
public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]));
}
public static (T1, T2, T3, T4, T5, T6) Scan<T1, T2, T3, T4, T5, T6>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible where T6 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]), Convert<T6>(input[5]));
}
public static IEnumerable<T> ScanEnumerable<T>() where T : IConvertible => ScanStringArray().Select(Convert<T>);
private static string[] ScanStringArray()
{
var line = Console.ReadLine()?.Trim() ?? string.Empty;
return string.IsNullOrEmpty(line) ? Array.Empty<string>() : line.Split(' ');
}
private static T Convert<T>(string value) where T : IConvertible => (T)System.Convert.ChangeType(value, typeof(T));
}
コンテスト
https://atcoder.jp/contests/abc344
問題A
Sを|で分けたものの、1番目と3番目の文字列を結合したものが答えとなります。
例
public static void Solve()
{
var S = Scanner.Scan<string>().Split('|');
var answer = S[0] + S[2];
Console.WriteLine(answer);
}
問題B
0が入力されるまで入力された値をリストに保持するを繰り返し、リストを反転させたものを出力します。
例
public static void Solve()
{
var list = new List<int>();
while (true)
{
var v = Scanner.Scan<int>();
list.Add(v);
if (v == 0) break;
}
list.Reverse();
Console.WriteLine(string.Join(Environment.NewLine, list));
}
問題C
初期状態を0のみの集合として、前回の集合の要素と今回の集合の要素の組み合わせの合計値の集合を次の集合にするという操作を3回行います。
3回操作を行った集合にXの各要素が含まれているかを判定します。
全体の時間計算量はO(N*M*L)になります。
例
public static void Solve()
{
var dp = new HashSet<long>();
dp.Add(0);
for (var i = 0; i < 3; i++)
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<long>().Distinct().ToArray();
var ndp = new HashSet<long>();
foreach (var v in dp)
{
foreach (var a in A)
{
ndp.Add(v + a);
}
}
dp = ndp;
}
var Q = Scanner.Scan<int>();
var X = Scanner.ScanEnumerable<long>().ToArray();
foreach (var x in X)
{
var answer = dp.Contains(x);
Console.WriteLine(answer ? "Yes" : "No");
}
}
問題D
次のような動的計画法を解きます。
dp[s] := 文字がsとなるときの操作回数の最小値
初期状態dp[""]=0として、それまでの文字列P[k]にS[j]を末尾に加えた文字列XがTに前方一致する場合、dp[X]=Min(dp[X],dp[P[k]]+1)で更新していき、最終的なdp[T]の値が答えとなります。
例
public static void Solve()
{
var T = Scanner.Scan<string>();
var N = Scanner.Scan<int>();
var dp = new Dictionary<string, int>();
const int Inf = 1 << 30;
dp[""] = 0;
for (var i = 0; i < N; i++)
{
var line = Scanner.ScanEnumerable<string>().ToArray();
var a = int.Parse(line[0]);
var ndp = new Dictionary<string, int>(dp);
foreach (var (s, c) in dp)
{
foreach (var t in line[1..])
{
if (s.Length + t.Length > T.Length) continue;
var ok = true;
for (var j = 0; j < t.Length && ok; j++)
{
ok &= t[j] == T[s.Length + j];
}
if (ok)
{
var x = s + t;
if (!ndp.ContainsKey(x)) ndp[x] = Inf;
ndp[x] = Math.Min(ndp[x], c + 1);
}
}
}
dp = ndp;
}
var answer = dp.ContainsKey(T) ? dp[T] : -1;
Console.WriteLine(answer);
}
問題E
値xに対して直前の値prev[x]と直後の値prev[x]を管理します。
1番目のクエリでは、a=x, b=y, c=next[x]としたとき、next[a]=b, next[b]=c, prev[b]=a, prev[c]=bとして更新します。
2番目のクエリでは、a=prev[x], c=next[x]としたとき、next[a]=c, prev[c]=aとして更新します。
全てのクエリを処理した後、先頭から順に値を列挙したものが答えとなります。
あらかじめ、最初の値の直前の値と、最後の値の直後の値に番兵を設定することで、最初と最後を意識することなく処理することができるようになります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var prev = new Dictionary<int, int>();
var next = new Dictionary<int, int>();
next[A[^1]] = -1;
prev[-1] = A[^1];
prev[A[0]] = -2;
next[-2] = A[0];
for (var i = 0; i + 1 < N; i++)
{
var u = A[i];
var v = A[i + 1];
next[u] = v;
prev[v] = u;
}
var Q = Scanner.Scan<int>();
for (var q = 1; q <= Q; q++)
{
var query = Scanner.ScanEnumerable<int>().ToArray();
if (query[0] == 1)
{
var (x, y) = (query[1], query[2]);
var a = x;
var b = y;
var c = next[x];
next[a] = b;
next[b] = c;
prev[b] = a;
prev[c] = b;
}
else
{
var x = query[1];
var a = prev[x];
var b = x;
var c = next[x];
next[a] = c;
prev[c] = a;
}
}
var curr = next[-2];
var answer = new List<int>();
while (curr >= 0)
{
answer.Add(curr);
curr = next[curr];
}
Console.WriteLine(string.Join(" ", answer));
}