ABC049

README

ABC049過去問感想

新しく設定したneovimで解いたのでかなり時間がかかってしまった。

• A問題は特になし。
• B問題は文字列処理っぽいが単に1行を2回出力するだけなのでとても簡単。
• C問題は場合分けで何とか解けると思ったがWAが排除できそうになかった。
  • 単語全体が他の単語の接頭辞になっていると判別が難しくなってしまう。
  • 逆向きに処理することで見通しが良くなる、というのは文字列処理の中の代表的パターンの1つと思われるので、よく覚えておきたい。
• D問題はUnionFind木を使うというネタバレがあっても解けなかった。
  • しかも解答PDFを読んだあと実装しても、依然としてサンプルが通らないという体たらく。
  • 結局、UnionFindアルゴリズムについてより深く理解するきっかけとなったのは良かった。

---

Union Findについて

各種関数の引数に異なる xxParents というスライスを渡す

これによって、2種類の異なるネットワークについて連結成分を管理することができる。

root 関数について

今回は、各ノードを unite した後、能動的にmain関数から root 関数を実行する必要があった。

UnionFind木を構築する中で、必ずしもあるノードの親と根が一致するとは限らないことに注意（当たり前だが）。 same 関数で根ノードの一致を判定する中で、経路圧縮が行われ、parents スライスの中身も根ノードで揃えられていく。

今回の問題で、root 関数によって根ノードを調べれば、連結成分である限り確実に一致する こと（イメージ）を頭に叩き込むこと。 （根ノードの一致性をチェックすることで同一グループか（連結か）どうかを判定しているのだから、ごくごく当たり前なのだが）