コンテスト: https://hoj.hamako-ths.ed.jp/onlinejudge/contest/106/problems/5
アーカイブ: https://hoj.hamako-ths.ed.jp/onlinejudge/problems/832
解説
https://hoj.hamako-ths.ed.jp/onlinejudge/state/25987
大切な考察が一つある。
「可能性のある文字列は10^32個ほどしか無い」
最大ケースのN=26で考えてみると、これは26!通りの文字列しか無く、26!=6*10^32くらいである。
これは二分探索できそうな感じがある。
リアクティブ問題は大体二分探索なので、上手く二分探索できる所を探してみよう。
あとは、可能性のある文字列を上手く二分探索できる形に落とす所であるが、以下のように数と文字列を対応させる。
N = 3のとき 0 : abc 1 : abd 2 : abe ... 23 : abz 24 : acb
このように可能性のある文字列を全て辞書順で並べた時の順番を数と対応させることにする。
これで質問するときの大小関係と数の大小関係が一致し、二分探索できる。
あとは、部分問題として数からそれに対応する文字列を得られれば後はやるだけになる。
[部分問題] 数に対応する文字列を得る(convert関数)
先頭から順に文字を決めていくことを考える。
これは辞書順最小の文字列をDPから復元する時のテクとかと同様である。
N=3を例とする。
この時、先頭をaとした場合は後ろの2つの組み合わせはP(26-1,2)通りある。
そのため、nがP(26-1,2)未満であれば、「a__」のパターンの中にあるということになり、aが確定する。
そうでないなら、a__のパターンではないということなので、次の文字を考える。
このとき、a__のパターン数をnから引いておく。
このように先頭からn番目を逐次更新しながら、目的の文字列を目指していく。
あと、注意するべきなのが、同じ文字は使えないので、文字を使ったかのフラグを用意しておき、使ってない文字の先頭からj番目を使うようにしておく。
typedef __int128 ll; int N; //--------------------------------------------------------------------------------------------------- ll aPb(int a, int b) { if (b < 0 || a < b) return 0; ll res = 1; rep(i, 0, b) res *= a - i; return res; } //--------------------------------------------------------------------------------------------------- string convert(ll n) { string res = ""; string alp = "abcdefghijklmnopqrstuvwxyz"; vector<int> used(26, 0); rep(i, 0, N) rep(j, 0, 26 - i) { if (aPb(26 - i - 1, N - i - 1) <= n) n -= aPb(26 - i - 1, N - i - 1); else { int idx = 0; while (used[idx]) idx++; rep(k, 0, j) { idx++; while (used[idx]) idx++; } res += alp[idx]; used[idx] = 1; break; } } return res; } //--------------------------------------------------------------------------------------------------- string ask(string s) { printf("%s\n", s.c_str()); fflush(stdout); string res; cin >> res; return res; } //--------------------------------------------------------------------------------------------------- // < 0 : x < ans // = 0 : x == ans // > 0 : x > ans int query(ll x) { string s = convert(x); string res = ask(s); if (res == "less") return 1; else if (res == "greater") return -1; return 0; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; ll ok = 0, ng = aPb(26, N); while (ok + 1 != ng) { ll x = (ok + ng) / 2; int q = query(x); if (q == 0) return; if (0 < q) ng = x; else ok = x; } query(ok); }
