2011-01-29

■ [SRM]SRM495 23:21

2011-01-27 25:00-（JST）

http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14424&rm=307047

自分が参加するのは久々のrng回

Level	タイトル	試合中	あとで	ひとこと
275	ColorfulCards	AC 10min	-	思いつけて良かった
500	CarrotBoxes	Compiled	-	グラフは苦手意識
975	StrangeElevator	Opened	-	500よりも望みあったかもしれない

• Coding
  • 275
    • ぱっと見DP？　と思ったけどちょっとややこしすぎる
    • 各位置で可能な最小の場合と最大の場合を調べて、両者が一致する⇔一意に決まる、とひらめいた
    • 条件を満たす例は必ず1つはあるのだから境界条件は考えなくて良い
  • 500
    • グラフか…
    • 各ノードから辿っていって開けるのはどれかを記録して、親ノードがあればそれにマージしていって枝が何個できるかという感じ？
    • テキトーに作ってみると全然違ったので真面目に考える
    • ちゃんと考えると、これは強連結成分をひとまとめにする、ということなのだと理解する
    • そしてトポロジカルソートしてやるとなんかうまくできそう
    • しかし強連結成分分解を書いたことがなかった！
      • 正直なところ、あまりいろんなアルゴリズム知らなくても数学ゲーさえちょこっとできればTopCoder（の"Algorithm"部門！）で赤にはなれちゃうのです…。良いことか悪いことか
    • 蟻本を開いて即席で書く。蟻本さまさまである
    • トポロジカルソートの先頭から未開封の箱が残り1つになるまで順に開いていくとき、何個開かないといけないか数える
    • しかしサンプルが合わない
    • トポロジカルソート作るときの順番によって必要な開封個数が変わることがある
    • つまり「残り1つになったとき」という終了条件をうまく扱えていない。確かにサンプルのそのケースでは間違う
    • 終了3分前に「最後にどれを残すか全通り試せばよい？」と思いついたがもう間に合いません
    • やっぱり正しくないコードを書き始めてしまうのは完全に負けルートだなあ
    • 500で早解き競争になることはないのだから、見切り発車で書き始めるのではなくノートにメモったりしつつじっくり考えるべし。今回は全部脳内でやっちゃってた
  • 975
    • 一応開いただけ。問題の理解もしてない
• Challenge
  • 275はいろいろなコードがあるがサンプルが強そうなので何もできない
  • 500をgreedyでやっている人を発見。しかし自分がeasyしか解けてないのと本当に落ちるかちゃんと検証する時間がなかったのとでチャレンジせず
    • もし成功していてもあまり順位変わらなかったので結果的に自重して正解
    • ほとんどの場合で「迷ったらチャレンジはするな」が良い戦略だと思います
      • 例外は、自分が1問は確実に正解している自信があって、かつ順位表で自分の下がまばら・上が僅差　というとき
      • あと、トーナメントで「これを撃墜しないと次のラウンドに進めない」という場合もある
• System Test
  • 通った

結果

• スコア：245.73 + 0.00 + 0.00 + (50*0-25*0) = 245.73
• 順位：73位/697人
• レート：2322 -> 2334

highestへじわり接近