問題
Dashboard - Qualification Round 2016 - Google Code Jam
'G', 'L' のみで構成された長さ K の文字列 original を C 回操作する。
文字列 s を操作するときは,
- 'G' -> K 個の 'G' が連なったものに変換
- 'L' -> original に変換
と操作する(なので C 回操作すると K^C 文字の文字列になる)。
今, C 回操作した後の文字列のある地点 s[index] を最高 S 回だけ調べることが出来る。最初の文字列がどのような文字列であっても, original に少なくともひとつの 'G' があったかを判定できるか。
判定できる場合は, 調べるべき index のリストを返す。
解法
実は一回の調査で original の C 個の文字を調べることが出来ます。
というのは,
- i*K^(C-1) -> i 番目の文字がわかる
- a*K^(C-1) + j*K^(C-2) -> j 番目の文字がわかる(a は任意の整数)
...
となっているので, 例えば 0, 1, 2, ..., C-1 文字目がそれぞれどうなっているのかを調べたければ,
0*K^(C-1) + 1*K^(C-2) + 2*K^(C-3) + ... + (C-1)*1 番目の index を調べれば良いです。
イメージとしては, K 分木で,
- 頂点が 'G' -> それ以下の頂点は全部 'G'
- 頂点が 'L' -> 下に original が続く
というのを考えるとわかりやすいかもしれません。
void solve(int K, int C, int S) { if (C*S < K) { cout << "IMPOSSIBLE" << endl; return; } vector<ll> ans; for (int i = 0; i < K; i += C) { ll t = 0; for (int j = 0; j < C; j++) { if (i+j >= K) break; t = t*K+(i+j); } ans.push_back(t+1); } int sz = ans.size(); for (int i = 0; i < sz; i++) { cout << ans[i]; if (i < sz-1) cout << " "; } cout << endl; } int main() { cin.tie(0); ios::sync_with_stdio(false); int T; cin >> T; for (int t = 1; t <= T; t++) { int K, C, S; cin >> K >> C >> S; cout << "Case #" << t << ": " ; solve(K, C, S); } return 0; }