またパスワードを忘れてしまいました!私はコンピュータの前に座って間違ったパスワードを打ち込んでいます。覚えているのは、パスワードが英小文字のみからなるということだけです。幸いなことに、ログインシステムは単に「パスワードが違います」と返すだけではありません。入力した文字列の接頭辞のうち、パスワードの(連続するとは限らない)部分列として現れる最長のものの長さも教えてくれます。形式的には、パスワード $P = p_1 p_2 \dots p_N$ と入力 $Q = q_1 q_2 \dots q_N$ に対し、ログインシステムの返答は、すべての $1 \le i \le L$ について $q_i = p_{k_i}$ を満たす添字 $1 \le k_1 < k_2 < \dots < k_L \le N$ が存在する最大の $L$ です。またシステムは、パスワードの長さ $N$ と、パスワードがアルファベットの先頭 $S$ 文字のみを使用することを意味する $S$ も教えてくれます。たとえば、$S = 4$ はパスワードが $\text{a}$, $\text{b}$, $\text{c}$, $\text{d}$ のみを含む(ただしすべてを含むとは限らない)ことを意味します。
私のパスワードを復元するのを手伝ってください!
実装の詳細
この問題はインタラクティブ問題です。以下の関数を実装してください。
C: char* guess(int n, int s);
C++: string guess(int n, int s);
- 引数:上で説明した通りの $N$ と $S$。
- 戻り値:正しいパスワード。
あなたのプログラムは以下の関数を呼び出すことができます。
C: int query(char* str);
C++: int query(string str);
- 引数:アルファベットの先頭 $S$ 文字からなる、長さ $1$ 以上 $N$ 以下の文字列。
- 戻り値:$0$ 以上
strの長さ以下の整数であり、クエリに対するログインシステムの返答を表す。 - コンパイルエラーを避けるため、この関数を呼び出す前に、グローバルスコープの任意の場所で上記のテキストと完全に一致する形で関数を宣言してください。
- 各テストケースにつき、この関数は最大 $50\,000$ 回まで呼び出すことができます。
プログラム内で追加の関数を定義しても構いません。
サンプルグレーダ
ローカルでコードをテストできるように、サンプルの grader.{c,cpp} が提供されています。サンプルグレーダはファイル password.in から以下の形式で入力を読み込みます。
- $1$ 行目:$N$ $S$
- $2$ 行目:パスワード
グレーダをあなたの解答プログラムと一緒にコンパイルし、生成された実行ファイルを実行することで、与えられた入力に対して推測戦略をテストすることができます。
小課題
テストケースはグループごとに採点される場合があります。小課題は以下の通りです。
| 小課題 | 配点の割合 | 入力の制約 |
|---|---|---|
| 1 | 10% | $N \le S \le 26$;パスワードに含まれる文字はすべて相異なる |
| 2 | 20% | $2 \le N \le 100$ かつ $2 \le S \le 4$ |
| 3 | 20% | $2 \le N \le 2\,000$ かつ $2 \le S \le 20$ |
| 4 | 30% | $2 \le N \le 3\,500$ |
| 5 | 20% | $2 \le N \le 5\,000$ |
入出力例
パスワードを $\text{aab}$ とします。グレーダは guess(3, 2) を呼び出します。呼び出し履歴は以下のようになり得ます。
| 呼び出し | 戻り値 |
|---|---|
guess("ab") |
2 |
guess("abb") |
2 |
guess("bab") |
1 |
guess("aab") |
3 |
この時点で、guess(3, 2) は "aab" を返す必要があります。