AtCoder ABC204
ABC204参加しました。
A - Rock-paper-scissors
じゃんけん問題。一人の出せる手が3通りで2人の手が決まったとしているので、3x3の9通り書き連ねます。
解説 - AtCoder Beginner Contest 204
B - Nuts
10個以下なら考慮しなくていいです。10個以上なっている場合に回収できるのは、$A_i-10$個です。
解説 - AtCoder Beginner Contest 204
C - Tour
都市ごとに幅優先探索をします。
foreach(都市X in 全都市){
ans += 都市Xを開始としてBFSで訪れた都市数
}
ある都市Xを開始点として、その都市から回れるだけ回っていきます。同じ都市を二度訪れても意味がないので、一度訪れた都市はメモしておいて、再び訪れたら無視します。最終的には都市Xからいける都市を全部訪れることができます。
たどり着いた都市数をカウントしておけば、都市Xをスタートとしたゴール都市数がわかります。
上記を一度の幅優先探索の結果とし、後は開始点とした都市Xを全都市for文で切り替えて行けばok。
注意点として、一度も移動しないことも許されます(つまり開始都市、終了都市が同じ)。これは、グラフで言えば自己ループを追加すればいいです。入力をそのまま受け取っても、自身の都市への経路はないので、自身の都市への経路を足しましょう。そうすれば後は上で書いたBFSがそのまま使えます。
Submission #23234504 - AtCoder Beginner Contest 204
解説 - AtCoder Beginner Contest 204
D - Cooking
各料理をオーブンA,Bどちらに割り振るかの2択で全探索した場合は、料理数が $ 2^{100} $ なので、TLEします。
また、途中で「料理時間が大きい方から」「総料理時間が短いオーブンに」割り当てればいいのではという考えに取り憑かれました。 これは公式回答ページから辿れる kanpurin.hatenablog.com でも、反例が紹介されています。
結局のところ単純な部分和DPになります。
このページがわかりやすかった。これに沿った解答をしてみました。SolveBがそれです。
Submission #23317162 - AtCoder Beginner Contest 204
解説 - AtCoder Beginner Contest 204
まとめ
最近調子が全然奮ってなかったですが、久々にCまでは解けた。 何度も思いますがDPは競プロ初心者には鬼門だと思います。やっぱり難しかった。 ただ、頻度が高い分、なんとかものにしたい。
