練習帳

■ [実践]Google Code Jam Qualification Round 02:39

　問題一覧：http://code.google.com/codejam/contest/dashboard?c=975485

　全問small, large共に正答できました．時間をかければ解けるという事が分かって一安心です．

A. Bot Trust

要約

　一直線上にボタンが並んでおり，二体のロボットがその前を移動してボタンを押していく．ボタンは1m置きに並んでおり，スタート時ロボットは二体とも最左のボタンの目の前にいる．ロボットは秒速1mで移動でき，ボタンを押すにも1秒かかる．また，二人が同時刻に同時にボタンを押す事は出来ない．どちらのロボットがどこのボタンを押すかを順に並べた手順書が与えられているので，その手順書通りのボタンを押すのに要する時間を求めよ．

　ボタンの数は100個，テストケースの数はsmallで20個以下，largeで100個以下．手順書にある押すべきボタンの数はsmallで10個以下，largeで100個以下．

方針

　ロボットの移動する様子をシミュレーションすれば良い．

コード(c++)

　工夫したところを挙げるならば，ボタンを押す手順のデータ構造．例えば，

O 2 O 3 B 4 O 5 B 6

ならば，

vector<int>    o       : 235
vector<int>    b       : 46
vector<char> turns : oobob

と分解しています．さらに下のコードではo, bの終端には番兵をおいています．

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int INF = 1000000;

int solve(vector<int > & o, vector<int> & b, vector<char>& turns){
  int poso = 0;
  int posb = 0;
  o.push_back(INF);
  b.push_back(INF);

  int pointert = 0;
  int pointero = 0;
  int pointerb = 0;
  int tick = 0;

  while(pointert < turns.size()){
    bool flag = false;
    tick++;
    if(o[pointero] > poso){
      poso++;
    }else if(o[pointero] < poso){
      poso--;
    }else if (o[pointero] == poso && turns[pointert] == 'O'){
      pointero++;
      pointert++;
      flag = true;
    }
    if(b[pointerb] > posb){
      posb++;
    }else if(b[pointerb] < posb){
      posb--;
    }else if (b[pointerb] == posb && turns[pointert] == 'B'){
      if(! flag){
	pointerb++;
	pointert++;
      }
    }
  }
  return tick;
}

int main(){
  int t;cin >> t;
  for(int i = 1;i<=t;i++){
    int n;cin >> n;
    vector<int > o, b;
    vector<char> turns(n);
    for(int j = 0;j < n;j++){
      char r;int p;cin >> r >> p;
      p--;
      turns[j] = r;
      if(r == 'O'){
	o.push_back(p);
      }else{
	b.push_back(p);
      }
    }

    int ans = solve(o, b, turns);
    cout << "Case #" << i << ": " << ans <<endl;
  }
  return 0;
}

B. Magicka

要約

　魔法使いが自分のelement listにelementを与えられた順番に投入していき，すべてのelementを投入した後のelement listの中身を答える．elementには8種類のbase elementと18種類のnon-base elementがあり，投入されるelementはbaseのみである．base elementの中には互いに反応してelement listに様々な影響を与えるものがある．具体的には，

• element Aとelement Bがcombineしてnon-base element Cが発生する
  • element listの最後尾にA(resp. B)があり，そこにB(resp. A)を投入すると，A, Bがelement list から消え，element listの最後尾にCが表れる．
• element Aとelement Bがopposedの関係である
  • element listのどこかにA(resp. B)があり，そこにB(resp. A)を投入すると，element listが空になる．
• elementの組が同時にcombineかつopposedになりうる．その場合条件判定はcombine => opposedの順に行う．

　combine するbase element の組とそれからできるnon-base element のリスト，opposedの関係のbase elementの組のリスト，及びelement listに投入するbase elementのリストが与えられている．最終的なelement listの中身を答えよ．

