/ 
Time Limit: 0 msec / Memory Limit: 64 MB
時は 0x2012 年、人権思想は急速に拡大し、きつねにもプログラミングコンテスト参加の権利が与えられていました(これまでは出題の権利しかありませんでした)。さてこれは、アルゴリズマーきつねである次郎がプログラミングコンテストの世界大会へ挑むお話です。
競技が開始し、次郎はすぐさま問題に取り組み始めました。世界レベルの大会とはいえ、今や世界屈指のアルゴリズマーとして名を馳せる次郎に解けない問題はありません。コンテスト時間を残り 2 時間ほど残してすべての問題を解き終えた次郎は、ある 1 つの問題だけ異様に時間制限が長くデータが大きいことに気づきました。
もちろん、次郎の書いたプログラムは巨大なデータに対しても制限時間内に答を出すことは可能です。しかしここで次郎はひとつの可能性に思い当たりました。 6199 年前、つまり 0x7db 年にタイで開催された国際情報オリンピックでも、1 つの問題だけ時間制限が長いということがありました。実はこれは、この問題で最も高速に正答を出すプログラムに特別賞を与えるという目的があり、そのことは閉会式まで伏せられていたのでした。
次郎はひょっとしたらこの問題もそういう特別賞があるのかもしれないと考え、プログラムの高速化を始めました。しかし、少しの無駄を省くとかちょっとした改善策はすぐに尽き、何らかの大幅な高速化が必要になりました。そこで次郎はプログラム中の探索部分に嘘の枝刈りを仕込むことにしました。
この枝刈りの基準を決めるのはひとつのパラメータ X です。X が小さいほど枝刈りは緩やかに行われ、大きいほど大幅に枝が刈られます。もちろんこの枝刈りは嘘なので、あまり X を大きくしすぎると Wrong Answer になってしまう恐れがあります。具体的には閾値 T が決まっており、X ≧ T が成立するときには Wrong Answer となり X ＜ T が成立するときには Accepted となります。次郎はとうぜん T の値を知りません。
ところで次郎は彼自身のポリシーとして、「Wrong Answerの少ない戦い方」を常に心がけています。なので、できれば Wrong Answer になるような X の設定をすることなく T の値を知りたいのですが、時間は 2 時間しか残されていません。あまりにたくさん X の値を変えながら提出をして結果を確かめている暇はないということです。
さて、Wrong Answer の回数を抑えつつ、できるだけ少ない提出回数で T の値を決定するにはどのような戦略をとればよいでしょうか。
課題
整数 T がある。T は 0 以上 M 以下の整数であることが分かっているが、具体的な値は分かっていない。以下の質問を繰り返すことで T の値を求めたい。
- ある整数 X について 「X ≧ T が成立するか？」を質問する
できるだけ質問の回数を少なくして T を特定することを考える。ただし次のような制約がつく: 質問の返答が「Yes」になるような質問を N 回行うと、これ以上何の質問もできない。
次のパラメータをもつプロシージャ getT(N, M) を実装せよ:
- N -- 返答が「Yes」になるような質問を行える回数。
- M -- T の上限を表す整数。
getT(N, M) 内では compare(X) を繰り返し呼び出すことができる。compare(X) の仕様は次の通り。
- X -- T 比較する対象の整数。0 ≦ X ≦ M でなければならない。
- 戻り値は質問に対する返答が「Yes」である(すなわち X ≧ T が成立する)ことを表す 1 か「No」である(すなわち X ＜ T が成立する)ことを表す 0 のいずれかである。
getT(N, M) は質問を繰り返し、隠された T の値を特定し、その T の値を戻り値として返す必要がある。ただし compare(X) を呼び出したときの戻り値が 1 であるということが N 回起こった場合、それ以降は 1 回も compare(X) を呼び出してはならない。
例
例1
N = 1, M = 4 の場合を考える。
この場合、たとえば次のような戦略で T を決定することができる。compare を次のようなパラメータで呼び出し、以下に示すような返答を得たとする。
| パラメータ | 戻り値 |
|---|---|
| compare(1) | 0 |
| compare(2) | 0 |
| compare(3) | 1 |
このとき 2 ＜ T かつ 3 ≧ T であることから T = 3 がわかる。したがって getT は 3 を返す必要がある。
例2
N = 2, M = 8 の場合を考える。
この場合、次のような戦略で T を決定することができる。compare を次のようなパラメータで呼び出し、以下に示すような返答を得たとする。
| パラメータ | 戻り値 |
|---|---|
| compare(4) | 1 |
| compare(1) | 0 |
| compare(2) | 0 |
| compare(3) | 1 |
このとき 2 ＜ T かつ 3 ≧ T であることから T = 3 がわかる。したがって getT は 3 を返す必要がある。
小課題
小課題 1 (25 点)
- N = 1
- 1 ≦ M ≦ 100 000
- getT(N, M) は compare(X) を許される限り何度呼び出しても構わない。
小課題 2 (25 点)
- N = 2
- 1 ≦ M ≦ 1 000 000
- getT(N, M) が compare(X) を呼び出す回数は 40 000 回以下でなければならない。
小課題 3 (最大で 50 点)
- 3 ≦ N ≦ 50
- 1 ≦ M ≦ 1 000 000 000 000
- 重要: この小課題の得点は compare(X) が呼び出された回数によって決まる。
この小課題のテストケース (N, M) に対して、次のように値 P(N, M) を定める。まず、w を wN ≧ M * N! を満たす最小の正の整数とし、W = w + N とする。ただし N! は N の階乗である。
- getT(N, M) が compare(X) を呼び出す回数が W 回以下であれば P(N, M) = 50
- α を 0 ＜ α ＜ 1 かつ getT(N, M) が compare(X) を呼び出す回数が 2W-αW 回以下となる最大の実数とすると P(N, M) = 50α
- getT(N, M) が compare(X) を呼び出す回数が 2W 回以上であれば P(N, M) = 0
実装の詳細
制限
- CPU 時間制限: 5 秒
- メモリ制限: 64 MB
注意: スタックのサイズには決められた制限はない。スタックとして使用されたメモリは、メモリ総使用量に含まれる。
インターフェース (API)
- 実装フォルダ: submission/ (プロトタイプ: submission.zip)
- 競技者が実装するファイル: submission.cpp
- 提出ファイルのインターフェース: submission.h
- 採点プログラムのインターフェース: grader.h
- 採点プログラムのサンプル: grader.cpp
- 採点プログラムの入力のサンプル: grader.in.1, grader.in.2, ...
注意:採点プログラムのサンプルは次の書式の入力を読み込む。- 1 行目: N, M, T が空白区切りで書かれている。
- 採点プログラムの出力
注意:採点プログラムは入力に対して、標準出力に次のような出力を行う。- getT(N, M) が誤った答を返した場合 "NG" と書かれた行を出力する。
- N = 1 に対し正しい実装がなされていれば "OK 1" と書かれた行を出力する。
- N = 2 に対し正しい実装がなされていれば "OK 2" と書かれた行を出力する。
- N ≧ 3 に対し正しい実装がなされていれば "OK 3 P" と書かれた行を出力する。ただし P は入力に対して採点基準にしたがって計算された P(N, M) の値である。
- Problem Proposal: qnighy
- Problem Statement: JAPLJ