AtCoder Beginner Contest 356
2完 AB
place: 6464th
pref: 595
意外と低くなかったappbird.icon
この順位だともっとpref下がると思ってたんだけどな
https://scrapbox.io/files/666493556a6a44001d38a67b.png
なんこれ!?
これが思いつけないのは相当疲れている
こっちに逃げて解いていた
いけそうだったのに〜〜〜
$ N = 2^iだったら楽
$ k = 0, 2^0の計算結果を出す
$ k\in \lbrack0, 2^0)の計算結果を使って$ k \in \lbrack 2^1, 2^2)の和を一気に出す
$ k\in \lbrack0, 2^2)の計算結果を使って$ k \in \lbrack 2^2, 2^3)の和を一気に出す
$ k\in \lbrack0, 2^3)の計算結果を使って$ k \in \lbrack 2^3, 2^4)の和を一気に出す
$ k\in \lbrack0, 2^4)の計算結果を使って$ k \in \lbrack 2^4, 2^5)の和を一気に出す
$ \vdots
というように計算できる
問題は、$ Nが2の累乗じゃなかった時にどう計算するか $ k = \lbrack 0, N \rbrackの結果は
$ \lbrack 0, f(N))で求められる
$ \lbrack f(N), N)の範囲は...。
やり直そうとしても頭が働かず問題を理解できなかったので、CDを解き直すことは諦めた