TopCoder Open Round 2B

結果報告

300-550-900のセット．
0ptで見事にレートが１００くらい下がりました．
Easyで変数書き忘れによりre-submit -> 変数初期化忘れで System test failedとかひどすぎる．
冷静に考えればMediumまでは解ける圏内であるべきだったなあ．
Hardは知らん．

Level	ProblemName	Status	Point
Easy	BlurredDartboard	SystemTestFailed	0.0
Medium	HeavyBooks	Opened	0.0
Hard	SequenceTransmission	Opened	0.0

Easy BlurredDartboard

問題

得点表が虫食い状態のダーツボードがある．
もともと得点は１，２，…，N-1,Nが１つずつ配置されていた．
ダーツの達人がこのダーツに挑み，得点をP以上にしたい．
確実にP以上の得点をとれる最小のダーツ投擲数を答えよ．

考えたこと

虫食い状態の物をまんべんなく使うか，
それとも点数の見えている物の中で最高得点（以下Mとする)を使うかだろう．
Mを使うなら，(N+M-1)/Mが答えである．
虫食い状態の物を使う時は，虫食い状態の点数の総和Sを求めておいて，
N/S（端数切り捨て)本ずつ各虫食い箇所に投擲した後，
虫食い箇所に適当に投擲した時（小さいものから順に取っていって何回でPを超えるか）
と，
Mに集中的に投擲した時
それぞれ考え，両者のうちの回数少ない方を取ればよいだろう．

書いた．
submitした
変数名一箇所間違えてるー！！
resubmitした
Systemtestfailed…だと…
変数初期化忘れてるーーー！
訂正した…orz（いまここ）

コード

  int minThrows(vector <int> points, int P) {
    int result=1000000001;
    int size = points.size();
    bool reserved[51];
    int maxscore = 0;
    memset( reserved, false, sizeof(reserved));
    for( int i = 0 ; i < size; i++ ){
      if( points[i] == 0 ) continue;
      else{
        reserved[points[i]] = true;
        maxscore = max( maxscore, points[i] );
      }
    }
    vector<int> vec;
    int sum = 0;
    int n_undef = 0;
    for( int i = 1 ; i <= size; i++ ){
      if( reserved[i] == false ){
        vec.push_back(i);
        sum += i;
        n_undef++;
      }
    }
    if( sum != 0 ){
      int set = ((long long)P)/sum;
      result = set * n_undef;
      ll val = set*sum;
      ll val2 = set*sum;
      int result2 = result;
      for( int i = 0 ; i < size; i++ ){
        if( val >= P ) continue;
        result++;
        val += vec[i];
      }
      if( maxscore != 0 ){
        if( (P-val2) % maxscore==0){
        result2 += (P-val2)/maxscore;
        }
        else{
        result2 += 1+(P-val2)/maxscore;
        }
        result = min( result , result2 );
      }
    }
    if( maxscore != 0 ){
      result = min( result, (P+maxscore-1)/maxscore);
    }
    return result;
  }

計算量はほとんどの所がO(1)で，
虫食い箇所を常に用いるケースの算出にO(虫食い箇所の個数) かかる

Medium HeavyBooks

TomekとWojtekが，重さのそれぞれ違う本を持ち運びたい．
一度に動かせる本の数は入力配列moveで与えられており，

• Tomekがmove[0]冊の本を選び，Wojtekのリュックに詰める
• Wojtekがmove[1]冊の本を自分のリュックから相手のリュックに押し付ける
• Tomekがmove[2]冊の本を自分のリュックから相手のリュックに押し付ける

...
といった操作を続けるとする．
両者は，自分の荷物の重さ-相手の荷物の重さを最小にするように常に行動し，
もしもこの値が変わらない複数の行動がある場合は，自分の荷物の重さ+相手の荷物の重さを最大にするように行動するとする．
最終的に両者が持つこととなる荷物の重さを要素数2のvectorとして返せ．

考えたこと(間違い含む)

どうせ最初以外は自分の持ってる重いものを相手に押し付けるだけじゃないですか．
ってことは本の重さの小さい順にソートしたら，
Tomekが持つ・Tomekが持つ……・Tomekが持つ，Wojtekが持つ，Wojtekが持つ……Wojtekが持つ，
みたいになるわけですよ． <- ここが間違い
てことは，Tomekが多く持たなきゃいけないシチュエーションなら，Tomekは小さいものの寄せ集めN個を持っていたら被害は少なく済む．　<- これも間違い
Tomekが少なく持つシチュエーションなら，Tomekは大きいものの寄せ集めN個を持っていたら嬉しい． <-これも間違い
よって最初のN個のばあいと最後のN個の場合をシミュレートすればよくね？

