3完。これで緑パフォとは・・・。時間を掛けすぎましたか。
各問題
A - ABC
まず1からKまでの全ての数に対して、A*B
の組がいくつあるかを数えます。素因数分解して組み合わせの数がいくつあるか数えればよいです。
12なら2^2 * 3^1
なので(2+1) * (1+1)
で6通り(1*12, 2*6, 3*4, 4*3, 6*2, 12*1
)という具合。
次に1からKまでの全ての数に対して、組み合わせられるCがいくつあるか数えます。これはCで割ればよいです。
で、1からKまでの全ての数に対して、双方をかけ合わせたものを足しあげれば答えです。
(追記)
今公式解説をみてひっくり返ったのですがいわゆる調和級数というやつで、全探索しても間に合うとのことです。ああ・・・。
B - ABC
Aの1の位が、0, 1, 5, 6のときは何乗しても1の位は変わりません。それ以外のときは、2または4のサイクルで1の位が変わります。2のときは2, 4, 8, 6, 2, 4, 8, 6,...という具合。
なので、B^C%4
がわかればよくて、これも法則性があります。
- Bが4, 8のときは何乗しても4の倍数は4の倍数なので常に0です。
- Bが0, 2, 6のときは、Cが1のときのみ2で、それ以降は(偶数掛ける偶数なので)4の倍数になるのでずっと0です。
- Bが1のときは1に何掛けても1なので常に1です。
- Bが5, 9のときは常に1です。
- Bが3, 7のときは3, 1, 3, 1,...となります。
これはac-libraryのpow_modを使えばすぐに求められます。(コンテスト中はこれに気が付かなかった・・・)
というわけで上記二つを組み合わせれば答えが定まります。
(追記)
上でごちゃごちゃ書いてますが、周期が4であることを踏まえてac-libraryのpow_mod
を使えばとてもシンプルに答えが求められるのでした。
C - String Invasion
今見ている場所より後ろにどの文字がいくつあるかを管理しながら、後ろから見て貪欲に塗りつぶしすればよいです。
D - Sky Reflector
なんとなくぼんやりわかったようなわからないような状態で時間切れ・・・。
まとめ
Bを実験で頑張っていたので、時間がかかりすぎてしまいました。いやそれにしてもみんな早い・・・。
個人的にはこれで水色に戻れなかったらいつ戻るんだよって感じなんですが・・・。