　テストケースの数は100以下，combineのリストはsmallでは1個以下，largeでは36個以下，opposedのリストはsmallでは1個以下，largeでは28個以下，投入するelementの数はsmallでは10個以下，largeでは100個以下．

方針

　combine, opposedの素となるelement はbaseのみなので，これらの関係をそれぞれ8×8のテーブルに保存すれば良い．element listをスタックとして保存すれば，combineの関係をチェックは容易にできるが，opposedの関係はスタックの中身全てを見ないとならない．そこで，element listの中身を種類ごとにカウントするデータを用意している（下のコードではvector<int> statを指す）．

　

コード(c++)

　問題文を理解するのが一番大変でした．

#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
#include <deque>


using namespace std;

int INF = -100000;
const static char base[8] =  {'Q', 'W', 'E', 'R', 'A', 'S', 'D', 'F'};

void solve(string& invoke, 
	   vector<vector<int> > & C , 
	   vector<vector<int> > & D, 
	   string & ans){

  deque<char> st;
  vector<int> stat(26);

  for(int i = 0;i< invoke.size();i++){

    if(!st.empty() && C[st.back() - 'A'][invoke[i]- 'A'] >= 0){
      char to_be_removed = st.back();
      stat[to_be_removed - 'A']--;
      char to_be_put = 'A' + C[st.back() - 'A'][invoke[i]- 'A'];
      st.pop_back();
      st.push_back(to_be_put);
      stat[to_be_put - 'A']++;
      continue;
    }

    st.push_back(invoke[i]);
    stat[invoke[i] - 'A']++;

    for(int j = 0;j<8;j++){
      if(stat[base[j] - 'A'] > 0 && D[base[j]-'A'][invoke[i] - 'A'] == -1){
	st.clear();
	for(int k = 0;k < 26;k++){
	  stat[k] = 0;
	}
      }
    }    
  }
  ans.clear();
  ans += "[";
  while(!st.empty()){
    ans += st.front();
    ans += ", ";
    st.pop_front();
  }
  if(ans.size () >= 2) ans.erase(ans.end() -2, ans.end());
  ans += "]";

}

int main(){
  int t;cin >> t;
  for(int i = 1;i<=t;i++){
    vector<vector<int > > C(26, vector<int> (26));
    vector<vector<int > > D(26, vector<int> (26));
    for(int j = 0;j<26;j++){
      for(int k = 0;k<26;k++){
	C[j][k] = -1;
	D[j][k] = 0;
      }
    }

    int c,d;cin >> c;
    for(int j = 0;j<c;j++){
      string composed;cin >> composed;
      C[composed[0] - 'A'][composed[1] - 'A'] = composed[2] - 'A';
      C[composed[1] - 'A'][composed[0] - 'A'] = composed[2] - 'A';
    }
    cin >> d;
    for(int j = 0;j<d;j++){
      string opposed;cin >> opposed;
      D[opposed[0] - 'A'][opposed[1] - 'A'] = -1;
      D[opposed[1] - 'A'][opposed[0] - 'A'] = -1;
     }
    int n;cin >> n;
    string invoke;cin >> invoke;
    string ans;
    solve(invoke, C, D, ans);

    cout << "Case #" << i << ": " << ans <<endl;
  }
  return 0;
}

C. Candy Splitting

要約

　キャンディの山を兄弟2人で分ける．それぞれのキャンディには価値があり，弟は自分と兄が獲得するキャンディの価値の合計が等しくないと泣き出してしまう．ただし，弟は合計を計算するとき，通常の足し算ではなく，bitwise XORで行う．キャンディを2分割する方法があるかを答え，さらに分割する方法があるときは，兄の取り分での価値の合計（こちらは通常の足し算）が最大でいくらかを答えよ．

　テストケースの数は100個以下，キャンディの価値は10^{6}以下，キャンディの数はsmallで2以上15以下，largeで2以上1000以下

方針

