Hatena::Grouptopcoder

思考錯誤 - By evima

プログラミングコンテスト参戦記。本番中のメモを公開します
過去のコンテストへの出題一覧 / TopCoder / Codeforces / Twitter

2013-06-16GCJ 2013 Round 3

あまりにも楽しかったので半年ぶりに記事を書きます。

f:id:evima:20130616062143p:image



  • スタート!
  • とりあえずAを読む
[A:概要] ルーレット。0~36の各番号にお金を賭ける。当たると36倍になって返ってくる。
しかしイカサマがされており、玉は賭けられた金額が最も少ない番号に必ず入る
(複数あるならその中から等確率でランダムに)。
他の人が賭け終わった後で、所持金の範囲でベットを置くときの利益の期待値の最大値を求めよ。

(問題文)

  • SmallとLargeの違いが分からない
    • 所持金や既に置かれた金額が違う (Small:1000 / Large:10^12) けど変わらなくないか?
  • 方針:
    • とりあえず0~36の番号を賭けられた金額が少ない順にソート
    • for each i in 1~36 do:
      • 0~i-1だけをベットする対象とする
      • まずは0~i-2にベットして、0~i-1のベット額を同じにする
        • 所持金が足りなければ失敗
      • その後、0~i-1に所持金が許す限りできるだけ多い金額を均等に賭ける
        • ただしiに置かれている金額以上にならないように
  • 多分これでいいだろう
  • 簡単そうで書いてみると意外とややこしい…
  • 開始9分半でランキングに最初の得点者が現れる、がAではなくD-Small
  • その後少しずつA-Smallの提出が出るが不正解だらけ
    • Aの方がDよりattempt数は多いが、Dは確実に正解されていてDの方が少し正解者が多い
  • 21:23(経過時間)、A-Small提出
    • Incorrect
  • えええ…いや考えてみればこれでいいならそんなに不正解が出るのはおかしいなあ
  • でもどこがおかしいんだ?
  • 0~i-1に均等に賭けない方がいいことがある…?
  • わからない
  • 気晴らしに一旦Dを読む(概要は後で)
  • Smallは N<=20 だから普通にDPか…Aが終わったらやろう
    • (ペナルティの形式がCodeforcesとかと違うので今すぐやる必要はない。やってもいいが)
  • Aに戻る
  • やっぱりさっきの方針がどんなケースでダメなのか分からない…
  • 正解者数が増えるスピードから判断する限り、みんなかなり苦戦している模様
  • …わかった
  • 本番中のメモ

f:id:evima:20130616101153j:image

(意味は察してください)

  • やっぱり均等がベストとは限らなかったか…
  • さっきのi(1~36)のループの内部に以下を追加
    • for each j in 1~i-1 do:
      • さっきと大体同じ賭け方をするが、i個のうち後ろのj個の金額を1増やす
  • 今度こそ正しいはず…
  • やっぱり結構ややこしい…サンプルを通すのに苦戦
  • 1:05:03、A-Small再提出
    • Correct!
  • ふう…Smallの特性を全く活かしていないのでそのままLargeも提出(1:05:35)
    • もう1時間以上経ってるのに93位に。まあこの順位ならこの時間でもそこまで遅くないかも?

  • 先ほど読んだDに移る
[D:概要] 観覧車。ゴンドラがN個あり、いくつかには既に人が乗っている(降りない)。
ランダムなタイミングで人が1人ずつやってきて、空いているゴンドラを待って料金を払って乗る
(乗ったら降りない)。料金は、人が来て最初のゴンドラに乗れたらNドル。
それが埋まっていて次のに乗れたらN-1ドル。…N-1回乗れずN個目でやっと乗れたら1ドル。
全部のゴンドラが埋まるまでに払われる料金の期待値を求めよ。

(問題文)

  • 前述の通りSmallでは N<=20 なのでやるだけ
  • 1:13:20 (A-Large + 7:45)、D-Small提出
    • Correct!
  • なんじゃこりゃ…AどころかRound 2のどの問題よりも圧倒的に易しかった
  • 44位に。ちょっと高すぎないか…もしかして25番に入れる可能性がないこともない?
  • Largeは N<=200 で解ける気配が全くしないのでBかCを選んで移ろう
  • B-SmallとC-Smallの正解者数は大体同じで、Bの方が少し多い
    • しかしB-Smallはかなりの不正解が出ていて、C-Smallはほぼ確実に正解されている
  • Cに移る

[C:概要] 有向グラフが与えられる。各辺のコストは正確には分からないが、
各辺について整数aとbが与えられ、a以上b以下であることは分かっている。
また、頂点1から2までのパスが与えられる。
これは頂点1から2までの最短路になっている可能性があるだろうか?
もしないなら、絶対に最短路の一部にならない辺のうち最初のものはどれか?

