AtCoder Beginner Contest 156

　このブログ更新に少し時間が空いてしまった……。二か月前だと記憶も薄れていってしまう。ある程度時間が経ってから問題を見直すのは復習として悪くないと思うけど、二ヶ月は長すぎる。書く内容を少なくしても更新速度を上げていきたい。

　この回は、Fで1caseのTLEが取れず五完でした。まあ、解法はあっていたので良いとします。

コンテストへのリンク

D - Bouquet

　n種類の花から花束を作る方法は、$2^n$通り（これは、「花のないの花束」も含んでいるので、答えはここからｰ1）

　そこから、ちょうどa種類の花束nCa通りと、b種類の花束nCb通りを引く。

　立式は単純だけど、これをこの問題の制約で解くにはベキ乗計算やコンビネーション計算をmod 素数で行わなくてはいけなくて、「繰り返し二乗法」や「フェルマーの小定理」を勉強させる教育的な問題だったんですね。

　この辺は、知らないとどうしようもない知識ですよね……。

E - Roaming

　制約が優しい問題。

　n=2やk=1の場合が入っていたらもっと難しかった。

　そういうのがないので、n人を(n-k)個以上の部屋に割り振る重複組み合わせと、k個の空き部屋の組み合わせで計算できる。

F - Modularness

　mod kでa+dがaより大きくなるのはどんなときか？　と考える。aもdもmod kで考えて良い。このとき、d=0でなく、また、a+d>=kとならなければ、大きくなっている。

　つまり、「繰り上がらなければOK」と気付くのが最大のポイント。

　あとは、Dが周期的に変化するので、「周期的に変化する部分」と「その後の部分」を分けて考える。ただ、今回は初期値が変わるので、「一周ごと」は考えにくい。「周回中」と「それ以後」で分けて考えればOK。

なので、

・周回中の(n-1)/k周で何回繰り上がるか、d=0なのは何回かを求める。

・その後の初期値を求め、残りはシミュレーション

で解ける。

　なお、本番中はTLEでした。

　この解法だと、sum(D)とD.count(0)を求める必要があるけど、こうやって組み込み関数二回使うより、自分でfor文で実装した方が速いらしい。

　確かに、計算回数は2*k→kに減ってるけど……。組み込み関数は速い印象があったので意外でした。