Codeforces #648 解説 - 雄大な大福

A 問題

問題概要

n 行 m 列のグリッドが与えられる
2 人のプレイヤーは行、列共に 1 がないセルを 1 つ選び、セルの値を 1 にする
操作ができなくなったプレイヤーが負け

解説

1 が記録されていない行と列の個数をそれぞれ数えます。
1 回 1 をセルに記録するごとに上の行と列の個数はそれぞれ 1 減少します。
したがって、その 2 つのうち小さい方の偶奇で答えがわかります。
提出したソースコード

B 問題

問題概要

長さ n の数列とそのタイプ (0 or 1) が与えられる
異なるタイプ同士は交換できる
何回か交換を繰り返して与えられた数列をソートできるかどうかを判定する

解説

各タイプがそれぞれ 1 つ以上あれば数列のソートは可能です。
そうでなければ、別の配列に与えられた配列をソートしたものを準備し、
元の配列があらかじめソートされているかどうかを判定します。
提出したソースコード

C 問題

問題概要

長さ n の順列 a, bが 2 つ与えられる
それぞれの配列を循環させて回転した際にインデックスが同じかつ、そのインデックスが示す値が同じである個数を数える
上記の個数の最大値を求める

解説

各順列の値についてそのインデックスを別の配列に記録します (バケットソート的な) 。
その後それぞれの値についての差を求めると a の各要素と b の各要素の距離が求められます。
同じ距離のものを数えて、その個数の最大値を求めます。
提出したソースコード

D 問題

問題概要

n 行 m 列のグリッド (0-indexed で maze[n][m] とする) が与えられる
壁をいくつか設置して、maze[i][j] = B ( $0 \leq i \leq n$ , $0 \leq j \leq m$ ) がゴール地点 (maze[n - 1][m - 1])に辿り着けないようにする
この時 maze[i][j] = G ( $0 \leq i \leq n$ , $0 \leq j \leq m$ ) は全てゴール地点に辿り着けるようにすることができるかを求める

解説

最初に B のセルが移動可能な方向を確認します。
その際に G のセルと隣接していた場合、G と B は常に一緒に行動することができてしまうため、答えは無条件で No です。
そうでなく、隣接セルが通路 (.) の場合、壁 (#) で覆います。
その後、ゴール地点から BFS などをして、各セルについて見ていきます。
その時にセルが G であるにも関わらず、ゴール地点にたどり着くことができないセルがあれば No 、そういったセルがなければ Yes です。
提出したソースコード

E 問題

問題概要

n 個の正整数からなる数列 A が与えられる
k 要素からなる空でない部分列を選ぶ
部分列の値を $\sum 2^{i}$ とする
ここで部分列中の要素の少なくとも $max(1, k - 2)$ 個は i 番目の bit が 1 でなければならない

解説

$k > 3$ の時は 3 要素を選ぶのが最適らしい。
$k > 3$ の部分列に関してはその中からランダムに 3 要素選ぶと、鳩の巣原理から最低 1 つの要素は i 番目の bit が 1 。
したがって部分列の要素を 3 としてループを回せば良い。
3 重ループをしても十分制限時間に間に合う。
提出したソースコード