Google Code Jam Round1A

GCJ

出ました。

50ptで113位。よって無事通過したようです。

今回は慣れているC++での参戦。
流石にこれをHaskellで挑む自信は有りませんでした。
まあ1完で通るみたいなので、Haskellでやってても通ってたかもしれない。

Problem A. FreeCell Statistics

ゲームの勝率をつけていて、今日の勝率がExactlyにPD%、全体の勝率がExactlyにPG%です。
今日は多くてもN戦しかしていません。
さあ勝率につけ間違いはあるかという問題。

たとえば今日は1戦しかしてないのに、今日の勝率が20%とかだったら完全につけ間違いです。
また、今日の勝率が10%なのに、全体の勝率が100%だったらやっぱりつけ間違いです。
この２つを愚直に試すだけ。

実装する→submit→通る。

テンプレートはここを参照→http://d.hatena.ne.jp/y_mazun/20110515/1305446194

template<class T>
T gcd(T a, T b){
  if(a > b) swap(a, b);
  if(a == 0) return b;
  return gcd(b % a, a);
}

int main(){
  int c; cin>>c;

  REP(cc, c){
    ll n; cin>>n;
    int pd; cin>>pd;
    int pg; cin>>pg;

    int B = pd;
    int A = 100;
    bool ans = true;

    int tmp = gcd(A, B);
    A /= tmp; B /= tmp;
      
    if(A > n) ans = false;
    if((pg == 0 || pg == 100) && pd != pg)
      ans = false;

    printf("Case #%d: %s\n", cc+1, ans ? "Possible" : "Broken");
  }

  return 0;
}

Problem B. The Killer Word

何個かの文字列から１つ選んで、すべての文字を隠しておきます。
相手がこの文字は入っていますか？という質問をするので、入っていたらその文字をオープンする。
入っていなかったら相手は１点失う。
相手は基本的に決まった順番で質問する。
ただし相手は、ありえる文字列を全部知っているのでありえない質問はしない。
さて、相手の点数を最も失わせるにはどの文字列を選べばいいでしょうという問題。

という感じの問題。

最も愚直には、全部の文字列を選んだ場合にシミュレーションするというのが考えられる。
でも文字列が N=10000 個あって、相手の質問のケースが M=100 個ほどあるので(さらにテストケースが10個ある)
愚直すぎるシミュレーションだと大体O(M*N*N)になるのでちょっと無理そうなので、別の方法を考える。

しばらく考えた結果。現在の状態から取り得る文字列で分類していけば、O(N*M)くらいでできそう。
つまり例えば取り得る文字列が
acc bbb abb ccc
の場合に、相手が最初に a が入ってるか聞くとそれぞれ
a__ ___ a__ ___
になるので、
1: acc abb
2: bbb ccc
という具合に分類できる。
またこの時同グループでは、相手の失った点数が同じになるので、答えがわかる。
なお最初は文字列の長さで分類しておく。

実装してみる→バグではまる。
どうやら

vector<list<int> > g;
// なにかする
for(list<int>::iterator it = g[i].begin(); it != g[i].end(); ++it){
  // なにかする
  g.push_back(hoge);
}

のようなコードはダメのよう。
(終わってから聞いたところ、@yak_ex さんによると、vectorのpush_backはメモリ再確保の可能性があるので、中身のリストのiteratorが無効化されるらしい)

バグを取る→submit→Wrong Answer

なんだと・・・！？
問題を読み直す。
同じ点数になる場合は最初に出てきた文字列を答えにしろ、というのを実装してなかった。

実装→submit→通る。

上記のバグにハマったせいで、結構時間かかってしまった。
実装ももっと綺麗にかけた気がするのでちょっとびみょんな感じ。
多分、リストで分類を表すんじゃなくて、配列内のここからここまでみたいなので分類を現せば、再帰関数でもっと綺麗にかけたかな？

#include<list>

char words[10000][12];
int lens[10000];
int id[10000];
int memo[10000][30];

