[AtCoder 参加感想] 2020/04/26:ABC 164

全体感想

体調を崩していてほとんど参加していないのですが。1 時間以上遅れで参加して、Fだけ解いたので、一応書きます。

difficulty は高めに出ていますが、考察の中身は難しくなくて、短時間で仕上げにくいというタイプですね。分からなかった人が多いというよりも、分かったけど解ききれなかった人が多いのでは？

私は初提出までに 35 分かかって、デバッグしてAC するまでに 55 分かかりました。ぎりぎりコンテスト時間内に最初の実装を終えて、提出を済ませたのですが、出力フォーマットすら合っていないｗ

各条件は、次のどれかです。

(a) 全て 0
(b) 0 が存在
(c) 全て 1
(d) 1 が存在

とりあえず簡単に解けそうな場合を場合分けしていって、残った場合を考えます。ひとまず扱いやすい (a) や (c) から攻めていきます。

[1] (a), (c) の条件がひとつもない場合

$N\geq 2$ なら市松模様に塗ればよいです。$N=1$ なら、$U[0]$ などを返します。

[2] (a), (c) の条件がある場合

必要なら転置して、行には条件があるとしてよいです。← こういう処理は、数学の証明においても、プログラムの実装でも、無駄な議論を減らすのに役立ちます。

[21] 行に (a), (c) の条件がともにある場合

このように行を埋めた時点で、どの列も「必ず条件を満たす」「必ず条件を満たさない」のどちらかです。したがって、あとは行の条件だけを気にします。$A[i,j] = U[i]$ のように、$U$ に沿って構築することで、行の条件は全て満たすことができます。

[22] 行に (a) の条件だけがある場合
[23] 行に (c) の条件だけがある場合

どちらも同じなので、[22] だけやっていきます。

[221] 列に (c) の条件がある場合：矛盾
[222] 列に (c) の条件がなく、(a) の条件がある場合

必ず $0$ にしなければいけないところを $0$ にすると、(a) (b) の条件は満たされます。(c) の条件はありません。あとは (d) の条件を満たしたいので、(a)(b) を満たした上で確定していないところは全部 $1$ で埋めます。これで、構築できているか矛盾しているかのどちらかです。

[223] 列に (a) の条件も (c) の条件もない場合

[2231] 行に (d) の条件がある場合

列は、01 混在になると嬉しいので、A[i,j] = U[i] という埋め方で条件を満たします。

[2232] 行に (d) の条件がない場合

いま場合分けのどの時点か一度確認しておきます。
行：(a) or (b)、列：(b) or (d) ですね。あとひといきです。

[22321] 列に (b) の条件がある場合

(a) の行を列本位で A[i,j] = V[j] という埋め方をすれば条件を満たします。

[22322] 行の条件が (a) or (b), 列の条件がすべて (d) の場合

どの列も、1 を欲しいのですが、(b) の行にしか 1 を入れられません。したがって、(b) 行が 1 個以下だと矛盾します。そうでない場合には、複数行に分けて 1 入れれば条件を満たします。