　smallならばキャンディの分け方を全探索できるが，largeには対応できないので，組み合わせとは異なるアプローチがあるのだろうと予想できる．おそらく一番ポイントとなるのは，「もしXORでの合計が等しいような分け方が存在するなら，他にどんな分け方をしても，分けた2つの山のXORでの合計はやはり等しい」という事．もし，XORの値が等しいキャンディの分け方が存在するなら，

C[0] xor C[1] xor ・・・xor C[k] =   1100101010110・・・1001
C'[0] xor C'[1] xor ・・・xor C'[k'] =  1100101010110・・・1001 

のようにbitごとに等しくなるので，この2つのXORをさらに取ると，値は0となる．ここで別の分け方をしても，ビットごとには両方0 or 両方1となるので，やはりXORでの合計は等しい．

　そこで，全てのキャンディの価値のXORでの合計を計算し0か否かを判定する．0ならば，価値の最も低いキャンディを弟に与え残りを兄の取り分とする．

コード例

　この問題ではXORのcommutativityとassociativityを深く用いています．教科書などで証明などはさらっと書かれていますが，それがいかに強力な主張なのかがわかるという点で面白い問題だと思いました．

#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
#include <algorithm>
#include <numeric>

using namespace std;

int solve(vector<int> & c){
  int xsum = 0;
  int n = c.size();

  for(int i = 0;i<n;i++){
    xsum ^= c[i]; 
  }
  if(xsum != 0){
    return -1;
  }
  sort(c.begin(), c.end());
  int ans = accumulate(c.begin(), c.end(), 0);
  ans -= c[0];
  return ans;
}

int main(){
  int t;cin >> t;
  for(int i = 1;i<=t;i++){
    int n;cin >> n;
    vector<int> c(n);
    for(int j = 0;j<n;j++){
      cin >> c[j] ;
    }
    int ans = solve(c);
    if(ans == -1){
      cout << "Case #" << i << ": " << "NO" <<endl;
    }else{
      cout << "Case #" << i << ": " << ans <<endl;
    }
  }
  return 0;
}

D. GoroSort

要約

　1からNを並べ替えた数列が与えられている．これに対し次の操作を繰り返し行い，最終的に1 2 ・・・Nと整列した数列を得たい．操作は1からnのうちいくつかを固定し，残りを一様ランダムに並べ替えるというものである．固定する数字や個数は自由に決めてよい．最適に行動したとき，元の数列を並べ替えるのに必要な操作回数の期待値を答えよ．テストケースの数は100個以下，Nはsmallでは10個以下，largeでは1000以下．

方針

　最適な行動は既に正しい位置にある数字のみ固定するというもの，以下ある数字が既に正しい位置ある状態（例えば2が左から2番目にあるなど）を「マッチ」，そうでない状態（例えば2が左から3番目にあるなど）を「ミスマッチ」と呼ぶ事にする．

　求める期待値の値はミスマッチの個数のみによるので，ミスマッチの個数がn個の時の求める期待値をE(n)とおき． n個のうちm個がマッチする場合の数をg(n, m)とおく．例えば，3個中1個マッチするパターンは

1 3 2
2 1 3

の2通りなので，g(3, 1)=2 ．これを用いると，n個のミスマッチの状態からの1回の操作を考えて，

E(n) = 1 + Σ_{m = 0}^{n} g(n, n-m) * E(m) / n!　・・・（1）

という式が得られるので，ここからEを漸化的に求める事を試みる．そのためにまずgについての漸化式を求める．f(n)で，n個の数字が全てミスマッチする場合の数とする．例えばn = 3の場合は

2 3 1
3 1 2

の2通りなので，f(3) = 2．また，ここでは使いませんが，f(0) = g(n, n)の関係もある．fを愚直に計算すると，

f(m) = (m-1) * (f(m-2) + (m-2) * (f(m-3) + (m-3) * (f(m-4) + (m-4) * ・・・))))

