Google Code Jam 2013 Qualification Round - Darseinのプロコン日記

A,B,C,Dsmallを解きました。

A. Tic-Tac-Toe-Tomek

　所謂四目並べの盤面が与えられるので、勝・敗・引き分け、あるいはまだ進行中かを答える問題。

解法：

　さすがにやるだけ。
　縦・横・対角のX,O,Tの数をカウントして、X(or O)が4つ、または3つ + Tが1つなら勝敗がわかる。
　勝敗がついてないときは、'.'が盤面にひとつでもあれば進行中、なければ引き分け。
　文字のカウントは'.'も入ってめんどくさかったのでmapを使った。1ケースあたりO(10*4*log4)
　例えば横を調べるときは以下のような感じ。

  for(int i=0;i<4;i++){
    map<char,int> cnt;
    for(int j=0;j<4;j++)cnt[board[i][j]]++;
    if(cnt['X']==4 || (cnt['X']==3 && cnt['T']==1))ans = "X won";
    if(cnt['O']==4 || (cnt['O']==3 && cnt['T']==1))ans = "O won";
  }

　smallとlargeの違いはテストケース数だけなのでそのままやればlargeも通る。

B. Lawnmower

　N×Mの芝生があり、初期状態ではすべて長さ100である。
　縦もしくは横一列を一斉に任意の長さに変える操作が可能である。
　この操作を好きなだけ繰り返せるとき、指定した芝生の状態を作れるかを問う問題。

　制約：small 1≦N,M≦10, 1≦a[i][j]≦2
　　　　large 1≦N,M≦100, 1≦a[i][j]≦100

解法：

　これ(AOJ 1079)を思い出して逆順シミュレーションすればよいと気付く。
　すなわち、与えられた芝生の状態からすべて長さ100の状態に戻せるか、を考えればよい。
　そうすると、与えられた芝生の中で一番短い芝生は、最後に刈られていることになる。
　ということは、その縦、もしくは横一列の全ての芝生もまた、最も短い芝生と同じ長さでなければいけないことになる。
　よってこの条件を満たし続けるように復元していけばよい。
　(一度復元したところはそのときどんな長さでもよいので適当にドントケアにしておく)
　1つのテストケースあたりO(N*M*(N+M))。
　きっちり復元を再現しなくてもよいらしい。(こちらを参照)

　smallだけ解けるような解法が思いつかなくてほげ。

C. Fair and Square

　自身が回文数(=文字列とみなしたときに回文になっている)、かつ、自身の平方根も回文になっている数をFair and Squareであるという。
　区間[A,B]中に存在するFair and Squareの数を求めよ。便宜上制約を1≦A≦B≦Nとする。

　制約：small N=1000
　　　　large-1 N=10^14
　　　　large-2 N=10^100

small解法：

　ナイーブに調べればよい。AからBまでループを回して、自身が回文数ならその平方根を求め、平方根が整数ならそれが回文数か調べる。以下のようなコードでよいと思われ。

for(int i=A;i<=B;i++){
  if(isPalindrome(i)){
    int a = sqrt(i);
    if(i == a*a && isPalindrome(a))ans++;
  }
}

問題はisPalindromeの実装だが、stringstreamとか使って文字列にしてやるのがたぶん一番楽。

bool isPalindrome(int x){
  stringstream ss; ss << x;
  string s = ss.str();
  for(int i=0;i<s.size();i++){
    if(s[i] != s[s.size()-1-i])return false;
  }
  return true;
}

O(N*log_10 N)なのでsmallは余裕。

large-1解法

　このままだとO(10^14*14)になって死亡するが、ちょっと発想を変えればいける。
　逆にAが回文数のとき、A^2が回文数ならA^2はFair and Squareである。
　ということで、N^(1/2)まで回文数チェックを行い、その二乗を求めてそれが回文数なら答えに追加すればよい。
　ちなみに、smallも含めて答えを列挙してあとから(二分or線形)探索する方が効率的である。

#define all(a) (a).begin(),(a).end()

vector<long long> fs; //Fair and Square Numbers
for(long long i=1;i<=10000000;i++){
  if(isPalindrome(i)){
    if(isPalindrome(i*i))fs.push_back(i*i);
  }
}

for(int i=0;i<TestCase;i++){
  cin >> a >> b;
  int ans = upper_bound(all(fs),b) - lower_bound(all(fs),a);
  cout << "Case #" << i+1 << ": " << ans << endl;
}

large-1のサイズならO(7*10^7 + T*log|fs|)程度なので間に合う。

large-2解法：

　10^100はやばすぎなので、普通にやっては解けない。のでOEISを使おう。
　というのが賢いやり方だと思うが、僕は普通に解いたのでそれを説明する。

　まず、二乗といえど普通の掛け算なので、筆算で書いてみる。
　回文数なので下のように変換しても同じ。
　

　よく見ると各桁の和も対称になっている。
　すなわち、キャリー(足し算の繰り上がり)が無ければ回文数になるのは明らか。
　問題はキャリーがある場合だが、キャリーがあると回文数にはならない。以下簡易証明。

