プログラム・プロムナード(7月号)
久々に情報学図書館に行ってきたので読んできた。
テスト勉強に行ったついでなので、キーワード拾ったぐらいなのだが。
今月の問題は
m本のコードの長さ(実数)が与えられて、
それらのコードから同じ長さをn本切り取るとき、
切り取れるコードの最長値はいくつか?
(0<=m,n<=1000)
時間が無かったので最後のほうしか読んでないけど、
の解法が書かれていたようである。
わからん…もうちょっと考えます
- 二分探索
0から長さの最大値までの間のどこかに切り取れる/切り取れないの
境界があるのだから、二分探索で解ける。
計算量は、切り取れるかどうかの判定はてきとうにやってもO(m)だから、
長さの最大値をlとするとO(mlogl)ぐらいか。
問題無さそうである。
これは思いついた人すごいなぁ。
選挙でおなじみの方式である。
最終的に当選候補者が同じ得票数で当選したとして
もっとも死票が少なくなる方法なのであるが、
この問題にも使える。
各コードの長さを政党の得票数と考え、
n人の当選者を出したとき、最後の候補者を選んだときの
値が答えになる。
計算量は、n回最大値を見つけるので、2分木を使うとO(nlogm)か。
馬鹿サーチでもO(mn)なので、大丈夫そうである。
