競プロ日記

C 白昼夢 / Daydream

コード
https://atcoder.jp/contests/abc049/submissions/6953590


微妙に迷った問題。
ちょっと考えて「これ後ろから調べていけば被らなくないか？」と思ったが、どうも裏道っぽかったからパスしてしまった。
というのも、仮に被るような文字列だった場合に解けないのはちょっとどうなんだろうということで、これは違うだろうと考えたからだ。
解いてから解説を見ると意外にもこれが想定解でびっくり。

その後しばらく考えて思いついたのがdp的な解法。
Sのi番目から始まる文字列で、指定の文字列(dream, dreamer, erase, eraser)が作れるかどうかは、Sのi-1番目以前には関係しないので、i=0から順に調べていこうという感じ。
こういうdpの典型例的な問題あっても良さそうだけどあるのかな？
重複なし優先度付きキューとしてSTLのSetを使ったが、dpでSetなんか使うのかなー違うのかなーとも思ったが一発でACできてほっこり。
計算量を計算しようと思ったけど思ったより難しかった・・・。
重複なしで計算量を多少落としたつもりだが、指定の文字列の文字数が短かったり、文字数のバリエーションが多かったりすると結局ほぼ全探索になる？
そういう場合は後ろから調べると被らない、という部分を活用しないといけないのかな。
そっちの解法も後で解いておこう。

D 連結 / Connectivity

コード
https://atcoder.jp/contests/abc049/submissions/7033954


今回はUnion-Find！やったー！
データ構造を扱う問題を調べながら理解できるとテンションが上がる。
何ならライブラリとして理解しながら実装していく瞬間が一番楽しいかもしれない。

もちろんUnion-Find使うよっていう部分は分からなかったから最初は解説頼り。
公式の解説は想像以上に簡素で、本当にUnion-Find使うよっていう部分しか分からなかった。
実際にUnion-Findを使って実装してみると、その後に工夫がまた1つ必要で、愚直に計算するとO(n^2)でTLEした。
「n<=2*10^5ならそんなに重い処理じゃないだろうしO(n^2)くらいけるのでは？」と思ったが全然そんなことはなかった。
10^8が相当軽い処理でギリギリとのことで、10^6,7程度を目安にするべきらしい、覚えておこう。

その後の工夫を実装してスッキリ解けたのだが、工夫部分説明がなかなかしっくり来るものがなかったから記録しておく。

Union-Findで道路のグループroadと鉄道のグループtrainを作成したとき、i番目の街とj番目の街が道路と鉄道のどちらでも繋がれているかどうかを求めるには、
・i番目の街が属する道路のグループにj番目の街が属しているか
・i番目の街が属する鉄道のグループにj番目の街が属しているか
この論理積を取れば良い。
これはグループ内で街が条件に合っていくか走査していくようなイメージだと思う。
これをi,jで2重ループすることで総数を数えられるが、この考え方に固執すると2重ループを外せず工夫部分をすんなり理解できない。

考え方を変えて、
・i番目の街が属する道路のグループとj番目の街が属する道路のグループが同じかどうか
・i番目の街が属する鉄道のグループとj番目の街が属する鉄道のグループが同じかどうか
の論理積を取ることを考える。
どちらもやっていることは同じだが、考え方は結構変わる。
片方が属するグループ内でもう片方の街を探していくのではなく、それぞれの街が属するグループを求めてから同じかどうか判別するイメージ。
こう考えると、道路と鉄道を分けて論理積で考えずに、(道路のグループ, 鉄道のグループ)のペアで保存しても良いことが分かる。
後は連想配列なりで総数を保存してあげれば1重ループで解けちゃう！

Union-Findの操作的には後者の方が近いが、単純に考えると前者の方が直感的だと思う。
自分は前者の考え方からなかなか抜け出せずに、多くの解説がなかなか理解できなかった。
図説を見て、さらに自分で書いてやっと抜け出せた。
考え方を固定してしまうのは怖い怖い。