Good Bye 2019 - D. Strange Device
概要
ある機械を買った。その機械には長さnの、各項が相異なる自然数列が存在する。この機械は、k個の相異なる、[1, n]の数字を入れて、それをaの添え字としたとき、それのk個のaの要素のうち、小さい方から見てm番目の添え字と値を出力する。
ところで、aとmをあなたは忘れてしまいました。知ってるのはnとkだけです。機械の電気代がすごく高いので、最大n回の機械への質問(k個の相異なる、[1, n]の数字を入れる)で、mを突き止めてください。
制約： 1 <= n, k <= 500, aの要素の値は10^9以下の非負の整数
ACするまで
この文章の、「端」、「真ん中」は考察を見てください。
1. aをソートしても、本質的には問題ないので、aが仮に昇順に並んでるとして考える。
2. 頑張って質問しても、真ん中のn-k+1個の数字しかわかりえない。m-1番目までの数字とかはどうあがいてもわからない。
3. ひとまず真ん中のn-k+1個の数字を調べるー＞いい感じに質問することで、n-k+1回の質問で特定できる。
4. これで残りk-1回の質問になる。そして、両端には合計k-1個の値がまだわからない。
5. わからないk-1個の値を質問列に入れてみると考えると、足りない1つを真ん中に相当する数字にする。そうすると、質問の結果は当然真ん中に相当する数字になる。
6. ここから、真ん中の数字を2つにして、わからないk-1個の値から1つ消すと考えると、質問の結果は真ん中の2つのどれかになり、どれになるかによって上か下かが定まる。
7. これをk-1個の数字、それぞれを落として考えてみることでちょうどk-1回の質問となり、(n-k+1)+(k-1)=n回の質問でちょうど終わる。
考察
僕の解法と公式解法、両方について書く。僕の解法をさらに煮詰めると公式解法になる。
僕の解法
インタラクティブは、質問queryを少しずつ変えることで、その差分から答えを探すのが常套手段。
今回、小さい方からm-1個を「下」として、大きい方からk-m個を「上」ということにする。この2つの区間に入ってる値は、原理的にどう質問しようが求まらない。
その下と上に挟まれてる、n-k+1個の値からなる区間を「真ん中」という。この真ん中の区間の値は、適切な質問をすることで求まる。
今回の場合は、k個の値を選び、m番目とされてる番号以外をそのまま、もう1つ未知の値を入れて質問しなおすことで、再びその時点でのm番目の値と添え字が分かる。この操作は、n-k+1回まで行うことができて、一回m番目になった値は除外されるので、結果的には、理論的に求まるとされるn-k+1個の真ん中に位置するすべての値がわかる。
この時、残るk-1個の値で、どれが上かどれが下かを判断する必要がある。
こういうときに、典型テクニックとして、求めたいものだけを抜くことによっての結果で判断がある。1つだけ抜くことによって、ありうる結果はたかだか定数個になり、結果がなにになるかは予測できる場合がある。その結果次第で判断できるというのが、今回の問題。
今回の場合、上or下のk-1個から1つ抜いて、真ん中から2つ(大きい方をb, 小さい方をsとする)入れて質問すると、ありうる答えとしては、
- 上の入ってる要素を抜いたのならば、m番目はsとなる。(下の要素は相変わらずm-1個入ってるため)
- 下の入ってる要素を抜いたのならば、m番目はbとなる。(下の要素は1つ減りm-2個になり、そこでm-1番目がsになった)
のたかだか2つしかない。
よって、これをk-1個の上or下の候補に対して試せば、上と下のそれぞれの数が分かる。これに質問はk-1回かかる。
最後に、(n-k+1)+(k-1)=n回なので、ピッタリでこの問題は解けた。
解説解法
僕の解法の後半部分の考察で、「求めたいものだけを抜くことによっての結果で判断」の考えでさらに詰める。
結果はたかだ定数個になることに着目する。
ひとまず適当なk+1個の添え字を選び、それらから1つ落としを質問することk+1回、すると帰ってくる結果は、
k+1のうち、昇順の並び、(m-1個)(m番目)(m+1番目)(k-m個)で考えると、
- m-1個のうちの1つ、m番目を落とした時にはm+1番目が答えになる。
- m+1番目、k-m個のうちの1を落とした時には、m番目が答えとなる。
よって、k+1回質問をすると、m+1番目が答えになってる回数自体がmの値となる。
この方法では、k+1回の質問だけで済む。
一言
想定解法、頭いいなぁ。一本取られた。
