不定期プログラミング覚え書き

青コーダーと黄コーダーの間を彷徨う社会人プロコン勢が余力のあるときに復習した内容をまとめるブログ

SRM561

TopCoder

物凄く久しぶりに日記更新。
SRM 555の裏オンサイトに参加した回から日記が止まっているという大変アレなことをした。
今更ながら参加者の方々お疲れ様でした！　何ヶ月前の話だよってツッコミは禁止！

この３ヶ月間、レートも大きな変動なく、相変わらず青と黄色を行ったり来たりしている。
久しぶりにgrundy数なるものを学んだこともあるので、備忘録も兼ねてまとめておこうと思う。

結果報告

250-550-1000のセット。

Level ProblemName Status Point
Easy ICPCBaloons PassedSystemTest 105.76
Medium CirclesGame Opened(practiced) 0.0
Hard -- Unopened 0.0

1500->1497->1518とかそんな感じのレート遷移をしてる。

Easy ICPCBaloons

問題

ICPCにおいて、問題に正解したチームにはバルーンが与えられる。
同じ問題に正解したものには、同じ大きさ・同じ色のバルーンが与えられるものとする。
今、様々な色のバルーンが存在する。
baloonCount[i]が第i色のバルーン個数で、baloonSize[i]がそのバルーンのサイズだとする。('M'ならば中くらいのサイズ、'L'ならば大きいサイズ）
ICPCの問題セットには、最大何チームがその問題に正解するかの予測が与えられている。maxAccepted[i]が第i問の正解者数最大数である。
この予測は決して外れることはない。
baloonの色を適宜塗り替えることによって、
すべての問題を最大正解者数分解かれたとしても、バルーンが不足しないようにしたい。
最小何回の塗り替えでこの条件をみたすことが可能か答えよ。不可能ならば-1を返せ。

考えたこと

問題の個数が15問までなので、
各問題について、どっちのサイズのバルーンを配布するようにするか？のパターンは
2^15くらいのオーダーでできる。
そうすると、以下の問題を各ループの中でとけば良い。

i色の同じサイズのバルーンがそれぞれ与えられる。
このバルーンを、n人に、指定の個数ずつ分け与えたい。
ただし、同じ人には、同じ色のバルーンしか渡せないとする。
何回バルーンを塗り替えればそれが可能か？

この問題を解くのに、各色を誰に割り当てるか？とかを愚直にやっていたが、当然のごとくTLEする。
考えなおしてみたところ、そのための計算量は、人数の階乗なので、当然この方針では無理だった。
(何故か最初は脳内で2^15と思っていた。個人的にこのミスが非常に多い気がする）
じゃあ…というわけで、人数orバルーンの種類の過不足を0で埋めて降順ソート、
大きな個数のバルーンを必要とする人から順に、大きな個数あるバルーンを割り当てておき、
足りない個数を色変えで補う、という貪欲法とする。
もちろん、色塗り不可能な場合は予め省いておくとする。

計算量は文句なく足りた。そしてなんか通った。
greedyで良いのか、若干証明が曖昧だけど、Submitする->通ったわーい

本当はgreedyの確証までしっかり持てて、それに気づけるといいんだけどなあ。

コード
  int calc( vector<int> have, vector<int> use ){
    int hsize = have.size();
    int usize = use.size();
    int maxsize = max(hsize,usize);
    while( have.size() != maxsize ) have.push_back(0);
    while( use.size() != maxsize ) use.push_back(0);
    sort( have.begin(), have.end() );
    sort( use.begin(), use.end() );
    int res = 0;
    for( int i = 0 ; i < maxsize; i++ ){
      if( use[i] > have[i] ) res += use[i]-have[i];
    }
    return res;
  }
  int minRepaintings(vector <int> balloonCount, string balloonSize, vector <int> maxAccepted) {
    int result = INT_MAX/2;
    int n_balloon = balloonCount.size();
    int n_problem = maxAccepted.size();
    int n_m_balloon=0;
    int n_l_balloon=0;
    vector<int> M_have;
    vector<int> L_have;
    for( int i = 0 ; i < n_balloon ; i++ ){
      if( balloonSize[i] == 'L' ){
        n_l_balloon += balloonCount[i];
        L_have.push_back( balloonCount[i] );
      }
      else{
        n_m_balloon += balloonCount[i];
        M_have.push_back( balloonCount[i] );
      }
    }
    sort( L_have.begin(), L_have.end());
    sort( M_have.begin(), M_have.end());
    sort( maxAccepted.begin(), maxAccepted.end() );
    for( int i = 0 ; i < (1<<n_problem) ; i++ ){
      vector<int> M_used;
      vector<int> L_used;
      int m_balloon_wanted=0;
      int l_balloon_wanted=0;
      for( int j = 0 ; j < n_problem; j++ ){
        if( (i & (1<<j)) != 0 ){
          M_used.push_back( maxAccepted[j] );
          m_balloon_wanted += maxAccepted[j];
        }
        else{
          L_used.push_back( maxAccepted[j] );
          l_balloon_wanted += maxAccepted[j];
        }
      }
      if( m_balloon_wanted <= n_m_balloon && l_balloon_wanted <= n_l_balloon ){
       int res1 = calc( M_have, M_used );
       int res2 = calc( L_have, L_used );
       result = min( res1+res2, result );
      }
    }
    if( result == INT_MAX/2 ) return -1;
    return result;
  }

計算量はNを問題数、Mをバルーン数とした時のO(2^N* max(N,M) )かな。

Greedyで良いコトの証明

直感的に納得したようなそうでもないような。とりあえず書いてみる。
i番目に要求バルーンの多い問題に、i番目に個数の多いバルーンの色を割り当てる、以外の方法で、
最適なバルーンの配置があるとする。
その配置を、
i番目に要求バルーンの多い問題に、a_i番目に個数の多いバルーンの色を割り当てるとする。
すると、a_iの定義から、
[tex:i a_j] であるような自然数i,jが存在する。
以下の用語を定義する。

  1. i番目に要求バルーンの多い問題が要求するバルーン数をR_i
  2. a_i番目に個数の多いバルーンの個数をN_i
  3. a_i最終的に色塗りによって何個増えたか？をS_iとする。

（つまり、色塗りによってその色のバルーンを増やしたのならばS_iは正、そうでなければ負である。)
定義により、 N_i+S_i >= R_i , N_j + S_j >= R_j, R_i >= R_j, N_i< N_jである。

  1. S_i=S_j=0の時、もちろんa_iとa_jを入れ替えても良い。
  2. S_i,S_jの符号が等しい(0も含む)時、a_iとa_jを入れ替えるとSの総和は減る（両方正）か等しい（両方負）かである。
  3. S_i<0 , S_j >0 の時は上述の不等式に矛盾するため、ありえない。
  4. S_i>0 , S_j <0 の時、入れ替えによってSの総和は減る

以上の４パターンにより、a_iとa_jは入れ替えても色塗り個数は減るor不変である。
これを永遠に繰り返していくと、最終的にgreedyな塗り方に行き着く。

正直細かな検証してないしもっと適切な場合分けある気がするけど個人的に納得したからよしとしとく。

Medium CirclesGame

平面の上にたくさん円がある。
円は交わることはないということが知られている。
今、AliceとBobが平面上にドットを打ち、ドットをかこう円をすべて消していく、というゲームを行う。
円をすべてなくしたプレイヤーが勝ちである。
Aliceが常に勝利できる場合はAliceを、そうでない場合はBobを返せ

考えたこと

( ﾟДﾟ)

復習

安定のしめじたんブログ(http://d.hatena.ne.jp/simezi_tan/20121121/1353438294)にてgrundy数というものがあることを知る
蟻本とか、nanikakaさんのブログ(http://d.hatena.ne.jp/nanikaka/20120524/1337797626)とかをみて、納得した気分になった。
多分一ヶ月もしたら忘れているであろうから、今のうちにまとめておく。
1. 超要約
交互に資源を奪っていき、最後の資源をなくした人が勝利というゲームは、
Nimというゲームに帰着することができ、grundy数という値で計算できる。

2. Nimとは？
何個かのコインが積み重なったパイルがある。（パイルは複数あるかもしれない）
AliceとBobは交互にパイルを選び、そこから１つ以上のコインを取るとする。
最後に資源をとった方
2-1. Nimの解き方
実はこのゲームは、すべてのパイルのコインの個数をXORした値（これがgrundy数である)が、
0以外->Aliceの勝ち、0->Bobの勝ちという事が知られている。
これは、

  1. grundy数が0以外の場合は、次のターンにgrundy数が0となるようなコインのとり方が存在すること
  2. grundy数が0である状態からはgrundy数が0以外の値にしか遷移できないこと

という２点の考察からわかる（特に前者の説明は蟻本がわかりやすこと）

3. 一般のgrundy数
一つの系（Nimで言う一つのパイル。一度に操作可能な単位）においては、grundy数は以下のように計算できる。
S = ∅
forall(遷移後の状態){
S.add(遷移後の状態のgrundy数)
}
return 0以上の整数でSに含まれない最小のもの

遷移ができない状態は0であることに注意する。
Nimに於いて、N個のコインがあるパイルのgrundy数はNである。（ガチ証明するなら帰納法とか使えば良い）。

また、grundy数がNであるとは、
grundy数が0〜N-1の状態にすべて遷移可能であることを示す。

複数の系のgrundy数は、各系のgrundy数をxorした値である。
つまり、7個のコインのあるパイルと3個のコインがあるパイルが存在する状態とは、
4個のコインがあるパイル1個の状態に等しい（7xor3=4)と言っている。
これはなぜかといえば、物凄く直感的に言うと、
異なる系で同じところにbitが立っていると、
そのbitが変化する行為を片方の系で行った際に、
それを打ち消すような行為を対戦相手がもう片方の系で行うことが可能であるから、そのbitはあってもなくても変わらない。
つまり、上の例で言えば、各パイルの3個のコインはあってもなくても変わらないのである。

与えられた問題にあるゲームは、
円の包含関係で表せるツリー構造から、ある頂点を選び、頂点から根までのパスを除去する行為を繰り返すことに該当する。
ゲームの性質から、ゲームの過程で現れる部分木は、元の木からある頂点を選び、その子どもをごっそり持ってきた形しかありえない。
よって、各頂点以下の部分木に対してgrundy数を計算すると良い。
遷移後に一つの木がもりになることがあるが、それはgrundy数の性質より、xorをすれば良い。

コード
  int grundy[52];
  int size;
  bool child[52];
  int parent[52];

  int grundy_rec( int x ){
    if( grundy[x] != -1 ) return grundy[x];
    set<int> S;
    for( int i = 1 ; i <= size; i++  ){
      bool ok = false;
      int curp = i;
      set<int> removed;
      while( curp != 0 ){
        if( curp == x ){ ok = true; break; }
        removed.insert( curp );
        curp = parent[curp];
      }
      if( ok ){
        removed.insert(x);
        int score = 0;
        for( int j = 1 ; j <= size; j++ ){
          if( removed.find(j) == removed.end() && removed.find(parent[j]) != removed.end() ){
            score ^= grundy_rec(j);
          }
        }
        S.insert(score);
      }
    }
    int score = 0;
    while(  S.find(score) != S.end() ) score++;
    return grundy[x]=score;
  }
  bool include( int x2, int y2 , int r2 , int x , int y , int r ){
    if( r < r2 ) return false;
    if( (r-r2)*(r-r2) >= (x-x2)*(x-x2)+(y-y2)*(y-y2) ) return true;
    return false;
  }
   string whoCanWin(vector <int> x, vector <int> y, vector <int> r)
  {
    size = r.size();
    vector<pair<int,int> > vec;
    for( int i = 0 ; i < size; i++ ) vec.push_back( make_pair( r[i],i ));
    sort( vec.begin(), vec.end() , greater< pair<int,int> > () );
    memset( child, true, sizeof(child) );
    memset( parent, 0, sizeof(parent) );
    child[0] = false;
    for( int i = 1 ; i <= size; i++ ){
      int ind = vec[i-1].second;
      int nowx = x[ind];
      int nowy = y[ind];
      int nowr = r[ind];
      for( int j = i-1; j > 0 ; j-- ){
        int ind2 = vec[j-1].second;
        int tmpx = x[ind2];
        int tmpy = y[ind2];
        int tmpr = r[ind2];
        if( include( nowx, nowy, nowr, tmpx, tmpy, tmpr ) ){
          child[j]=false;
          parent[i]=j;
          break;
        }
      }
    }
    /*
    for( int i = 0 ; i <= size; i++ ){
      cout << child[i] << " ";
    }
    cout << endl;
    for( int j = 0 ; j <= size; j++ ){
      cout << parent[j] <<" ";
    }
    cout << endl;*/
    memset( grundy, -1, sizeof(grundy) );
    int grd = 0;
    for( int i = 1; i <=size; i++ ){
      if( parent[i] ==0 ){
        grd ^= grundy_rec(i);
      }
    }
    if( grd == 0 ) return "Bob";
    else return "Alice";
  }

頂点の個数をNとすると、状態数は頂点の個数に等しく、
各状態について遷移可能な状態もたかだかNなので、計算量は O(N^2)とかかな。