AtCoder Beginner Contest 156
最近競技プログラミングをやっているのでそのログも残していきます!
ABC156お疲れ様でした。反省が多い回でした。
C - Rally
のminとmaxの間に最適ながあることが示せますが,制約が余裕なのでで全探索をかけても十分ですね。
D - Bouquet
今回の諸悪の根源。
答えがであることはすぐにわかります。の制約的に,一般的なライブラリでを求めることはできませんが,より階乗を使って求められます。がしかし今回,modを途中で取り忘れた箇所があったことに気づいておらずWAを3回食らってしまいました。
教訓:各操作をするごとにmodを取る。
E - Roaming
終了後に解説ACしました。無念。
以下自分の理解をまとめておきます。
の際は全てのパターンを作ることができるので,個の区別できる部屋に人の人を区別せずに割り振っていくことになります。いわゆる高校数学の重複組合せで,と求められます。
がそれ以下の場合は,動く人と動かない人が出てきます。動く回数が回の場合は,最小の(遠回りしたり,同じ部屋間を行き来しない)移動回数がちょうど回の場合の総和となります。例えばからに部屋を移動するとき,途中の部屋を経由すると+1できるため,最小の移動回数が以下の場合は動く回数が回の移動も可能となります。
最小の移動回数が回となる場合については,まず人動く人を選んで,その人を「人が残っている部屋」に割り振る場合の数をカウントすれば良く,これはとなります。この際,一人一人について,自分がいない通りの部屋に入れば良い,と考えてしまうと,誰か他の人がいなくなった場所に入る場合を考慮してしまいます。すると,ある二つの部屋での人の行き来をカウントしてしまうこととなり,これは移動回数が-2された場合と結果的に等しいのでNGです。
戻ることを含む場合を省いて考える方針が立てられなかったのと,なぜかの時にも で解けるだろうと思い込み,一発で解く方法を考えようとしてしまったのが敗因です。せっかくまではPCが計算してくれるので,制約は贅沢に使おうというのがこの問題の教訓ですね。
参考:
[AtCoder 参加感想] 2019/02/22:ABC 156 | maspyのHP
Fは後日解きます。
次回も頑張ります。