はじめに
AtCoder Beginner Contest 232の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc232
問題A
xで文字列を分けてそれぞれ掛けます。
public static void Solve()
{
var S = Console.ReadLine().Trim().Split('x');
var answer = long.Parse(S[0]) * long.Parse(S[1]);
Console.WriteLine(answer);
}
制約が3文字なので、aとbからそれぞれ文字0を引いて掛けるだけいいと思います。
public static void Solve()
{
var S = Console.ReadLine().Trim();
var answer = (S[0] - '0') * (S[2] - '0');
Console.WriteLine(answer);
}
問題B
a-zを0-25とし、26通りのずらし方を試すことで、全部のパターンを調べることができます。
zの次はaなので、26はaとなるため、26で余りを取ることで26の周期として扱うことができます。
public static void Solve()
{
var S = Scanner.Scan<string>().Select(x => x - '0').ToArray();
var T = Scanner.Scan<string>().Select(x => x - '0').ToArray();
for (var k = 0; k < 26; k++)
{
var ok = true;
for (var i = 0; i < S.Length; i++)
{
ok &= (S[i] + k) % 26 == T[i] % 26;
}
if (ok)
{
Console.WriteLine("Yes");
return;
}
}
Console.WriteLine("No");
}
問題C
2つのグラフG1とG2が同じ形であることは、G2の頂点番号のみを適切に置き換えたときに、G1のそれぞれの辺に対応する辺を持つことを示すことで判定することができます。
制約も1<=N<=8と小さいので、G2のそれぞれの頂点に対応する順列を総当たりし、G2の辺E2の頂点を置き換えた辺すべてが、G1の辺E1に存在するかを判定します。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var E1 = new bool[N, N];
var E2 = new (int A, int B)[M];
for (var i = 0; i < M; i++)
{
var (a, b) = Scanner.Scan<int, int>();
a--; b--;
E1[a, b] = E1[b, a] = true;
}
for (var i = 0; i < M; i++)
{
var (a, b) = Scanner.Scan<int, int>();
a--; b--;
E2[i] = (a, b);
}
foreach (var order in Enumerable.Range(0, N).Permute())
{
var ok = true;
foreach (var (c, d) in E2)
{
ok &= E1[order[c], order[d]];
}
if (ok)
{
Console.WriteLine("Yes");
return;
}
}
Console.WriteLine("No");
}
Permuteメソッドは自作のLINQ拡張メソッドです。
問題D
移動方法がi+1かj+1のみなので、左上のマスから行くことができるマスを数え上げます。
もし隣り合うマスが.ならば、そのマスの現在の値と今いるマスの値+1との最大を集計することで、そのマスまで通ったマスの数の最大値をまとめることができます。
制約により左上の値が1のため、マスの値が0の場合は、マスが#、または到達不可能といえるので、判定を無視することができます。
public static void Solve()
{
var (H, W) = Scanner.Scan<int, int>();
var C = new char[H][];
for (var i = 0; i < H; i++)
{
C[i] = Scanner.Scan<string>().ToArray();
}
var G = new int[H, W];
G[0, 0] = 1;
var answer = 0;
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
if (G[i, j] == 0) continue;
answer = Math.Max(answer, G[i, j]);
if (i + 1 < H && C[i + 1][j] == '.')
{
G[i + 1, j] = Math.Max(G[i + 1, j], G[i, j] + 1);
}
if (j + 1 < W && C[i][j + 1] == '.')
{
G[i, j + 1] = Math.Max(G[i, j + 1], G[i, j] + 1);
}
}
}
Console.WriteLine(answer);
}
高橋君がマス (1,1) から歩き始めるとき
ほかの場所から再開できると勘違いして4WAしました。
解説では、逆順にマスの値を確定させていくことで、左上のマスに最終的な値をまとめているみたいです。
問題E
コンテスト中の考察です。
K=1の時は、(x1 == x2 && y1 != y2) || (x1 != x2 && y1 == y2)の場合のみ到達可能
K=2の時は、
(x1 == x2 && y1 == y2)ならば、H-1またはW-1
(x1 == x2 && y1 != y2)ならば、H-2
(x1 != x2 && y1 == y2)ならば、W-2
(x1 != x2 && y1 != y2)ならば、2
K>=3の時は、
K-2を数え上げたうえでK=2の盤面ができれば解くことができないだろうか。
for(var h = 0; h < K - 2; h++)
{
var w = K - 2 - h;
// 組み合わせ?
}
時間切れになりました。
解説では、4通りの状態のdpでした。
// dp[k, 0, 0]: k回動いた時の(x1 == x2 && y1 == y2)の状態
// dp[k, 0, 1]: k回動いた時の(x1 == x2 && y1 != y2)の状態
// dp[k, 1, 0]: k回動いた時の(x1 != x2 && y1 == y2)の状態
// dp[k, 1, 1]: k回動いた時の(x1 != x2 && y1 != y2)の状態
// 初期状態
dp[0, x1 == x2 ? 0 : 1, y1 == y2 ? 0 : 1] = 1;
for (var k = 0; k < K; k++)
{
dp[k + 1, 0, 0] = dp[k, 0, 1] + dp[k, 1, 0];
dp[k + 1, 0, 1] = dp[k, 0, 0] * (W - 1) + dp[k, 0, 1] * (W - 2) + dp[k, 1, 1];
dp[k + 1, 1, 0] = dp[k, 0, 0] * (H - 1) + dp[k, 1, 0] * (H - 2) + dp[k, 1, 1];
dp[k + 1, 1, 1] = dp[k, 0, 1] * (H - 1) + dp[k, 1, 0] * (W - 1) + dp[k, 1, 1] * (H + W - 4);
}