　最下位(=最上位)に注目すると、キャリーがある場合、キャリー=最下位桁にならなければならない。
　すなわち、1〜9までの二乗のうち、2桁になり、1桁目と2桁目が一致、あるいは2桁目+1が一致するものとなる必要があるが、
　そんなものはないので、最下位桁でキャリーは起きない。
　となると、最下位桁は1,2,3のどれかになる。そうすると、最上位桁にキャリーを持ち越すと回文が崩れるので一個下の桁もキャリーはない。
　というのが再帰的に起こるので、絶対キャリーは起きない。

　となると、条件は各桁の和が10よりも小さければOKということになる。
　中央の桁に注目すると、これは2乗和になっているので、少なくとも2乗和が10よりも小さいことがわかる。
　ということは、3を使う場合それ1個のみ、2を使う場合中央か端で1回のみ、となるので、ほとんどが0と1のみのケースとなる。
　回文であることを頭に入れると、前半だけ決めると後半も決まる。1は前半で4回までしか使えない。
　よって、100桁でも大雑把に50C4程度しか組合せの数は存在しないため、全部調べても余裕。
　実は中央の桁が最大になることも(少し頑張ると)わかるので、2乗和が10を越えないような列を生成すればOK。

　ただ、二乗と大小比較を行うため、BigIntegerが欲しくなったりするところも割とめんどくさい。
　僕の自作BigIntがある前提だと以下のコードになる。(っていうかコレを提出した)

vector<BigInt> ps;
string a,b;
ll ans;

int cnt = 0;
void rec(int l,int n,string s,int sum){
  if(2*l>=n){
    cnt++;
    if(n&1)l--;
    for(int i=l-1;i>=0;i--)s += s[i];
    ps.push_back(BigInt(s)*BigInt(s));
    return;
  }

  for(int i=0;i<=3;i++){
    if(l==0 && i==0)continue;
    s += (char)('0'+i);
    int tmp = sum;
    if(2*(l+1)<=n)sum += i*i*2;
    else sum += i*i;
    if(sum<10)rec(l+1,n,s,sum);
    sum = tmp;
    s.erase(s.end()-1);
  }
}

int main(){
  int testcase;
  for(int i=1;i<=51;i++)rec(0,i,"",0);

  cin >> testcase;
  for(int casenum=1;casenum<=testcase;casenum++){
    cin >> a >> b;
    ans = upper_bound(all(ps),BigInt(b)) - lower_bound(all(ps),BigInt(a));
    cout << "Case #" << casenum << ": ";
    cout << ans << endl;
  }
}

D. Treasure

　箱がN個ある。鍵の種類が決まっていて、鍵と鍵穴の種類がマッチすると開けられる。
　初期に持っている鍵の他に、箱から新たに鍵を手に入れることもある。
　箱の鍵穴の種類、初期の手持ち鍵、それぞれの箱から手に入る鍵の情報に基づいて、すべての箱を開ける手順のうち辞書順最小の手順を示せ。

　制約：small 1≦N≦20,1≦鍵の総数≦40
　　　　large 1≦N≦200,1≦鍵の総数≦400

small解法：

　制約が20なので、お約束のbit全探索を疑う。
　どの箱が開いているかを0,1で表現すると、2^Nの状態がある。
　これに掛けることの今手持ちの鍵の情報……と考えてしまうが、開いている箱が同じであれば、手持ちの鍵の状態は常に同じになる。
　なぜならば、初期の鍵も、箱を開いて手に入る鍵も、箱を開くために消費した鍵も、すべて変わらないためである。
　よって、状態数は2^Nしかないため、全て開いていない状態→全て開いた状態へのパスを探せばよい。
　ただし普通に再帰して全探索するとつらそうなのでメモ化再帰にした。これで計算量はO(N*2^N)。
　また、鍵の数を状態ごとに復元するのがめんどくさかったので、関数の引数には鍵の数を持たせた(がメモ化のkeyとしては使わなかった)
　辞書順最小は、辞書順で若いものから優先的に使うように探索するだけでよい。

int k,n;
vector<int> ans,path;
int memo[1<<20];
int c[300],kn[300],gk[300][500];

int rec(int state,vector<int> keys){
  if(state == (1<<n)-1){
    ans = path;
    return 1;
  }

  if(memo[state]>=0)return memo[state];
  
  rep(i,n){
    if( (state>>i)&1 )continue;
    if(keys[c[i]]){
      keys[c[i]]--;
      path.push_back(i+1);
      rep(j,kn[i])keys[gk[i][j]]++;

      if(rec(state|(1<<i),keys) == 1)return memo[state] = 1;

      rep(j,kn[i])keys[gk[i][j]]--;
      path.pop_back();
      keys[c[i]]++;
    }
  }
  return memo[state] = 0;
}

int main(){
  int testcase;
  int tmp;

  cin >> testcase;
  for(int casenum=1;casenum<=testcase;casenum++){
    vector<int> keys(201);
    for(int i=0;i<=200;i++)keys[i] = 0;

    cin >> k >> n;
    rep(i,k){ cin >> tmp; keys[tmp]++; }
    rep(i,n){
      cin >> c[i] >> kn[i];
      rep(j,kn[i])cin >> gk[i][j];
    }

    path.clear(); ans.clear();
    rep(i,1<<n)memo[i] = -1;

    rec(0,keys);

    cout << "Case #" << casenum << ": ";
    if(ans.empty())cout << "IMPOSSIBLE" << endl;
    else rep(i,n)cout << ans[i] << ((i==n-1)?"\n":" ");
  }
}

large解法：

　わからん。神々のソースコードを読もう(提案)。