N高等学校のコンピューター部がパソコン甲子園で頑張っているのに触発されて久しぶりに、AtCoder Beginner Contest 073 にチャレンジ。
AtCoder Beginner Contest 073 - AtCoder Beginner Contest 073 | AtCoder
結論から言うと、A, B, C はすぐ終わったもののDがハマって解けなかった。 解法的にはあってたっぽい。
Aは、除算と剰余ができればOK。
Bは、for文で回して足し合わせができればOK。
Cは、setに突っ込んだり、消したりして最後に数を数えればOK。
そして最後のDだけを考える。
最短経路問題なので、ダイクストラかワーシャルフロイドで解けそうということがわかる。
方針として通らなきゃいけない町の集合Rの順列を作っても8!で計算できそうだったので 全ての町間の最短距離を計算すればええやんという話に。
で、結局解けずw
解法的にはあってたっぽいけれどハマったところ
- 町は0からはじまりじゃなく1からははじまりなのにfor文ミスる
- これはforマクロそろそろ用意した方が良いんじゃないかという気がした。
- INT_MAX + INT_MAX があってオーバーフローして負の数字が出てたサンプルが全部通ったけどこれに気づかずに1時間以上悩んだ
- 解説を見て #define INF (1 << 29) とかを使った方が良いということを学んだ
- next_permutationはvectorをちゃんとソートしてないと使えない
- ドキュメントちゃんと読んでなかった奴
- これまた中途半端に通ったりしたのでハマった
最終的に解けたけどいろいろ学びのあるABCだった。というかまたAtCoder、テストケースの内容をぜひアップロードしてほしい…。間違いに気づくのが本当に大変でした。
ソースコードは、
N高の生徒たちもすごくがんばって学んでいるので、自分も競プロ初心者ながら、アリ本を少しずつ学んでAtCoderにもモリモリ参加していこうと思います。
生徒たちの間で競技プログラミングの面白さ伝えていきたいところ。大学になってから特に数学死ぬほど苦手だったけど、数学とも少しずつ仲良くなっていきたい。 少なくともABCぐらいだったらあんまり数学関係ないけど、ある程度行くと数学がどうしても必要になってくるということがわかってきた今日この頃。
