AtCoder Beginner Contest 156

結果

順位   228th / 5737
パフォーマンス   2034
レーティング  1753 → 1784(+31)

　E問題までの5完。F問題も解きたかったけど、終了後10分くらい粘ってもダメだったのでそんなに行けそうでもなかった。

A - Beginner

　最初提示されているのが表示レーティングかと思って入力例1の結果が全然違ってびっくりした。

　提出

B - Digits

　えー、難しくない？でも割っていくだけで良かったのか。余計な実装をしてしまった。

　提出

D - Bouquet

　最初は脳死で事前計算するCombinationを持ってきて、いやでもダメじゃんとなって普通に計算する方のCombinationを計算。なんかいまいち綺麗に書ききれなかったな。

　提出

E - Roaming

　わりと早い段階で「最終的に空になる部屋が $i$ 個」の場合の数を計算すれば解けそうという観点が出てきた。それで考えていくと、空になる部屋を選ぶnCiと、 $i$ 人が $n - i$ 部屋のうちのどこかに属する{n - 1}_C_iが見えるので勝ち。後ろのやつを考えるとき僕もooo|||oooみたいな丸と仕切りの図を書いてしまうね。

　 $k = 1$ の場合コーナーケースだとか？全室埋まりが作れないというところかな？全然気づかないでやっていた。

　無駄なMODpowを削除しないまま提出してしまったのが悔やまれる。コードゴルフをやるつもりはないけどできるだけ無駄な記述はない状態で出したい。

　提出

F - Modularness

　クエリ問題になっている意味が何かあるのかなとちょっと疑ったけど、普通に各クエリを $O(k)$ で解くことができそうと判断してそれに向かう。

　クエリが $n, x, m$ として、足される $d$ が $k$ で周期が回るので、 $k$ の倍数でどこかループすることがわかる。そのループ周期は $(\sum k) l \equiv 0 \;(\mathrm{mod} \;m)$ みたいな感じで書けるので、 $\sum k$ と $m$ で最小公倍数をどうのこうのすると周期がわかるんですね〜。

　あとは条件に合うものを数える方法を考える。初めに $d$ を $m$ で割った余りに加工しておくんだけど、 $d_i \% m = 0$ のときは $0$ ではなく $m$ にしておけば、失敗するときはなんか $m$ で割った商が増える感じになるのでそれを上手く計算すればできる。

　しかし入力例2とかで1ズレたり合ったりするので終わり。 $n$ を1小さくするべきなのかそうじゃないのかがわからなかった。

　コンテスト終わってから気づいたけどこれループ周期とかを考える必要はないんですね。オーバーフローしないかとか心配になったんだけど、 $d$ の各要素が最大 $m$ で、全体が $k$ 個で、それを $\frac{n}{k}$ 個足しうるから $nm$ で大丈夫なんだ。32行で綺麗に書けたので自分としてはこれで満足。でもfinalはC++の予約語？にあるから変数名にするのはやめようねとAtCoderのコード表示を見ていて思った。

　提出

水たまり