いろいろな記録

大学院生やってます

AtCoder Beginner Contest 156

最近競技プログラミングをやっているのでそのログも残していきます!

  

ABC156お疲れ様でした。反省が多い回でした。

C - Rally

atcoder.jp

X_iのminとmaxの間に最適なPがあることが示せますが,制約が余裕なので P = 1 \text{~}100で全探索をかけても十分ですね。

 

D - Bouquet

atcoder.jp

今回の諸悪の根源。

答えが 2^n - {}_n C _a - {}_n C _b - 1であることはすぐにわかります。nの制約的に,一般的なライブラリで {}_n C _a を求めることはできませんが, a, b \leq 2 * 10^5 より階乗を使って求められます。がしかし今回,modを途中で取り忘れた箇所があったことに気づいておらずWAを3回食らってしまいました。

教訓:各操作をするごとにmodを取る。

 

E - Roaming

atcoder.jp

終了後に解説ACしました。無念。

以下自分の理解をまとめておきます。

 k \geqq n - 1の際は全てのパターンを作ることができるので,n個の区別できる部屋にn人の人を区別せずに割り振っていくことになります。いわゆる高校数学の重複組合せで, {}_n H _n = {}_{2n - 1} C _nと求められます。

 kがそれ以下の場合は,動く人と動かない人が出てきます。動く回数がk回の場合は,最小の(遠回りしたり,同じ部屋間を行き来しない)移動回数がちょうどi (\leqq k)回の場合の総和となります。例えばaからbに部屋を移動するとき,途中の部屋cを経由すると+1できるため,最小の移動回数がk以下の場合は動く回数がk回の移動も可能となります。

最小の移動回数がi回となる場合については,まずi人動く人を選んで,その人を「人が残っている部屋」に割り振る場合の数をカウントすれば良く,これは {}_{n - i} H _i = {}_{n - 1} C _iとなります。この際,一人一人について,自分がいないn-1通りの部屋に入れば良い,と考えてしまうと,誰か他の人がいなくなった場所に入る場合を考慮してしまいます。すると,ある二つの部屋での人の行き来をカウントしてしまうこととなり,これは移動回数が-2された場合と結果的に等しいのでNGです。

 

戻ることを含む場合を省いて考える方針が立てられなかったのと,なぜか k \leq n - 1の時にも O(1)で解けるだろうと思い込み,一発で解く方法を考えようとしてしまったのが敗因です。せっかくO(n)まではPCが計算してくれるので,制約は贅沢に使おうというのがこの問題の教訓ですね。

 

参考:

[AtCoder 参加感想] 2019/02/22:ABC 156 | maspyのHP

 

Fは後日解きます。

 

 

次回も頑張ります。