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

Google Code Jam Round 2とか SRM543(自習)とか書いてないものも色々あるけど，まずは最近のを書いておこう．

275-500-1000のセットでした．
250以外のEasyは本当良いこと無い…
Mediumがとき易かったので助かった．

Level	ProblemName	Status	Point
Easy	ElectionFraudDiv1	ChallengeSucceeded	0.0
Medium	FlipGame	PassedSystemTest	399.65
Hard	SplittingFoxes	Opened	0.0

Easy ElectionFraudDiv1

問題

投票割合を丸めて整数で表そうとすると総和が100にならなかったりする．
例えば，投票者数３人＆投票先３人だったら，
全員違う人に投票すれば，{33,33,33}みたいな結果になるし，
投票者数７人＆投票先３人で，２人・２人・３人みたいに表が集まったら，
結果は{29,29,43}になったりする．
この{29,29,43}みたいな最終的投票結果を入力として受けた時，
その結果を可能にする最小の投票者数を答えよ

考えたこと

なにこれわかんない．

>Mediumを読んだらそっちが解けそうだったのでお茶を濁す
>戻ってくる
>なにこれわかんない
>取り敢えずある程度大きな人数まで順に見ていって，投票結果の可否判定するコード書くか
>なんかバグってる気しかしないけど時間無いので提出
>チャレンジされた，まあ予定通りね

復習

方針としては間違っていなかったらしい．
ただ，X人の投票者数がいるときに，投票率Y%になるような人数に幅が有ることをすっかり考え忘れてた．
そのあたり修正して，負の投票者数とかも禁止するようにしたら通った．
なぜこの方針で良いのか等まだ釈然としない．．．

  int MinimumVoters(vector <int> percentages) {
    int sum = 0;
    int size = percentages.size();
    for( int i = 0 ; i < (int)percentages.size(); i++ ){
      sum+=percentages[i];
    }
    for( int i = 1 ; i <= 100000 ; i++ ){
      int countmin=0;
      int countmax = 0;
      bool ok = true;
      //cout << i << "," ;
      for( int k = 0 ; k < size; k++ ){
       int point = percentages[k];
       int start = (2*point-1)*i/200;
       if( point>0&&((2*point-1)*i )% 200 != 0 ) start++;
       start = max(0, start);
       if( start*200 >= (2*point+1)*i){
         ok = false;
         break;
       }
       countmin += start;
       int end=(2*point+1)*i/200;
       if( ((2*point+1)*i)%200 == 0 ) end--;
       countmax+= end;
      }
      if( ok && countmin <=i && countmax >= i ) return i;
    }
    return -1;
  }

計算量は入力配列長さ*100000くらい？

Medium FlipGame

問題

H×Wの盤面がある．
毎ターン，左上から右下への最短路を一つとり，
その最短路の下側の枡だけひっくり返すという動作をする
入力として，この操作をある程度繰り返した時の結果が与えられる
その結果を作り得る最小のターン数を答えよ．

考えたこと

ある値のマス目がk回ヒックリ返されるとすると
その左側のマス目・下のマス目は必ずk回以上ヒックリ返されないと行けない．
最終的に表であるか否かに従い，最低k回ork+1回ひっくり返さなくてはいけないといえる．
この操作をマス目の右上からじゅんじゅんに繰り返していけば，
左下の盤面のひっくり返される回数＝最低でも費やさないといけないターン数が求まる．
このターン数ちょうどで与えられた結果が実現出来る事はすぐに分かる．
（値がkの枡〜k-1の枡の境界でひっくり返す，という操作をやり続ければ良い）
よって，左下の盤面がひっくり返される回数を答えれば良い．

コード

 int minOperations(vector <string> board) {
    int table[51][51];
    int h = board.size();
    int w = board[0].size();
    memset( table, 0, sizeof(table));
    for( int i = 0 ; i < h ; i++ ){
      for( int j = 0 ; j < w ; j++ ){
        if( board[i][j] == '1' ) table[i][j] = 1;
      }
    }
      for( int i = 0 ; i < h ; i++ ){
        for( int j = w-1 ; j >= 0 ; j-- ){
          if( j-1 >= 0 && table[i][j] > table[i][j-1] ){
            if( (table[i][j] %2) == (table[i][j-1]%2) ){
              table[i][j-1] = table[i][j];
            }
            else{
              table[i][j-1] = table[i][j]+1;
            }
          }
          if( i+1 < h && table[i+1][j] < table[i][j] ){
           if( (table[i+1][j] %2) == (table[i][j]%2) ){
              table[i+1][j] = table[i][j];
           }
           else{
             table[i+1][j] = table[i][j]+1;
           }
          }
        }
      }
      /*for( int i = 0 ; i < h ; i++ ){
        for( int j = 0 ; j < w ; j++ ){
          cout << table[i][j] << ",";
        }
        cout << endl;
      }*/
    return table[h-1][0];
  }

計算量は $O(HW)$ ．

Hard SplittingFoxes

問題

一応問題開いて急いで読もうとしたけどあまりよく飲み込めなかったのでパスした