となる．うれしいのは(m-2) * ・・・以降の部分がf(m-1) に等しい事で，ここから

f(m) = (m-1) * (f(m-2) + f(m-1) )

という漸化式が得られる．定義から

g(n ,m) = nCm * f(n-m)

なので，fについての漸化式からgについての計算式が得られる．結論だけ書くと，

g(n, m) = ( (n-m-1) * n * g(n-1, m) + n * (n-1) * g(n-2, m) ) / (n-m)
（if n≠m）
g(n, n) = 1
g(n, n-1) = 0

となる．これで目標は達成できたが，gをn!で割った，h(n, m) = g(n, m) / n!を用いるとさらに簡略化できる．hについての漸化式は

h(n, m) = ( (n-m-1) * h(n-1, m) + h(n-2, m) ) / (n-m)
（if n≠m）
h(n, n) = 1 / n!
h(n, n-1) = 0

となり，さらにEについての式は

E(n) = 1 + Σ_{m = 0}^{n} h(n, n-m) * E(m)
E(0) = 0
E(1) = 0

と，書き直せる．

コード例

以上の方針で書いたコードが下のものです．

#include <iostream>
#include <vector>
#include <utility>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <iomanip>

using namespace std;

typedef long long ll;

vector<double> memo(1001, -1);
vector<int> f_memo(10001, -1);
vector<vector<double> > h_memo(1001, vector<double> (1001, -1) ) ;


ll frac(int n){
  if(f_memo[n] >= 0) return f_memo[n];
  if(n == 0) return 1;
  return f_memo[n] = n * (frac(n-1));
}

double h(int n, int m){
  if(n == m) return h_memo[n][m] = 1/(double)frac(n);
  if(n - m == 1) return 0;
  if(h_memo[n][m] >= 0) return h_memo[n][m];  
  h_memo[n][m] = ( (n - m - 1)* h(n-1, m) + h(n-2, m))/(double)(n-m);
  return h_memo[n][m] ;
}

double E(int n){
  if(memo[n] >= 0) return memo[n];
  if(n == 0) return 0;
  if(n == 1) return 0;
  double ret = 0;
  for(int m = 0;m < n;m ++){
    ret += E(m) * h(n, n-m);
  }
  ret = (ret + 1)/ (double)(1- h(n,0));
  return memo[n] = ret ;
}


double solve(vector<int> & c){
  int mismatch = 0;
  for(int i = 0;i<c.size();i++){
    if(c[i] != i){
      mismatch++;
    }
  }
  return E(mismatch);
}


int main(){
  int t;cin >> t;
  for(int i = 1;i<=t;i++){
    int n;cin >> n;
    vector<int> c(n);
    for(int j = 0;j<n;j++){
      cin >> c[j] ;
      c[j] --;
    }
    double ans = solve(c);
    cout << "Case #" << i << ": "  << ans << endl;
      
  }
  return 0;
}

分析

　しかし，このコードはsmallしか通りません．計算量も多く，また，h(n, n) = 1/n!はn=1000くらい大きくなるとdoubleでは扱えないほど小さくなります．しかしsmallで実験してみると，実はE(n) = n (n ≠ 1)とわかります．つまり，ミスマッチの個数がそのまま答えになります．自分自身はなぜそれで正しいのかをきちんと理解できていませんが，largeは下のコードで通しました．

double solve(vector<int> & c){
  int mismatch = 0;
  for(int i = 0;i<c.size();i++){
    if(c[i] != i){
      mismatch++;
    }
  }
  return E(mismatch);
}


int main(){
  int t;cin >> t;
  for(int i = 1;i<=t;i++){
    int n;cin >> n;
    vector<int> c(n);
    for(int j = 0;j<n;j++){
      cin >> c[j] ;
      c[j] --;
    }
    double ans = solve(c);
    cout << "Case #" << i << ": "  << ans << endl;
      
  }
  return 0;
}

ツイートする