CODE FESTIVAL 2017 qual A A, B, C 考察

code-festival-2017-quala A - Snuke's favorite YAKINIKU

S が YAKI からはじまるかを調べれば良い。 Rust なら starts_with がある。

N, M <= 10^3 なので O(NM) で選択する行と列を 1 ずつ増やして全探索すれば良い。反転するので行と列の両方で選ばれたマスは白になる点に注意する (入力例のおかげで気づくことができる) 。

0..=N 0..=M のように N M を含みそびれていて 2 WA 。

1x1 から 4x4 くらいまでを実際に書いて確かめつつ各パターンをカバーできるように実装した。

まず各文字と個数を数える。これを BinaryHeap で個数の大きいものから順に取り出して個数を減らして戻すを繰り返していく。

偶数 x 偶数の場合は 4 ずつ減らして最後までいけるなら OK 。

偶数 x 奇数 (または奇数 x 偶数) の場合は奇数側の 1 行 (列) を残してほかは 4 ずつ減らす。これで偶数 x 1 (または 1 x 偶数) になる。あとは 2 ずつ減らして最後まで (1 残るものは無視) いけるなら OK 。

奇数 x 奇数の場合はさらに 3 つに分けられる。

1 x 1 の場合は OK 。

1 x 奇数 (奇数 x1) の場合は 2 ずつ減らして最後まで (1 残るものは無視) いけるなら OK 。

奇数 x 奇数の場合は中央を通る縦横 1 行・ 1 列を残した他のマス分だけ 4 ずつ減らす。あとは 2 ずつ減らして最後まで (1 残るものは無視) いけるなら OK 。

リングフィットアドベンチャーを続けている。