脳log[20220624]

2022年06月24日 (金) [AtCoder] 精進。AGC056-A「Three Cells per Row and Column」(水 diff)。N が 3 の倍数のときは簡単だけど 3 で割り切れないと難しい。1 余る場合と 2 余る場合を手で構築してうまく敷き詰められないかと思ったけどうまくできなかった。■提出 #32694973 (AC / 582 Byte / 68 ms)。Array#sample と Array#shuffle! の使用がすべてを物語っている。テキトーにコンピュータに構築させたらええねん。■「テキトー」の解説。1 から N の順列を 1 つテキトーに選んで、i 番目の値が j のとき、j 列の i-1 から i+1 行目を # にする。順列の中で隣接 3 要素の少なくとも 2 つの値が連続しているときは上下に伸ばした # が連結してしまって不都合なので、そういう順列は不採用にする。1 行目から上に伸ばした # と N 行目から下に伸ばした # の扱いが特殊だけど、それぞれ N 行目、1 行目の同列に配置すれば行の条件と列の条件は満たす。そのうえでそれが N-1 行目、2 行目から上下に伸ばした 3 マスと連結になるなら連結成分の条件も満たす(このとき 2 マスの連結成分が 2 つと 4 マスの連結成分が 2 つできている。他は 3 マス)。■自動生成するまで気がつかなかったけど、N が大きいほど構築はテキトーにやって失敗しない。むしろ条件設定を失敗して N=6 の場合に構築できない(どの順列も条件を満たさない)ケースが目立った。人間は N=6 が一番簡単なのになー。