519.1
1000に挑もうとしたら、出題されなくて、1000よりも難しい900が出題された...。
250
一ビットずつ操作して数を作ることを考えるとき、AからBまでの数を作らないといけないとして、途中経過で登場する最大の数を答えよ、という問題。操作の手順が与えられる。
キャリーが出たところで、全部立ててから下を潰すような処理らしいので、AとBで食い違ったところで適当にうまいことやりくりすれば良いらしい。
600
指定された文字列のうちのいくつかしか含まない文字列は何通りあるか答えよ、という問題。
順番に文字を後ろに足していくDPで解ける。今自分が指定された文字列のどの文字にマッチしているかと、どの文字列を既に含んでいるかを状態にする。最終的に、指定された数の文字列を含んでいるものすべてが答えになる。
