ABC065D(ARC076B)で苦労した話

反省文を書く。子育ての合間にAtCoderの過去問を解いたりしてる。 で実装に手間取ったので判断ミスをしたところの確認と対処を記録する。

この過去問を解いていた。 MSTのコストが答えなのでPrimかKruskalで良いだろうと考えた。 ノードが平面上にあるという特徴があるのでエッジの絞り込みに使えば終わるだろうと踏んでいた。

でPrimを採用して実装した。予想通りにTLE。でエッジの絞り込みを実装を始めた。 WA, WA, … 最終的には、実装方針を変えエッジ候補を事前に絞り込んだKruskalで解決( AC )した。

大量の WA 。根本的には正確に実装する力が低いからWAを多発させてしまったわけだけど、 今回の問題について設計的な判断を誤ったのが具体的な失敗箇所。

候補エッジを絞る処理をヒープに追加するところで行う実装を目指してしまったことがバグの温床を作ってしまった。

今回のケースでは平面上の点という特徴があり、事前に簡単に絞ることができる。 最初に採用したPrimに引きずられてエッジの絞り込みを適切なタイミングを考慮せず埋め込んだのがミス多発の原因だ。

コード内で枝狩りなど最適化を行うフェーズをどこに置くのが適切でバグが少なくなるかは書き出す前に考え直す癖を作らないとならないなぁと感じた。 そうすれば今回の場合なら、絞り込みを行った時点でエッジが全てリストで手に入るのでKruskalに実装を切り替えるのが自然と思いつく。 あと、そもそも最初にエッジを絞れると気付いていたにも関わらず動く実装に飛びついたのもダメだった。アルゴリズム設計に少し時間をかければ躓くこともなかったはずだ。

問題が簡単なときに基本的なアルゴリズムに帰着させることができるようになってきたけど、細かいミスは多発する。 それを減らすためにvim環境を少し整えた。

• 最近、壊れてたlsp対応を直した
• snipetを増やした
• templateを作った
• keymapを整理した
• いらないPluginを除去した