TCO Round 2A - 不定期プログラミング覚え書き

結果報告

250-450-1000のセット．Medium解けなくてRound2突破ならず
ratedになるとかいう噂もあったけれど，結局ratedになったらしい．
お陰でレートは自己ベスト更新した．
しかしもうちょっとEasyは早く解けなかったものか…

Level	ProblemName	Status	Point
Easy	SwitchesAndLamps	PassedSystemTest	130.13
Medium	CucumberWatering	Opened	0.0
Hard	EvenPaths	Unopened	----

Easy SwitchesAndLamps

問題

一対一に対応しているスイッチの集合とランプの集合があるが，どういった対応関係になっているかは分かっていない．
入力としてある程度，スイッチの状態に対するランプの状態が与えられている．
（例えば，switches[0]="YYNY"，lamps[0]＝"YYYN"なら，１・２・４番目のスイッチがON，３番目のスイッチがオフの時，１，２，３番目のランプが点灯，４番目のランプは消えている，という意味になる）
スイッチとランプの対応関係を明らかにするためには，
最低何種類のスイッチの状態を考察しなければならないか？

考えたこと

switches[0]="YYNY"，lamps[0]＝"YYYN"みたいなケースだと
１，２，４番目のスイッチと１，２，３番目のランプが対応する事はわかるが，
そこから先は今後の実験で調べるしか無い．
そしてそれは，あと $log_2 3$ 回調べれば良い．
このように，「このスイッチの集合とこのランプの集合が対応している事はわかるが，そっから先はわからん！」という対応を作れるだけ作って
その集合の要素の最大値を持ってきて，logを取ればよいだろう

書いた…なんとテストケースでエラーになった／(^o^)＼

方針はあっていたけれど，
「このスイッチの集合とこのランプの集合が対応している事はわかるが，そっから先はわからん！」と考えるときには，スイッチの集合とランプの集合は同じ個数でなければいけない，ということを忘れていた．
急遽それを付け加えるため，各スイッチについて「このランプとの対応は絶対にありえません」というランプの集合（コード的には配列）を用意し，それを比較する，なんていう強引な手段をとった

コード

  int theMin(vector <string> switches, vector <string> lamps) {
    int result=0;
    bool matches[51][51];
    memset( matches, true, sizeof(matches) );
    int s = switches.size();
    int size = switches[0].size();
    vector<vector<int> > match(51);
        for( int a = 0; a < s ; a++ )
        for( int i = 0 ; i < size; i++ ){
            for( int j = 0 ; j < size; j++ ){         
              if( switches[a][i] != lamps[a][j] ){
                match[i].push_back(j);
              }
            }
        }
    bool checked[51];
    memset( checked, false, sizeof( checked) );
    for( int i = 0 ; i < size; i++ ){
      sort( match[i].begin(), match[i].end() );
      match[i].erase( unique( match[i].begin(), match[i].end() ), match
                     [i].end() );
    }
    

    for( int i = 0 ; i < size; i++ ){
      if( checked[i] ) continue;
      int num =1; 
      checked[i] = true;
      for( int j = i+1 ; j < size; j++ ){
        if( match[i] == match[j] ){
          num++;
          checked[j] = true;
        }
      }
      if( size-num != match[i].size() ){
        return -1;
      }
      if( num == 0 ) return -1;
      int ans = 0;
      while( num > (1<<ans) ){
        ans++;
      }
      result = max( result, ans );
    }
    return result;
  }

計算量は,スイッチの数をN,予め与えられるスイッチーランプの対応関係の数をMとすると $O(MN^2)$ とか．

後々思ったこと．

vectorをゴニョゴニョ使うよりは多分bit列で符号化してあげたほうがわかり易かったんだろうなあ，と，他の人のコードを見ながら思った．

Medium CucumberWatering

問題

数列X[i]が与えられるので，数直線上を，数列で決められた順番通り歩かなくてはいけない．
ただし，K個ワープポイントを設置することが許されており，任意のワープポイント間は瞬時に移動できるものとする．
この時の最短移動距離を求めよ．

