はじめに
AtCoder Beginner Contest 347の復習記事です。
記事における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/abc347
問題A
各A[i]について、A[i]%K==0ならばA[i]/Kを出力します。
例
public static void Solve()
{
var (N, K) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var answers = A.Where(x => x % K == 0).Select(x => x / K).ToArray();
Console.WriteLine(string.Join(" ", answers));
}
問題B
連続する部分文字列は、0<i<j<|S|となるS[i]からS[j]までの文字列となり、|S|は最大でも100なので、iとjの組み合わせを全探索し、その部分文字列S[i..j]を集合などで管理して、最終的な集合の大きさを求めます。
例
public static void Solve()
{
var S = Scanner.Scan<string>();
var N = S.Length;
var set = new HashSet<string>();
for (var i = 0; i < N; i++)
{
for (var j = i + 1; j <= N; j++)
{
set.Add(S[i..j]);
}
}
Console.WriteLine(set.Count);
}
問題C
1週間でループするので、各D[i]をA+Bで割った余りの重複を省いてソートしたものをEとし、Eの長さをMとします。
E[0]日目を1週間の1日目としたとき、全て休日である条件は、E[M-1]が休日であることなので、E[M-1]-E[0]+1<=Aが条件となります。
また、1週間でループするので、E[i+M]をE[i]+A+Bとし、各E[i] (i<M)について同様の条件を判定することで、各E[i]日目を1週間の1日目としたときの判定を行うことができます。
例
public static void Solve()
{
var (N, A, B) = Scanner.Scan<int, long, long>();
var C = A + B;
var D = Scanner.ScanEnumerable<long>().Select(x => x % C).Distinct().Order().ToArray();
var M = D.Length;
var E = new long[M * 2];
for (var i = 0; i < M; i++)
{
E[i] = D[i];
E[i + M] = D[i] + C;
}
for (var i = 0; i < M; i++)
{
if (E[i + M - 1] - E[i] < A)
{
Console.WriteLine("Yes");
return;
}
}
Console.WriteLine("No");
}
問題D
次の動的計画法を解きます。
dp[i,a,b] := i番目のビットまでみたとき、Xのビットが1の数がa、Yのビットの数がbの時のXの値
遷移は次のようになります。
-1を存在しない値とする。
i==0のとき、
Cの0番目のビットが0のとき、
dp[0,0,0] = 0
dp[0,0,1] = -1
dp[0,1,0] = -1
dp[0,1,1] = 1
Cの0番目のビットが1のとき、
dp[0,0,0] = -1
dp[0,0,1] = 0
dp[0,1,0] = 1
dp[0,1,1] = -1
i>0のときかつdp[i-1,a,b]!=-1のとき、
Cのi番目のビットが0のとき、
dp[i,a,b] = dp[i-1,a,b]
dp[i,a+1,b+1] = dp[i-1,a,b] | (1<<i)
Cのi番目のビットが1のとき、
dp[i,a+1,b] = dp[i-1,a,b] | (1L<<i)
dp[i,a,b+1] = dp[i-1,a,b]
最終的にX=dp[N,A,B]となり、Y=C^Xとなります。
例
public static void Solve()
{
var (A, B, C) = Scanner.Scan<int, int, long>();
var N = 60;
var dp = new long[N + 1, A + 2, B + 2];
for (var i = 0; i <= N; i++)
{
for (var a = 0; a <= A; a++)
{
for (var b = 0; b <= B; b++)
{
dp[i, a, b] = -1;
}
}
}
if ((C & 1) == 0)
{
dp[0, 0, 0] = 0;
dp[0, 1, 1] = 1;
}
else
{
dp[0, 1, 0] = 1;
dp[0, 0, 1] = 0;
}
for (var i = 1; i <= N; i++)
{
for (var a = 0; a <= A; a++)
{
for (var b = 0; b <= B; b++)
{
if (dp[i - 1, a, b] == -1) continue;
var bit = (C >> i) & 1;
if (bit == 0)
{
dp[i, a, b] = dp[i - 1, a, b];
dp[i, a + 1, b + 1] = dp[i - 1, a, b] | (1L << i);
}
else
{
dp[i, a + 1, b] = dp[i - 1, a, b] | (1L << i);
dp[i, a, b + 1] = dp[i - 1, a, b];
}
}
}
}
if (dp[N, A, B] >= 0)
{
var x = dp[N, A, B];
var y = C ^ x;
Console.WriteLine($"{x} {y}");
return;
}
Console.WriteLine(-1);
}
問題E
最終的なAの各値は、Sにxが追加してから、Sからxが削除されるまでの集合の大きさの和となります。
このことから、各クエリごとにxがSに追加されたときのクエリ番号と、そのクエリまでの集合の大きさの累積和を管理し、xがSから削除されるときにxを追加したクエリ番号からの累積和をA[x]に足すという処理を行います。
全てのクエリが終わったあとに、Sに残った要素についても同様の処理を行うことで、答えを求めることができます。
例
public static void Solve()
{
var (N, Q) = Scanner.Scan<int, int>();
var X = Scanner.ScanEnumerable<int>().ToArray();
var A = new long[N];
var S = new Dictionary<int, int>();
var cum = new long[Q + 1];
for (var i = 0; i < Q; i++)
{
var x = X[i];
if (S.ContainsKey(x))
{
A[x - 1] += cum[i] - cum[S[x]];
S.Remove(x);
}
else
{
S[x] = i;
}
cum[i + 1] = cum[i] + S.Count;
}
foreach (var (x, i) in S)
{
A[x - 1] += cum[Q] - cum[i];
}
Console.WriteLine(string.Join(" ", A));
}