Yandex Algorithm2011 Round1

A

• ドミノを並べる
  • いつかの合宿で似たような問題でなかったっけ？
  • 問題文み間違えてた。上2列と下2列で区切って互い違いにするだけじゃん
  • 書いた。pretest AC。

B

• いつも通り問題文が読みにくい
  • Bにしては難しい気が
  • とりあえず解は2部探索できるな
  • 解を固定したら後ろから埋めていくだけなんじゃないの
  • dequeとかを使って書いた。最大ケースを入れるとちょっと遅い
  • CUSTOM TESTでも使ってみるか。
  • 最大ケース入れたら20KB以下にしてとか言われた。ひどい。
  • もういいサブミット。pretest AC。

C

• 木の確率の問題
  • 問題文が無駄に長い。
  • ええと、要するに各リーフについて期待値を求めればいい？
  • 各リーフの期待値はノードを順々に上がっていけばそこそこの速度で求めれそう
  • ちゃんとしたオーダーで書くのめんどい。もっと楽できんか。
  • 木を作らずrootからその葉の右までの葉の合計とか求めればいけそう（←間違い）
  • めんどい。書いた。pretest WA。なんでだ終わった。

結果

256位。なぜかオレンジ色になった。Cはまじめに書いた方が短かった。