書いた…ら，コーディングフェーズラスト3秒とかなにこれ酷い．
コンパイルに3秒くらいかかってタッチの差でsubmit出来なかった＼(^o^)／

……ん，何か周りの話を聞いていると間違い臭いな．

復習後

まず，上記考えのどこが間違っていたかという話．
move={5,4,2}とか行った問題設定を考えると
最初にとった本5冊は最終的に小さい順に
Wojtek用，Tomek用，Tomek用，Wojtek用，Wojtek用となる．
よって，例えば本の重さが
{1,1,1,30,50,50}とかだったら，
Tomekは最初に選ぶ本を1,1,1,50,50とした方が嬉しいわけで．
最初と最後だけ考えれば良いなんて甘すぎたわけです．

じゃあ，どうすれば良いのか？という話．
Tomekが最初に選ぶmove[0]個本を軽い順にbook[0]...book[ move[0] ]とすると，
book[i]の行方は常に固定である．
よって，すべての本を軽い順にソートして，小さいものから順番に考えていくと良さそうだ．

此処から先は，iwiwiさんの提出コードを呼んだらﾃｨﾝときた
pairを要素と持つ配列dp[i][j]を用いて，動的計画法を使う．
dp[i][j]は，
すべての本の中で軽い本i冊のうち，Tomekはj冊をWojtekのリュックに最初に詰めた．
状態を表し，
第一要素：j冊の本のみを考えた時の，Wojtekの持つ重さ-Tomekの持つ重さ
第二要素：j冊の本のみを考えた時の，Wojtekの持つ重さ+Tomekの持つ重さ
とする．
このようなペアの最大値を常にdpの要素として保持する事で，
dp[本の数][ move[0] ]にTomek的に最善な最終状態（Tomekが先手なので，これが実質の最終状態にもなる）を用意することが出来る．

この状態から算出されるTomekの持つ重さ・Wojtekの持つ重さを答えとして返せば良い．

コード

  vector <int> findWeight(vector <int> books, vector <int> moves) {
    vector<int> result;
    sort( books.begin(), books.end() );
    int size = books.size();
    vector<int> signs;
    for( int i = 0 ; i < moves[0]; i++ ){
      signs.push_back(1);
    }
    int n_books = signs.size();
    for( int i = 1 ; i < (int)moves.size(); i++ ){
      int count = 0;
      int enemy = 1;
      if( i%2 == 0 ) enemy = -1;
      for( int j = (int)signs.size()-1; j >= 0 ; j-- ){
        if( count >= moves[i] ) break;
        if( signs[j] == enemy ){
          signs[j] *= -1;
          count++;
        }
      }
    }
    pair<int,int> dp[51][51];
    for( int i = 0 ; i < 51; i++ ) for( int j = 0 ; j < 51; j++ ) dp[i][j] = make_pair( -INT_MAX/2, INT_MAX/2 );
    // dp[i][j]...from i kinds of books. use j books
    // dp[i][j].first = result[1]-result[0].
    // dp[i][j].first = result[1]+reslt[0];
    // dp[i][j] is defined from dp[i-1][j] and  dp[i-1][j-1]
    for( int i = 0 ; i < 51; i++ ) dp[i][0]=make_pair( 0, 0 );
    for( int i = 1 ; i <= size; i++ ){
      for( int j = 1 ; j <= n_books; j++ ){
         dp[i][j] = max( dp[i-1][j], make_pair( dp[i-1][j-1].first+signs[j-1]*books[i-1], dp[i-1][j-1].second+books[i-1] ) );
      }
    }
    result.push_back( (-dp[size][n_books].first+dp[size][n_books].second)/2 );
    result.push_back( (dp[size][n_books].first+dp[size][n_books].second)/2 );
    
    return result;
  }

dp部の計算量は大体，本の数*move[0]の値．

Hard SequenceTransmission

問題

a,b,nが入力として与えられていて，
a+b, 2*a+b, ...,(n-1)*a+b, n*a+bまでをbit列でつなげるとする．
例えばa = 3, b = 5, n = 4なら，
10001011111010001となる．
このbit列の0->1,1->0の移り変わりの個数（上の例で言えば8）を答えよ．

考えたこと

( ﾟдﾟ)