SRM 648

nico_shindannin（診断人） @nico_shindannin

もう少しでKitayutaMart通りそうだけど、なぜかN=K=1でTLEしてしまうのじゃ…。自分のPCだと、結果も正しいし、変なこともしてない気がするけど…

nico_shindannin（診断人） @nico_shindannin

やっと、KitayutaMartとおった。長い道のりだった。ちなみに、間違いは1<<(-1)ってやってるところがあった…これはあかんのじゃ。

nico_shindannin（診断人） @nico_shindannin

KitayutaMartの簡単な解説。まずN番目の小さい値が、2の累乗で区切った階段状の列の何列目に来るかを求める。階段列rに含まれている商品の数は2のr乗個、Kを超えるとK個ずつになるので、何列目に来るかは簡単に求められる。 pic.twitter.com/npqEuqp2zU

拡大

nico_shindannin（診断人） @nico_shindannin

今回やっかいなのは、列4以降のK個で区切られてしまうパターン。簡単にするために、列4以降はすべて列4に置き換えてかんがえてよい。なぜなら、列が増えても大小関係は変わらないから。

nico_shindannin（診断人） @nico_shindannin

あとは、列の中でx番目に小さい商品の価格が分かれば良い。これは直接求めるとTLEなので、二分探索で求める。商品の価格y以下の商品が何個あるかを計算するのも時間がかかるので、以下の2の累乗の倍数ごとに分けた、青枠ごとにまとめて数える。 pic.twitter.com/vwfExBoQ9w

拡大

nico_shindannin（診断人） @nico_shindannin

ただし、2の0乗の部分は、K以下の数しか使えないのは注意。例えば14以下の商品個数は 14/(2^2)-8/(2^2)+14/(2^1)-8/(2^1)+min(14,K)-8で求められる。そんなかんじじゃ。

nico_shindannin（診断人） @nico_shindannin

あ、xっていきなり出てきたけど、x=N-(含まれる列以前にでてきた商品の個数)なので、含まれる列さえ決まれば求めることができます。

nico_shindannin（診断人） @nico_shindannin

あとは、事務だけじゃ。

いしかど @ISIKADO

SRM648のmed通した。2回もシステムテストで落ちてつらい。

いしかど @ISIKADO

考えるの少し時間かかる系のやつだけど、それでも提出数少ない気がする？