いよいよ待ちに待った「国際情報オリンピック日本代表プログラミングコンテスト」(IJPC : IOIer Japan Programming Contest)の開催だ。2010年にカナダ、2011年にタイで開催された国際情報オリンピック(IOI)に日本代表として出場した 計 5 人が問題を作るプログラミングコンテストであり、5 時間で 3 問の問題を解くという IOI に似た形式である。

IJPC の参加者への感謝の意を表するとともに、IJPC を盛り上げるために巨大な垂れ幕を作ろう。出来るだけ大きく目立つものにしたいところではあるが、あまり垂れ幕作りに時間をかけすぎると肝心の大会問題の準備時間を削ってしまうことになる。つまり、手間を省きつつ大きな垂れ幕を作りたい。

ところで手元には都合のよいことに、何に使われたのかわからない巨大な垂れ幕がある。この垂れ幕は非常に長く、もとから何かの文字列が書かれている。このままでは当然 IJPC 用の垂れ幕として使うことはできないが、少しだけ修正してこれを IJPC 用に使えないだろうか?

もとから書かれている文字列に "IJPC" という文字列が含まれていればうれしいのだが、さすがにそう都合よくはいかないだろう。ある程度の文字を書き換える必要があるはずだが、文字を書き換える作業は垂れ幕が大きいこともありとても時間がかかる。さて、ここでプログラムの出番だ。できるだけ少ない書き換え回数でこの垂れ幕を使えるようにする方法を求めよう。

英大文字からなる N 文字の文字列 S がある。S のある位置の文字を別の文字に書き換える操作を繰り返し、S の部分文字列に "IJPC" という 4 文字が現れるようにしたい。ここである文字列から 0 文字以上の任意の文字を削除して得られるような文字列を、元の文字列の部分文字列と呼ぶ。

次のパラメータをもつプロシージャ replace(N, S) を実装せよ:

• N -- 与えられる文字列の文字数。N ≧ 4 を仮定してよい。
• S -- 英大文字からなる文字列。S は N 文字であると仮定してよい。

replace(N, S) は S の部分文字列に "IJPC" が現れるようにするために必要な最小の書き換え回数を戻り値として返す必要がある。

N = 8, S = "IAMJAPLJ" の場合を考える。

この場合、S の 7 文字目または 8 文字目のどちらかを文字 'C' に書き換えることで S の部分文字列に "IJPC" が現れるようにすることができる。したがって replace(N, S) は 1 を返す必要がある。

N = 28, S = "IOIERJAPANPROGRAMMINGCONTEST" の場合を考える。

この場合 S はもとから "IJPC" を部分文字列として含んでいるため、書き換えを行う必要はない。したがって replace(N, S) は 0 を返す必要がある。

きつねの太郎と次郎はPrime Hazardというコンピューターゲームで遊んでいる。

Prime Hazardに登場するキャラクターには2以上の整数が書かれていて、素数が書かれたキャラクターはプレイヤーの仲間であり、合成数が書かれたキャラクターはプレイヤーの敵である。

プレイヤーはキャラクターに書かれた数字を見て、瞬時に敵か仲間かを判断し敵だけを攻撃しなくてはならない。敵は書かれている数字の最小の素因数を入力することで倒すことができる。

太郎と次郎はこのゲームをプレイする際に次のような役割分担をすることにした。

• 太郎は敵の数字を読んでその情報を次郎に伝える。
• 次郎は太郎からの情報を元に、キャラクターが敵かどうか、敵であれば最小の素因数は何かを判断する。

一度に大量のキャラクターについて処理しなくてはならないため、情報の伝達はできるだけ簡単にしたい。太郎は次郎に0か1の数字をいくつか伝えることにした。

2以上の正整数Nが与えられる。Nが素数か判定せよ。合成数の場合は最小の素因数を求めよ。

次のプロシージャを実装せよ:

