はじめに
AtCoder Beginner Contest 346の復習記事です。
記事における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/abc346
問題A
問題文通り、B[i]=A[i]*A[i+1]となるBを求め、それを出力します。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var B = new long[N - 1];
for (var i = 0; i + 1 < N; i++)
{
B[i] = A[i] * A[i + 1];
}
Console.WriteLine(string.Join(" ", B));
}
問題B
文字列wbwbwwbwbwbwを十分な長さ連結した文字列をSとします。
Sのwとbについての累積和をそれぞれ計算しておき、長さw+bの区間のwの個数とbの個数が、それぞれwとbであるかを判定することで答えを求めることができます。
例
public static void Solve()
{
var (W, B) = Scanner.Scan<int, int>();
var S = "wbwbwwbwbwbw";
while (S.Length < 300)
{
S += S;
}
var cumW = new int[S.Length + 1];
var cumB = new int[S.Length + 1];
for (var i = 0; i < S.Length; i++)
{
cumW[i + 1] += cumW[i];
cumB[i + 1] += cumB[i];
if (S[i] == 'w') cumW[i + 1]++;
else cumB[i + 1]++;
}
var L = W + B;
for (var i = 0; i + L <= S.Length; i++)
{
if (cumW[i + L] - cumW[i] == W && cumB[i + L] - cumB[i] == B)
{
Console.WriteLine("Yes");
return;
}
}
Console.WriteLine("No");
}
問題C
1からKまでの総和SはK*(K+1)/2で求めることができ、K以下の重複を除いたAの値をSから引いたものが答えとなります。
例
public static void Solve()
{
var (N, K) = Scanner.Scan<int, long>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var S = K * (K + 1) / 2;
foreach (var a in A.Distinct().Where(x => x <= K))
{
S -= a;
}
Console.WriteLine(S);
}
問題D
次のような動的計画法を解きます。
dp[i,j,k] := i番目の文字がj(0|1)であるかつ、良い文字列であるk(0|1)ときのコストの最小値
遷移は次のようになります。
a = S[i], b = S[i]^1 とする。
i番目で良い文字列になるパターン
dp[i+1,a,1] = Min(dp[i+1,a,1], dp[i,a,0]);
dp[i+1,b,1] = Min(dp[i+1,b,1], dp[i,b,0] + C[i]);
i番目では良い文字列ではないパターン
dp[i+1,a,0] = Min(dp[i+1,a,0], dp[i,b,0]);
dp[i+1,b,0] = Min(dp[i+1,b,0], dp[i,a,0] + C[i]);
i番目までに既に良い文字列であるパターン
dp[i+1,a,1] = Min(dp[i+1,a,1], dp[i,b,1]);
dp[i+1,b,1] = Min(dp[i+1,b,1], dp[i,a,1] + C[i]);
Min(dp[N,0,1], dp[N,1,1])が答えになります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>().Select(x => x - '0').ToArray();
var C = Scanner.ScanEnumerable<long>().ToArray();
const long Inf = 1L << 60;
var dp = new long[N + 1, 2, 2];
for (var i = 0; i <= N; i++)
{
for (var j = 0; j < 2; j++)
{
for (var k = 0; k < 2; k++)
{
dp[i, j, k] = Inf;
}
}
}
dp[1, S[0], 0] = 0;
dp[1, S[0] ^ 1, 0] = C[0];
for (var i = 1; i < N; i++)
{
var a = S[i];
var b = S[i] ^ 1;
dp[i + 1, a, 1] = Math.Min(dp[i + 1, a, 1], dp[i, a, 0]);
dp[i + 1, b, 1] = Math.Min(dp[i + 1, b, 1], dp[i, b, 0] + C[i]);
dp[i + 1, a, 0] = Math.Min(dp[i + 1, a, 0], dp[i, b, 0]);
dp[i + 1, b, 0] = Math.Min(dp[i + 1, b, 0], dp[i, a, 0] + C[i]);
dp[i + 1, a, 1] = Math.Min(dp[i + 1, a, 1], dp[i, b, 1]);
dp[i + 1, b, 1] = Math.Min(dp[i + 1, b, 1], dp[i, a, 1] + C[i]);
}
var answer = Math.Min(dp[N, 0, 1], dp[N, 1, 1]);
Console.WriteLine(answer);
}
問題E
最終的なマスの色は、マスに対する最後のクエリの操作によって上書きされるので、クエリを逆順で処理することを考えます。
1番目のクエリでは、A行目に対してまだ操作が行われていないとき、A行目のうちそれまでに塗りつぶした列以外のマスを塗りつぶすという操作になります。
同様に、2番目のクエリでは、A列目に対してまだ操作が行われていないとき、A列目のうちそれまでに塗りつぶした行以外のマスを塗りつぶすという操作になります。
このことから、塗りつぶしていない行とその数、塗りつぶしていない列とその数を管理しながらクエリを適用していくことで、すべてのクエリを適用した状態の色の数を数え上げることができます。
また、操作が行われなかったマスの数はH*W-操作が行われたマスの数で求めることができ、この値を初期状態の色0の個数に加える必要があります。
例
public static void Solve()
{
var (H, W, M) = Scanner.Scan<int, int, int>();
var dict = new Dictionary<int, long>();
var query = new (int T, int A, int X)[M];
for (var i = 0; i < M; i++)
{
query[i] = Scanner.Scan<int, int, int>();
}
Array.Reverse(query);
var row = new int[H];
var col = new int[W];
Array.Fill(row, -1);
Array.Fill(col, -1);
var remH = H;
var remW = W;
for (var i = 0; i < M; i++)
{
var (t, a, x) = query[i];
a--;
if (t == 1)
{
if (row[a] != -1) continue;
row[a] = x;
if (!dict.ContainsKey(x)) dict[x] = 0;
dict[x] += remW;
remH--;
}
else
{
if (col[a] != -1) continue;
col[a] = x;
if (!dict.ContainsKey(x)) dict[x] = 0;
dict[x] += remH;
remW--;
}
}
var sum = dict.Values.Sum();
var zero = (long)H * W - sum;
if (!dict.ContainsKey(0)) dict[0] = 0;
dict[0] += zero;
Console.WriteLine(dict.Where(x => x.Value > 0).Count());
foreach (var (k, v) in dict.Where(x => x.Value > 0).OrderBy(x => x.Key))
{
Console.WriteLine($"{k} {v}");
}
}