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;
}