int main(){
  int ccc; scanf("%d", &ccc);
  REP(cc, ccc){
    int n, m;
    scanf("%d%d", &n, &m);

    printf("Case #%d:", cc+1);

    REP(i, n){
      scanf("%s", words[i]);
      lens[i] = strlen(words[i]);
    }

    for(char c = 'a'; c <= 'z'; c++){
      REP(i,n){
        int flag = 0;
        REP(j,lens[i]){
          if(words[i][j] == c){
            flag |= (1 << j);
          }
        }
        memo[i][c - 'a'] = flag;
      }
    }

    int idCnt_s = 0;
    {
      map<int, int> mm;
      REP(i,n){
        if(mm.count(lens[i]) == 0){
          mm[lens[i]] = idCnt_s++;
        }
        id[i] = mm[lens[i]];
      }
    }

    REP(k, m){
      char buff[30]; scanf("%s", buff);
      int que[26];   REP(i, 26) que[i] = buff[i] - 'a';
      int idCnt = idCnt_s;

      vector<pair<int, list<int> > > group(n);
      REP(i,n)
        group[id[i]].s.push_back(i);

      REP(i,26){
        char q = que[i];
        int ggg = idCnt;

	bool ok = true;
	REP(gg, ggg){
	  if(group[gg].s.size() != 1){
	    ok = false;
	    break;
	  }
	}
	if(ok) break;

        REP(gg, ggg){
          int point = group[gg].f;
          list<int> &s = group[gg].s;
          map<int, int> mapping;

          // printf("group %d(%d): ", gg, point); FOR(it, s) printf("%s ", words[*it]); puts("");

          if(s.size() == 1) continue;

          list<int>::iterator it = s.begin();
          mapping[memo[*it][q]] = gg;

          while(it != s.end()){
            int i = *it;
            int next;

            if(mapping.count(memo[i][q]) == 0){
              mapping[memo[i][q]] = idCnt;
              group[idCnt++].f = point + (memo[i][q] == 0 ? 1 : 0);
            }

            next = mapping[memo[i][q]];
            if(next != gg){
              group[next].s.push_back(i);
              it = s.erase(it);
            }else{
              ++it;
            }

          }

          if(mapping.size() != 1 && memo[*s.begin()][q] == 0)
            group[gg].f++;
        }
      }

      int maxpoint = 0;
      int maxid    = 0;
      REP(i, idCnt){
        if(maxpoint < group[i].f){
          maxpoint = group[i].f;
          maxid    = *group[i].s.begin();
        }else if(maxpoint == group[i].f){
	  maxid    = min(maxid, *group[i].s.begin());
	}
      }

      printf(" %s", words[maxid]);
    }
    puts("");
  }

  return 0;
}

Problem C. Pseudominion

手札とデッキがあって、それぞれのカードには

  • c 枚のカードをデッキから引く
  • s ポイント増える
  • t ターン分、残りターンが増える

というようなパラメータがある。

手札とデッキが与えられたときに、ポイントを最大にしなさい、という問題。

とりあえず、ターンが増えるカードは出得なので、出す。
というのはすぐに分かったのだが、そのあとの方針がたたない。
B問題で時間がかかったこともあり、ここでタイムアップ。

時間があるときにもう少し考えてみる。

(追記) Bを再帰で書いた

こっちのほうが圧倒的に読みやすそう

char words[10000][12];
int memo[10000][30];
pair<int,int> data[10000];

int que[26];

/*
 * [idx1, idx2)をグルーピングする
 * 次の文字はque[q]
 * 返り値は ポイントの最大値と、そのidxに-1をかけたもの
 * -1をかけることでmaxをとるだけでよくなる
 */
pair<int, int> solve(int idx1, int idx2, int q){
  pair<int,int> ret = mp(0, - 1 * data[idx1].s);

  if(idx1 + 1 == idx2) return ret;

  int query = que[q];

  for(int idx = idx1; idx < idx2; idx++)
    data[idx].f = memo[data[idx].s][query];

  sort(&data[idx1], &data[idx2]);

  if(data[idx1].f == data[idx2-1].f){
    ret = solve(idx1, idx2, q+1);
  }else{
    int lastIdx = idx1;
    for(int idx = idx1 + 1; idx <= idx2; idx++){
      if(idx == idx2 || data[idx].f != data[lastIdx].f){
	// [lastIdx, idx) が一つのグループ
	int add = lastIdx == idx1 ? data[idx1].f == 0 ? 1 : 0 : 0;
	pair<int, int> tmp = solve(lastIdx, idx, q + 1);
	tmp.f += add;
	ret = max(ret, tmp);
	lastIdx = idx;
      }
    }
  }

  return ret;
}

int main(){
  int t; scanf("%d", &t);
  REP(tt, t){
    int n, m;

    scanf("%d%d", &n, &m);
    REP(i, n) scanf("%s", words[i]);

    for(char c = 'a'; c <= 'z'; c++){
      REP(i,n){
        int flag = 0;
        REP(j,strlen(words[i])){
          if(words[i][j] == c){
            flag |= (1 << j);
          }
        }
        memo[i][c - 'a'] = flag;
      }
    }

    printf("Case #%d:", tt+1);

    REP(k, m){
      char buff[30]; scanf("%s", buff);

      pair<int,int> ret = mp(0, 0);

      REP(i,26) que[i] = buff[i] - 'a';

      REP(i,n){
        data[i].s = i;
        data[i].f = strlen(words[i]);
      }

      sort(&data[0], &data[n]);

      int lastIdx = 0;
      for(int idx = 1; idx <= n; idx++){
        if(idx == n || data[idx].f != data[lastIdx].f){
          // [lastIdx, idx) が一つのグループ
          pair<int, int> tmp = solve(lastIdx, idx, 0);
          ret = max(ret, tmp);
          lastIdx = idx;
        }
      }

      printf(" %s", words[-1 * ret.s]);
    }

    puts("");
  }

  return 0;
}