SRM 554

Single Round Match 544 Round 1 - Division II

http://community.topcoder.com/stat?c=round_overview&er=5&rd=14736

250に11分。残り時間を500に費やすも、投稿できず。Room 55。レートは780から847へ。白コーダー。

Problem Status Points
250 ElectionFraudDiv2 Passed System Test 218.78
500 BoardSplitting Opened 0.00
1000 AliceBobShuffle Unopened
  • 250に11分。218.78ポイント
  • 残りを500に費やす
    • 貪欲法で考えるもうまくまとまらず、DPで書き始める
    • 頭真っ白状態で終了
  • 250でチャレンジできる(不具合を起こしそうな)実装を見つけた
    • しかしデータが用意できず
  • レートが少し上がってうれしい
  • 次回の目標
    • 2問通す

ElectionFraudDiv2

http://community.topcoder.com/stat?c=problem_statement&pm=11946&rd=14736

11分。218.78点。

  • 実装を終え、テストもパスしたので投稿した
    • よく書けたように思う

以下は投稿した実装。

class ElectionFraudDiv2 {
public:
  std::string IsFraudulent(std::vector<int> percentages) {
    int l = 0, u = 0;

    EACH(it, percentages) {
      l += std::max(*it * 10000 / 100 - 50, 0);
      u +=          *it * 10000 / 100 + 49;
    }
    
    if (l <= 10000 && 10000 <= u) {
      return "NO";
    }
    else {
      return "YES";
    }
  };
};
  • 初めは上限の+ 49をしていなかった
    • テストケースに助けられた
    • これがなかったらまた落ちていただろう
    • うーむ
  • チャレンジできる実装を見つけた
class ElectionFraudDiv2 {
public:
  string IsFraudulent(vector <int>);
    
};
 
string ElectionFraudDiv2::IsFraudulent(vector <int> p) {
  float pr=0,ps=0;
  for(int i=0;i<p.size();i++)
    {
      pr+=((float)p[i]-0.5);
      ps+=((float)p[i]+0.4);
    }  
  //cout<<pr<<" "<<ps;  
  if(pr>100||ps<100)
     return "YES";
  else
    return "NO";     
}
  • 上限を少なくとも+ 0.49、もしかしたら+ 0.499999等にしなければいけないはずだ...
    • しかしテストケースを考えつくことができなかった
    • 考えついたわけではないが、"51 51"でよかったらしい
    • 後で考えよう
  • SRM544 Div2 Easy(250) ElectionFraudDiv2 - 赤コーダーになりたいを読む
    • Div II Easyはどんどん難しくなってきているらしい
    • 今回はテストケースが助けてくれるようになっていたので、そう感じなかった
    • テストケースが助けてくれない場合が多くなってきたようには感じる

BoardSplitting

http://community.topcoder.com/stat?c=problem_statement&pm=11951&rd=14736

60分超費やした。未投稿。

  • 貪欲法のような気がした
    • まとまらなかった
  • DPで書き始めた
    • 頭の中真っ白
    • 終了
  • チャレンジで他のコーダーの実装を読むに貪欲法であった
  • 考えてみるに、二段階の貪欲法だ
  • 長さ5の板が4つ必要だとする。また、供給される板の長さを4とする


  • actualLengthがdesiredLengthより長い場合は板を切ることなく長さを満たすことができる


  • これは以下のように処理できる
  desiredLength -= (desiredLength / actualLength) * actualLength;
  • この処理が終わった後は常に以下が成り立つことに注意しよう


  • この例の場合、更新されたdesiredLengthは1だ
    • desiredLengthが1の場合の処理は容易に想像できる
    • 供給される板を折っていけばよい
      • 折った回数をカウントする


  • 供給された板を折らなくてよい場合があることに注意しよう


  • この場合はもちろんカウントしない
  • 以下を考えよう


  • これは一回目の貪欲法で終わってしまうケースだ


  • 折る必要がないので、答えも0
  • ここまではいいとする
    • 以下のような場合で頭が真っ白になってしまった


  • 一回折る


  • 次に折る方法が以下のように2種類あり、その選び方によって結果が変わるように考えてしまったのだ


  • DPで実装しようと決めたのは、そのような理由であった
    • 「全てを網羅しなきゃ」
    • 挙げ句の果てに途中から頭真っ白である
  • 上の例では何れにしても一回折っている
    • つまり、折った余りが求める長さでない場合は、どのような方法を取ったとしても一回折らなければならない
  • もっと言えば、二回以上折る必要はない
    • 板は無限に供給されるからだ
    • 余りを考えなければ、desiredCount回折ればよい
    • もちろん最適解ではない
  • もう一回言い直そう
    • ちょうどよい長さ分余っていれば折らなくてよい
    • そうでない場合も一回折ればよい
      • この場合は余りの中の切れ端の一つを折ってやったほうがよい
      • つまり、上の図の左側のように敷き詰めるようにしたほうがよい
  • こう考えると周期があることが分かる
    • desiredLengthとactualLengthの最小公倍数をdesiredLengthで割った数だ


  • 実際はこれを考慮せずとも反復してしまえばよい

実装は以下(システムテスト済み)。

class BoardSplitting {
public:
  int minimumCuts(int desiredLength, int desiredCount, int actualLength) {
    desiredLength -= (desiredLength / actualLength) * actualLength;
    
    int c = 0, r = 0;

    for (int i = 0; i < desiredCount; i ++) {
      if (r > desiredLength) {
	r -= desiredLength;
	c += 1;
      }
      else if (r == desiredLength) {
	r -= desiredLength;
      }
      else {
	r += actualLength - desiredLength;
	c += 1;
      }
    }
    return c;
  };
};
  • 貪欲法は苦手だ
    • システムテストを通っても懐疑的になってしまう
    • 貪欲法ができる人はきっととても頭のいい人だろうと思ってしまう