考えたこと

何となくワープポイントを置く場所はX[i]のどこかに限定して良い気がする．
でもそれ以上は全くわからん…単純に前通りためそうとしたら，ワープポイントの数が最大50である以上，到底間に合わない．

復習

editorialを読んだらワープポイントの場所がX[i]のどこかで良い事を綺麗に証明していた．

もしも最適解で，ワープポイントの場所がX[i]で表せないところにあると仮定するそのようなワープポイントの位置をX'とする．
この時，ワープポイントを少し移動することで，移動距離をより短く（もしくは変化なし）することができる事を示す．

このワープポイントが使われていない場合：X'はそもそもいらないので，取り除けば良い．
ワープポイントが使われている場合：X'がX[i]で表せない事により，X'を使う時人言うのは，右側からX'に入るケースと，左側からX’に入るケースに分別することができる．
右側から入るケースが多いのならば右側に，左側から入るケースが多いのならば左側にX'を移動させることで，
総移動距離を短くすることが出来る．
右側から入るケース＝左側から入るケースの時は，移動距離を変化させずにX'をずらす事が出来る．
よって，どのケースでもX'を左右どちらかに移動することが可能であり，最終的にX'=X[i']なるi'が存在するように出来る．

まあそんなわけで，ワープポイントの場所については直感通りであった．
しかし，それだけではコードが書けないのが難しい所．

editorialの説明は僕には解らなかったけれど，
simezi_tan氏の説明(http://d.hatena.ne.jp/simezi_tan/20120423/1335108392)を呼んで取り敢えずは納得．
dp[i][j]...X[i]にワープポイントを起き，あとおけるワープポイントがj個である時の，X[i]より右側で移動する距離の最小値．
なんて設定でのDPで解けた．
これは言われない限り思いつけない気がするなあ

コード

  long long memo[53][53];
  vector<long long> xs;
  vector<int> X;
  long long rec( int curx , int remK ){
    if( memo[curx][remK] != -1LL ) return memo[curx][remK];
    if( curx == (int)xs.size() ) return LONG_MAX/2;
    //case: no more teleport
    long long dist= 0;
    long long cur_val = xs[curx];
    for( int i = 0 ; i+1 < (int)X.size(); i++ ){
      ll maX = max( X[i], X[i+1] );
      ll miX = min( X[i], X[i+1] );
      if( maX >= cur_val  && miX <= cur_val ){
        dist += maX-cur_val;
      }
      else if( maX >= cur_val && miX >= cur_val ){
        dist += maX-miX;
      }
    }
    if( remK == 0 ) return memo[curx][remK] = dist;
    // case: more teleport 
    for( int j = curx+1; j < (int)xs.size(); j++ ){
      long long dist_tmp = rec( j, remK-1 );
      long long cur_left = xs[curx];
      long long cur_right = xs[j];
      for( int i = 0 ; i+1 < (int)X.size(); i++ ){
        ll maX = max( X[i], X[i+1] );
        ll miX = min( X[i], X[i+1] );
        if( maX <= cur_right && maX >= cur_left ){
          if( miX <= cur_right && miX >= cur_left ){
            dist_tmp += min( maX-miX, cur_right-maX + miX-cur_left );
          }
          else{
            dist_tmp += min( maX-cur_left, cur_right-maX );
          }
        }
        else{
          if( miX <= cur_right && miX >= cur_left ){
            dist_tmp += min( miX-cur_left , cur_right-miX );
          }
        }
      }
      dist = min( dist, dist_tmp);
    }
    return memo[curx][remK] =dist;
  }
  long long theMin(vector <int> x, int K) {
    long long result=0;
    X=x;
    for( int i = 0 ; i < (int)x.size(); i++ ) xs.push_back( x[i] );
    xs.push_back( -5000000000LL );
    xs.push_back( 5000000000LL );
    sort( xs.begin(), xs.end() );
    xs.erase( unique( xs.begin(), xs.end() ) , xs.end() );
    memset( memo, -1LL, sizeof(memo) );
    result = rec( 0, K );
    return result;
  }