はじめに
AtCoder Beginner Contest 173で久しぶりに3完しました。
順位 5302nd / 10750
パフォーマンス 638
レーティング 502 → 517 (+15)
Contest Result - AtCoder
A - Payment
Nを1000で割って余りが0なら、そのまま。
そうでないなら、Nを1000で割った商に＋1して1000かけて、Nを引いたものが答え。
B - Judge Status Summary
集計処理して、それぞれの要素を表示する。
C - H and V
H,Wの最大が6と小さいので、行と列を選ぶパターンを全て列挙し、それぞれのパターンで条件を満たすか判定すれば良い。とアルゴリズムは全探索でOKなのだが、その実装が素早く正確にできますか？という問題。
全探索の対象がH,Wの2要素あるのもまたしんどい。。ただし、行列を選択する/しないの2択での全探索なので、bit全探索が利用可能。bit全探索をしっかりとマスターして、実装に行ければよかったのだが、自信がなくDFSでの全探索をしてしまった。結果、変数のオンパレードになってかなりぐちゃぐちゃしんどい実装となった。これでACできたの本当に救い。。
ACできたように、本問題はDFSでも解ける。しかし、その場合bit全探索よりコード量が多くなるし、変数も多くなって実装が大変になる。時間もかかる。つまりパフォーマンスが下がる。なので、いくらACできるからといってbit全探索は避けて通るべきではない。DFSできるならそれでいいじゃないかと思っていたけど今回のコンテストでいろんな手札はやはり持っておくべきと痛感した。これが最大の学び。
そして、ちなみに、Pythonだとitertoolsを活用するともっと簡単に実装できる。結論、bit全探索とitertoolsを精進する。
DFSでのACコード
Submission #15005813 - AtCoder Beginner Contest 173
D - Chat in a Circle
コンテスト中には解けなかったが、解説動画にて理解。
N=10くらいで良い感じのサンプルを自作できれば解答できたかもしれないと思ったりもしたが、できなかった。
考察詳細は下記。最近scrapboxを使い始めた。リンクの作り方が秀逸。数式書きやすいで良い感じ。
scrapbox.io
おわりに
基本の全探索はできるようになった！が、bit全探索はできていなかったり、全探索周りの課題があることを再認識、要精進。
