脳log[20211122]

2021年11月22日 (月) [AtCoder] 精進。ARC112-D「Skate」(ギリギリ黄 diff)。初見ではない。グリッドだけど行列に見える。行と列を並べ替えて寄せていってもいいのかなと。島(#)がない行か列に足場(#)を作って連結していくことを考える。だけど足場が行と列の両方で孤立している場合には連結にならない。そこから連結しているもの同士が複数のグループに分かれて孤立している場合に想像が及ぶ。行で連結するのがいいか列で連結するのがいいか、両方のベストミックスを考える必要があるのか。いろいろ考えてしまって答えが出なかったのが初見のとき。今回は UnionFind でなんとかなりそうだと見当がついた。提出 #27452260 (AC / 471 Byte / 830 ms)。■青 diff の後ろの４問目でなければ水 diff だった可能性もあるのでは？ こんなアンケートがあったよ。「ARC112 C(DFS Game)とD(Skate) どっちの方が難しいと感じましたか」 結果は７対３で C。印象通りだけど C 問題の方は時をおかずに解けているのも事実>20210216p01。■「Ruby によるすべての提出」を見ると他の AC (３つ)はほぼ半分の 400 ms 前後で処理を終えている。どうやら行と列に分けて２回の UnionFind を行う必要はなかった。行と列の組み合わせを一意に識別する (縦×横) 通りの通し番号を使うことは考えていたのだけど、そもそも # がある場所について、ある行に対する列、ある列に対する行を識別する必要がなく、(縦+横) 通りを考えるだけで良かった。提出 #27452260 (AC / 467 Byte / 445 ms)。