Codeforces Round #630 (Div.2)-E Height All the Same
面白かったので解説を。
問題概要
グリッドがある。 グリッドの各マスにはいくつかのブロックが積んであり、これに対して次のような操作が行える。
- 隣り合っている マスを選び、ブロックを つずつ上に積む。
- マスを選び、ブロックを つ積む。
この操作によって、すべてのマスのブロックの個数を等しくできるような、サイズ * で、初期状態でのブロックの個数が 個以上 個以下であるようなグリッドの個数を、 で数え上げよ。
考察・解法
3秒くらい考えると、可能か不可能かに影響するのは、それぞれのマスのブロックの個数の偶奇だけであることに気づく。
もう少し実験をするなどして考察をすると、グリッドのマス数が奇数なら、いつでも可能であり、偶数なら、「ブロックの個数が偶数であるようなマスの数」が偶数であれば可能である。
まず、マス数が奇数である場合について、これはいつでも可能なので、通り数は である。
マス数が偶数のときは、 個以上 個以下の奇数の個数を , 偶数の個数を として、次のように書ける。
めっちゃ二項定理だが、項が1個飛ばしで抜けている。 実はこれは、
と表現することができ、これを で計算することで、この問題が解ける。 計算量は となる。
感想
結構面白かった。AGCのBの簡単枠にありそう。コンテストの短い時間の中でも安定して解けるくらいにしたい。