問題 atcoder.jp 解き方 木構造で何かしらの最大を求める問題は木dpっぽさを感じたので、この方針で突っ込んだ。 自分の子が持つべき情報は、何冊もらった時にどれだけのやる気を得ることができるかのテーブル。 この情報があれば、普通のdpの遷移と同じよう…

問題 atcoder.jp 解法 「同じ硬貨を使わない」というのを「同じ桁が同時に非零にならない」と読み替える。つまりY - X = Z (Y : 支払い、Z : お釣り) だと考えた時に、a0 < a1 < ... < a(n-1) かつ a(i+1) % ai = 0が成り立ってるので、各硬貨の使用枚数の上…

問題 atcoder.jp 解き方 偶奇のみに注目すればよく、mod 2 で考える。 与えられた漸化式によって出来る bit 列は、初めの長さ m のビット列さえ決まれば一意に定まるので、m bit分のパターンに注目すれば良さそう。 0と1しか取らないので、各位置をスタート…