TCO12 Round 2C 参加記
TCOに参加しました。Round 3進出は修羅の門なのですっぱり諦め、レート上昇を目標に挑みました。
結果はこちら
順位 | 得点 | レーティング | |
---|---|---|---|
539th | 0.00 | 1560 → 1506 -54 | |
300 | 500 | 900 | Challenge |
未提出 | 未提出 | 未提出 | +0 / -0 |
すがすがしいほどの惨敗でした
辛うじて黄色に残れました
開始前
配点が300 500 900の変則と知って嫌な予感
75分フルを300に注ぎ込むノリで行こうかなと考える
開始
300を開く
ふむふむ、TSPを捻った問題か
入力は・・・何これ?
んー、あーthousandsは道のコストの1000の位を表してるのか
hundreds, tens, onesもそのノリか
意地悪な入力だなぁ
コストを整数の2次元配列に直す
さて、肝心の問題をどう解くか
コストを変えるのは1回だけ
訪問した頂点集合Sと、現在頂点vから、どの辺をどのコストに変えれば意味のあるコスト変更になるかは決まりそうだぞ
えーと、まず何もコストを変えない場合にどこの頂点へ行くかを計算するか
で、コストを変える場合はどうすっかな
計算で求めた頂点を除いたら、どこへ行くかを計算するか
ん、未訪問頂点が1個の場合は例外処理しとくか
えー、で、この(S, v)の状態からは多分、計算で求めた頂点2つにしか訪問できないはずだ
1個目の頂点のコストをどう変えたら2個目の頂点に行けるか
1個目の頂点へのコストが9999だったら2個目行けないな
んーあー
場合分けを考えて実行して、合わないサンプルと見比べながら条件を追加していく作業
どんくらい時間たった?
残り20分くらい
粘れば解けるはず、0完は避けたい
むむー
サンプル合わないーー
ガリガリガリ
残り90秒
これは完全に自分オワコンですね
終了
コンテスト終了
何やら900の問題でゴタついているようだ
でもratedなのは間違いないらしい
うぬぬー
TCO Round2難しい
また来年リベンジしたいなぁ
結局300は、厳密にコストをどう考えるかではなく、辺のコストを-1、9999にするなどの、変化が生じうる可能性を全ての辺について考えれば良かったらしい
なるほどー