Codeforces Round #303 (Div. 2)

初めてCodeforcesに参戦しました。結果は5問中4問正解で2826人出場した中で254位でした。そしてレイティングは1500 → 1704でCandidate Masterに！！ん？これってDiv.1じゃないか。#304(Div.2)にも参加する気でワクワクしていたのでちょっと複雑wまぁレイティングが変化しないけど問題を解くことはできるし、時間と体力があれば参戦しようかと思ってます。以下今回の問題の簡単なサマリー。

A - Toy Cars

問題文を3周くらい読んでようやく理解したのはここだけの秘密w Inputは総当たりの対戦表になってるんですね。つまり、各行をみて1(自分のみ負け)または3(両方負け)が１つでもあれば負けです。そうでない行の数を数えれば終了!

B - Equidistant String

最初にSusie loves symmetryと見て回文にしないといけないと勘違い。少々難しいと感じて飛ばしましたw C, Dを解き終えた後にもう一度問題を読んでも勘違いに気づかず、Sample Outputをみてようやく気づきました。正解者の多い問題だったので解けなかったらどうしようかと正直ちょっと焦りましたw

C - Woodcutters

この問題はGreedyで解けますね。自分はまず、両端はそれぞれ外側に倒す。それ以外は左側の木から考えていき、左に倒せるならそれを優先、右にも倒せないならばその木は倒すことができないと考えました。

if(n == 1){
    cout << 1 << endl;
  } else if (n == 2){
    cout << 2 << endl;
  } else {
    int result = 2;
    for(int i = 1; i < n - 1; i++){
      if(x[i - 1] < x[i] - h[i]){
        result++;
      } else if(x[i] + h[i] < x[i + 1]){
        result++;
        x[i] = x[i] + h[i];
      }
    }
    cout << result << endl;
  }

D - Queue

これはソートをして、時間の小さい方からGreedyに考えればいけますね。

E - Paths and Trees

これが解けませんでした。ダイクストラ法など勉強はしてきたつもりだったんですけどまだまだですね。今の自分はグラフが一番弱いです。そろそろ対策をせねば。