SRM 751 Div 2 に参加

topcoder

Submit Div 2 問題

https://community.topcoder.com/stat?c=round_overview&rd=17400

レーティング

  • レーティング 0の白コーダー
  • Easy, Midを解けたがHardは解けず
  • 結果、0->1152 で緑に。1200を越えると青になるようで、AtCoderの青よりも難易度が低いことが分かる

TopCoderの特徴

  • クラスにメソッドを定義して提出する
  • チャレンジフェイズがあってRoom内の他人のコードのバグを見つけるとポイントが貰える
    • チャレンジで撃墜は結構ある
    • 事前のテストを増やした方がぬか喜びしなくて済みそう
    • 運営の負荷削減のためだろう
  • リロード時など、レスポンスが遅い
  • 遅く解くとスコアが低い。早解きが有利

難易度

  • Div2 Easy, Mid, Hardがそれぞれ、
  • ABCのB, C, Dに対応するように感じた

公式解答

https://www.topcoder.com/blog/single-round-match-751-editorials/

Easyについて

struct CalkinWilf {
    vector <int> findRational(string path) {
        int a = 1, b = 1;
        for (char p: path) {
            if (p == 'L') {
                b += a;
            } else {
                a += b;
            }
        }
        return {a,b};
    }
};
  • 最後のreturn、こういう書き方ができるんだ

Mid

  • 2/100などを考えると、2/98, 2/96... と同じ方向に何度も上がることに気づくと、一気に上がれると分かる
  • 一方、25/35などだとジグザグに上がるが、1ステップ毎に大きい方が半分程度になる
  • 計算量はlog(N)となりそう　→AC

Hard

  • 全ての頂点の次数が偶数
    • それはオイラーグラフ
    • オイラーグラフは一筆書きできる
    • 一筆書きしつつ、奇数または偶数番目の辺を切れば半分になる
  • 基礎の応用だ

Div 1

  • 多くの人はこちらに参加
  • TLもワイワイとなっていて、結構参加しているようだ