• 次のパラメータを持つプロシージャ taro(N):
  • N -- 与えられた正整数。
  このプロシージャ中で send(b) を繰り返し呼び出すことで次郎にデータを送信することが可能である。ただし b は 0 または 1 でなければならない。このプロシージャは jiro(S, X) よりも先に1度だけ呼び出され、戻り値を持たない。
• 次のパラメータを持つプロシージャ jiro(S, X):
  • S -- 太郎から送られてきたデータの長さ(ビット数)。
  • X -- S 個の整数からなる1次元配列。0 ≦ i ＜ S に対して X[i] は taro(N) 中で send(b) が i+1 回目に呼び出された際の b の値に等しい。
  このプロシージャは taro(N) が呼び出された後に1度だけ呼び出される。このプロシージャはNが素数である場合は -1, 合成数の場合は最小の素因数を戻り値として返す必要がある。

N = 7

の場合を考える。

taro 中で send が次のように呼び出されたとする。

このとき jiro 呼び出しにおいて S = 4 であり、

となる。

この場合、7 は素数であるので、jiro は -1 を返さなければならない。

N = 6

の場合を考える。

この場合、6 は合成数であり、最小の素因数は 2 であるので、 jiro は 2 を返さなければならない。

時は 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) を呼び出してはならない。

N = 1, M = 4 の場合を考える。

この場合、たとえば次のような戦略で T を決定することができる。compare を次のようなパラメータで呼び出し、以下に示すような返答を得たとする。

このとき 2 ＜ T かつ 3 ≧ T であることから T = 3 がわかる。したがって getT は 3 を返す必要がある。

N = 2, M = 8 の場合を考える。

この場合、次のような戦略で T を決定することができる。compare を次のようなパラメータで呼び出し、以下に示すような返答を得たとする。

このとき 2 ＜ T かつ 3 ≧ T であることから T = 3 がわかる。したがって getT は 3 を返す必要がある。

統計において、データの散らばり度合いを表す数である分散について説明しよう。

数列a[1], a[2], …, a[n]があるとき、

• a[1]からa[n]までの合計をnで割ったものが平均mである。
• それぞれのa[k]について、mとの差の二乗を計算し、その合計値をnで割ったものが分散(σ^2)である。

数列上のある区間の分散を計算したい。

ここに数列 A[0], A[1], ... A[N-1]がある。最初に init(N, A) によって A の初期値が与えられる。

次のプロシージャを実装せよ:

• 次のパラメータを持つプロシージャ init(N, A):
  • N -- 数列の長さ。数列の各項には 0 から N-1 までの異なる整数の番号がつけられている。
  • A -- 数列の各項を表す整数の配列。0 ≦ i ＜ N に対し 1 ≦ A[i] ≦ 10 000 を仮定してよい。
  このプロシージャは最初に update(i, x) または variance(i, j) が呼び出される前に1度だけ呼び出される。このプロシージャは戻り値を持たない。
• 次のパラメータを持つプロシージャ update(i, x):
  • i -- 値が変化する数列の項の番号。0 ≦ i ＜ N を仮定してよい。
  • x -- 値が変化した後の i 番目の項の値。0 ≦ x ≦ 10 000 を仮定してよい。
  このプロシージャは複数回呼び出される。1回の呼び出しは1回の数列の値の変化に対応する。このプロシージャは戻り値を持たない。
• 次のパラメータを持つプロシージャ variance(i, j):
  • i -- 分散を計算したい区間のはじめの項の番号。 0 ≦ i ＜ N を仮定してよい。
  • j -- 分散を計算したい区間の最後の項の番号。 i ≦ j ＜ N を仮定してよい。
  このプロシージャは複数回呼び出される。それぞれの呼び出しに大して i 番目の項から j 番目の項(両端も含む)までの(j - i + 1)個の値を母集団としたときの分散を戻り値として返す必要がある。小数点以下の値は切り捨てて整数値にして返すこと。

N = 3, A[i] の初期値が

の場合を考える。

最初、プロシージャ init は上記のパラメータで呼び出される。その後、複数回の update または variance の呼び出しが任意の順番で行われる。以下に呼び出しと正しい戻り値の例を示す: