AtCoder ABC156 メモ

ABCDEを解きました。青パフォ上位なのは嬉しいですがF解けなかったのが悔しい。

D Bouquet

combination(n, a)のnが大きくaは小さいのでn(n-1)...(n-a+1)とa!を求めないと計算できないです。

E Payment

はじめ各部屋の人数がk以下の個数を数えようとして時間を溶かしました。 0人の部屋の個数iを固定して、どの部屋を0にするかnCi と 残りの部屋に1人以上割り振る方法で nCn-iをかけます。 iごとに足せば計算できます。(0<=i<=Min(N-1, K))

K=1だとi=0とできないですが制約的に関係ありません。

F Modularness

次のような方針を考え続けて時間を終えました。

各diごとに考える。aj (j=i mod k)がaj-1より大きくなる条件は？a0にsum(di) を何度か足してd0...di-1を足したものがaj-1。diを足すとaj。なので頑張ってmod m が1変わるjの個数を探す。 di + x*y < n mod m みたいになるX以下のxの個数を数えることができればこの問題は解ける。

twitterを見ると同じ方針で解こうとした人は結構いたっぽいです。 しかも解き方自体は存在するらしい！ ( https://twitter.com/maspy_stars/status/1231219562076459010 )

しかし、とても難しそうですね。解説pdf通りだと簡単です。丁寧な解説なのでここでは書きませんが上の方針を早めに捨てられていれば解けていたかもしれません。 modの式変形はどのような時に大変でどのような時は簡単なのか判別できる能力が必要と感じました。まずはmod式変形の勉強を進めていきたいです。