AtCoder Beginner Contest204に参加しました。
結果
A,B,C問題の3問正解でパフォーマンスが 867でした。
最近またD問題が解けなくなってきてる。C問題までを早解きしてなんとかパフォーマンスは稼げてるけど…
A - Rock-paper-scissors
問題文の通りじゃんけんをすれば良い。
全員が同じ手を出しているか、全員がバラバラの手を出しているかの2パターンあるのでどちらのパターンか判断して適切な手を選ぶ。
グーチョキパーが0,1,2に変換されているので、全員がばらばらのパターンの場合2人の手を足したものが1,2,3のどれになっているかで足りない手を判断すれば良い。
B - Nuts
制約を見るとNが1000と小さいので前から順番に条件を満たすかどうか確認して、累積和を計算すれば良い。
具体的にはが10より大きい場合は
を足していけば良い。或いは、
を足し続けていくのでも良い。
C - Tour
各都市をスタートとして全部の都市に対して経路計算をしてどの都市からどの都市にたどり着ける・たどり着けないを判断する。たどり着ける都市の組合せを数えればそれが答えになる。
経路計算は幅優先探索でもダイクストラでもなんでも良さそう。
D - Cooking
解けそうで解けなかった問題。 問題文を読むと結局次の問題を解けば良いと思った。
- N個のアイテムを2つのグループに分ける。
- 2つのオーブンの使用時間の大きい方を最小化する。
2つ目の最大値の最小化問題なら二分探索を使うのが定番。 1つ目の2つのグループに分けるって方がうまくできなかった。 bit全探索とか色々試したけどだめだった。
