GCJ 2018 round1 C - A Whole New Word
問題ページ Google Code Jam
考えたこと
- 全ての可能な単語パターンは何通りか
- i文字目の文字種をc[i]とするとc[i]の総積になる
- nがこれに等しければ何をつくっても一致するので不可能
- とりあえず適当にケースをつくってみる
- j文字目が全て同じ文字→j文字目を異なるものにできない
- j文字目に異なる文字が含まれるのが1列だけ→新たな単語をつくることはできない
ABC ABD ABE
- 何か実験してると1文字交換して不可能で2文字交換するとできるみたいなパターンがなさそう
- 1文字置換ならば全探索してもO(N^2LlogN)くらいになりそう
- 全ケース最悪なパターンが来るとちょっと怪しい気持ちになる
- 答えが見つかったタイミングで終了してるから最悪になるケースはそんななさそう
- 単語iに単語jの文字を移したとしても新たな単語が作れないときを考えるとAAAA,AAAB,AAAC,AAAD,…,AAAZみたいな感じでそんなに個数がなさそう
- 何とかなりそうなので出すと通った
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int testcase; cin >> testcase; REP(tes, testcase) { int h, w; cin >> h >> w; vector<string> s(h); REP(i, h) cin >> s[i]; set<string> st; REP(i, h) st.insert(s[i]); string ans = "-"; REP(i, h) REP(j, h) { if(i == j) continue; REP(k, w) { if(s[i][k] != s[j][k]) { string tmp = s[i]; tmp[k] = s[j][k]; if(st.find(tmp) == st.end()) { ans = tmp; goto end; } } } } end:; cout << "Case #" << tes+1 << ": " << ans << endl; } return 0; }