はじめに
AtCoder Beginner Contest 298の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc298
問題A
文字列Sにoが含まれているかつ、Sにxが含まれていないという条件を満たすかを判定します。
文字列内にある文字が含まれているかはstring.Containsで調べることができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
var answer = S.Contains('o') && !S.Contains('x');
Console.WriteLine(answer ? "Yes" : "No");
}
問題B
行列Aを4回回転させると元に戻ることから、調べる必要がある行列Aの状態は4つであることがわかります。
そのため、Aを回転させながら、A[i][j]==1のときB[i][j]==1であることを4回判定します。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = new int[N][].Select(_ => Scanner.ScanEnumerable<int>().ToArray()).ToArray();
var B = new int[N][].Select(_ => Scanner.ScanEnumerable<int>().ToArray()).ToArray();
bool F(int[][] C)
{
var result = true;
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
if (C[i][j] == 1)
{
result &= B[i][j] == 1;
}
}
}
return result;
}
int[][] Rotate(int[][] C)
{
var result = new int[N][];
for (var i = 0; i < N; i++)
{
result[i] = new int[N];
for (var j = 0; j < N; j++)
{
result[i][j] = C[j][N - 1 - i];
}
}
return result;
}
var answer = false;
for (var k = 0; k < 4; k++)
{
answer |= F(A);
A = Rotate(A);
}
Console.WriteLine(answer ? "Yes" : "No");
}
問題C
辞書などのデータ構造と順序集合を使って、C[i]にはiが書かれたカードが入っている箱の番号を重複を許さず昇順にならべた集合を管理し、B[j]には箱jに入っているカードに書かれた数を重複を許して昇順にならべた集合を管理することで、次のような操作で答えを求めることができます。
- 1番目の形式のクエリについて、
B[j]にiを追加し、C[i]にjを追加する。 - 2番目の形式のクエリについて、
B[i]を表示する。 - 3番目の形式のクエリについて、
C[i]を表示する。
C#では、SortedSetを使うことで順序集合を得ることができますが、重複する要素を管理することはできないので、j番目の箱にiが書かれたカードが何枚あるかを別に管理し、2番目のクエリの形式でその枚数繰り返したものを出力する必要があります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var Q = Scanner.Scan<int>();
var B = new Dictionary<int, SortedSet<int>>();
var C = new Dictionary<int, SortedSet<int>>();
var Bc = new Dictionary<int, Dictionary<int, int>>();
while (Q-- > 0)
{
var query = Scanner.ScanEnumerable<int>().ToArray();
if (query[0] == 1)
{
var (i, j) = (query[1], query[2]);
if (!B.ContainsKey(j)) B[j] = new SortedSet<int>();
if (!C.ContainsKey(i)) C[i] = new SortedSet<int>();
if (!Bc.ContainsKey(j)) Bc[j] = new Dictionary<int, int>();
if (!Bc[j].ContainsKey(i)) Bc[j][i] = 0;
B[j].Add(i);
Bc[j][i]++;
C[i].Add(j);
}
else if (query[0] == 2)
{
var i = query[1];
Console.WriteLine(string.Join(" ", B[i].SelectMany(x => Enumerable.Repeat(x, Bc[i][x]))));
}
else
{
var i = query[1];
Console.WriteLine(string.Join(" ", C[i]));
}
}
}
問題D
文字列Sの管理に整数型を使ってしまうと、Qが最大でも6e5なので正確に値を管理することができません。
また、3番目の形式のクエリごとに文字列から愚直に値を求めようとすると、クエリごとに時間計算量がO(|S|)になり、全体時間計算量がO(Q^2)になってしまいます。
VをSの十進数表記の数として998244353で割った余りとしたときを考えます。
- 1番目の形式のクエリのとき、
V=(V*10+x)%998244353になります。 - 2番目の形式のクエリのとき、
Sの先頭をxとすると、V=V-10^(|S-1|)*xになります。
このことから、Vの値を保持しながらQueueなどのデータ構造を使って、その時点のSの先頭と長さを管理することで、クエリあたりの計算量を高速化することができます。
2番目の形式のクエリのときに、10^|S-1|を求めるには時間計算量がO(log|S|)必要になりますが、あらかじめ10のべき乗を時間計算量O(N)で計算しておくことで、クエリのごとの時間計算量O(1)で求めることができます。
以上のことから、全体時間計算量O(N+Q)で求めることができます。
public static void Solve()
{
var Q = Scanner.Scan<int>();
var P = new mint[Q + 10];
P[0] = 1;
for (var i = 0; i + 1 < P.Length; i++)
{
P[i + 1] = P[i] * 10;
}
mint curr = 1;
var queue = new Queue<int>();
queue.Enqueue(1);
while (Q-- > 0)
{
var query = Scanner.ScanEnumerable<int>().ToArray();
if (query[0] == 1)
{
var x = query[1];
curr *= 10;
curr += x;
queue.Enqueue(x);
}
else if (query[0] == 2)
{
var len = queue.Count - 1;
var x = queue.Dequeue();
curr -= P[len] * x;
}
else
{
Console.WriteLine(curr);
}
}
}
問題E
次のような動的計画法を解きます。
dp[i,j,k] := k(先手|後手)のとき高橋君の位置が地点i、青木君の位置が地点jにいる確率
また、次のような遷移になります。
- 初期状態
dp[A,B,1] = 1 // 高橋君から始めるので、青木君が後手で高橋君がA、青木君がBについたところから開始する
dp[Min(i+p,N),j,0] += dp[i,j,1]/P; // 1<=p<=P
dp[i,Min(j+q,N),1] += dp[i,j,0]/Q; // 1<=q<=Q
dp[N,j,0] (B<=j<N)の総和が答えとなります。
public static void Solve()
{
var (N, A, B, P, Q) = Scanner.Scan<int, int, int, int, int>();
var dp = new mint[N + 1, N + 1, 2];
dp[A, B, 1] = 1;
var iP = mint.Inverse(P);
var iQ = mint.Inverse(Q);
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
for (var p = 1; p <= P; p++)
{
dp[Math.Min(i + p, N), j, 0] += dp[i, j, 1] * iP;
}
for (var q = 1; q <= Q; q++)
{
dp[i, Math.Min(j + q, N), 1] += dp[i, j, 0] * iQ;
}
}
}
mint answer = 0;
for (var j = B; j < N; j++)
{
answer += dp[N, j, 0];
}
Console.WriteLine(answer);
}