Codeforces Beta Round #9

時間が合わずにずっと回避してきたCodeforceについに参加できました。

Problem A: Die Roll

  • 3人で6面サイコロを振って、一番大きかった人が勝ち。ただし自分が最大でタイだった場合、自分の勝ち。
  • 自分が勝つ確率を求めなさい。
    • ただし結果は分数で出してください。
  • GCD書くだけ。Accepted.

Problem C: Hexadecimal's Numbers

  • N (<109) 以下の整数で、10進表記したとき0と1しか含まないような数はいくつある?
  • そんなに多くはなさそうだし、Nを超えるまで小さい順にひたすら生成してみた。
  • Accepted.

Problem B: Running Student

  • 原点からX軸に沿ってバスが走る。バスに乗って、どこかのバス停で降りて、目的地まで自力で走る。バスの速さと自分の速さと目的地の座標が既知。最速で目的地に着くにはどのバス停で降りればいい?
    • 最速となるバス停が複数あるなら、目的地に一番近いものを出してね。
  • バス停の数少ないし、全部試せばいいよね。
    • 座標値を2乗するとオーバーフローするのと、誤差に気をつける。
  • WA. 誤差で死んでるのかな。
  • 整数で出来るところは整数でやるようにしてsubmit. WA...
  • ...
  • Standingを見てみた。自分の一つ上に、先先代の部長と思われる人がいた。
    • 東京の大学の院に進学して以来音信不通なのだけど、元気でやっていらっしゃるようだ。
  • ...
  • ・・・何かトラップがあるのかな。
  • バス停は順番に並んでるとは限らない。同じ道の上を行ったり来たりするような変態路線があるかもしれず、バスの移動時間を (始点からの距離/速さ) で求めると間違う、とか。
  • やっぱりWA.
  • ・・・あれ?
  • ・・・さっき解いたはずのCがWAになってる?

Problem C: Hexadecimal's Numbers

  • どうやらRejudgeが入ったらしい。泣ける。
  • ひたすら生成するループをまわすとき、while(true) を書くのを面倒臭がって REP(i,n) と書いたので n = 1 のケースで回す回数が足りなくなってた。
  • submit. Accepted.

Problem B: Running Student

  • あれここ実装間違ってる、いややっぱり間違ってない、いくらなんでもそんなトラップは無いはず、とか言いながら何度もsubmit. 全部 Case 9 でWA.
  • もういいや。次行こう。

Problem D: How many trees?

  • n 頂点で高さが h 以上の木はいくつある?
  • いつものDPだ。メモ再帰しよう。
  • ・・・なかなか答えが出ない。
    • DPは各状態間の関係を把握するのが苦手なので得意ではありません。
      • ICPCのときはなぜか自分がいつもDP担当になるのだけど。
  • そんなこんなでタイムアップ。
  • 最近はコンテストに出てもぜんぜん問題が解けなくて鬱です。