(問題文)

  • Smallではグラフの頂点も辺も20個以下
  • 「a以上b以下」は単に「aまたはb」ということにしていい気がする
    • 辺は20個までなので、各辺がaかbのどちらになるかの 2^(辺数) パターンを全て試せる
  • 方針:
    • パスの最初の辺から順に、その辺までが最短路の一部になる可能性があるか判定
    • for each pattern in 0~2^(辺数)-1 do:
      • 頂点1から2までの距離と、
        (パスの今見ている辺までの距離)+(そこから頂点2までの距離)が一致するか判定
        • 一度でも一致すれば、この辺までは最短路の一部になる可能性がある。次の辺へ
        • 一度も一致しなければ、この辺は絶対に最短路の一部にならない。この辺を答えて終了
  • 最短路を求めるのはワーシャルフロイドが楽だが…
    • 10 * 2^20 * 20^3 の5重ループに
  • でも本当に800億回ループが回ることはあまりなさそうだし、4分弱で10ケースしかないし…
  • Smallは失敗しても再チャレンジできるんだし、やっちゃえ
  • 書き上げたらサンプルを一発で通ったので入力をダウンロード
  • 案の定ケース2が5秒たっても終わらない
    • だが200秒くらいで10ケースさばけばいいんだ、大丈夫!
  • 10ケース中7ケースは一瞬で、残り3ケースは19秒、21秒、14秒で、合計54秒で終了
  • 1:43:34 (D-Small + 30:14)、C-Small提出
    • Correct!
  • なんとコンテストの最後の3分の1の時間帯に27位に

f:id:evima:20130616081108p:image

  • うそ・・・マジで・・・オンサイト行けちゃうの・・・?
  • しかしC-Largeに今の方針は全く通用しないし、解ける気配も薄い
  • Bに移る

[B:概要] 平面上にN点が与えられる。この中から任意の数の点を結んで得られる、
自己交差しない多角形の面積の最大値をSとおく。
N点全てを頂点として用いて、面積がS/2より大きい自己交差しない多角形を作れ。

(問題文)

  • Smallでは N<=10 だから nPr(N,N) + nPr(N,N-1) + ... 通りを全て試すだけか
    • 自己交差しないかどうかは、本来隣り合わない辺同士が接触してないか確認すればOK
  • あれ、解なしのときはどうするの…?
    • 最近Codeforcesでよくこういう問題が出て、基本的には
      簡単な必要条件が満たされていれば解は存在する。今回は必ず存在するのか
  • コンテスト中に幾何の問題を解くのは久しぶりだな…
  • まあSpaghetti Sourceをほとんど丸写ししたやつをコピペするだけだし問題ない
  • いたって普通の全探索なのになぜかSegmentation Faultやサンプル不一致を連発
    • 実はあまりこういうのを書かないので慣れていないことが露呈
  • 2:18:06 (C-Small + 34:32)、B-Small提出
    • Incorrect
  • えーなんで…?
  • このとき順位表の2ページ目(21~40位)はすでに55点(A,C,D-Small)で埋まっていた
    • B-Smallを通しても46点。やはりオンサイトは夢だった
    • しかしこれを通さずに終わるわけにはいかない…!あと10分で必ず通す
  • coutデバッグの結果、原因はテストケースが複数あることだった
    • なんと、2つ目以降のテストケースで「任意の数の点を結んで得られる面積の最大値」が
      0になってしまうという爆笑バグを仕込んでいた
      • テストケースが1つなら、グローバル変数は0で初期化されているので問題ないが…
  • そういえばさっきは実行時間が短すぎたな…
    • 面積が正の多角形を見つけたら無条件でそれを答えていたのだった
  • 残り3分半。本当はさっき使った入力をもう一度使って、
    本当に出力が変わったか確認したいところだが…
  • 時間がないので入力をダウンロード
    • 制限時間は4分のはずだが、もうコンテスト自体が残り4分を切っているので
      タイマーにはコンテスト自体の残り時間が
  • 実行!
    • やっぱり一部のケースで1.3秒とか1.6秒とかかかる…速く!
  • 25秒で全100ケースの処理が完了
  • 2:27:34 (C-Small + 44:00)、B-Small再提出
    • Correct!
  • 62位に。やっぱりオンサイトは無理だった…でも頑張ったよ

  • BCDのSmallとAの暫定46点で終了。Large採点前の時点で暫定68位
  • 数秒後に採点終了

f:id:evima:20130616092759p:image

  • 50位!!
    • トップ25には入れなかったが、次の25人には入れた…大満足
  • ちなみに去年は…

f:id:evima:20130616094137p:image

  • 提出されたB,CのLargeが大量に落ち、オンサイトのボーダーは僕より2点上の「48」だった
    • 2点といっても、BCDからどれか1つLargeを通さないとダメ
      • ご覧の通り僕はBCDのLargeには手も足も出なかった。別に惜しくはない
  • それに50位っていうのも表面上のものかも…
    • 例えば「Bを捨ててC-Largeを取りに行って散った37点の人」に内容で勝ったとは思えない
      • もし「46点以上で通過、45点以下は脱落」というルールだったら、
        かなりの人が46点を取れたはず
  • とはいえ、少しの間だけ夢を見させてもらった
    • 競技プログラミングでここまで胸が躍る体験をしたのは初めてだった
  • ここまで楽しめたのには、GCJのルールの良さが貢献しているところが大きいかも
    • もしSmallがなかったら、B: 無理 C: 無理 D: 無理 となってあまり楽しめなかったと思う
  • 楽しかったよ、ありがとうGCJ
    • 来年は覚悟しとけよLargeども…

To be continued to GCJ 2014.