第3回 RCO日本橋ハーフマラソン 本戦 (オープン) A問題だけに4h注力して参加してみた

Quiz

https://atcoder.jp/contests/rco-contest-2019-final-open/tasks/rco_contest_2019_final_a

結果

  • 時間内 0点(一部WA)(2019-03-02 18:00:00)
  • 時間が過ぎてACしたとき 587618点 (2019-03-02 18:33:24) 中央値くらい
  • やり残しも実装 798499点 (3/3 AM4) 結構良い点数

やったこと

  • まず右まで50枚めくり、情報を得る
    • 30枚くらいの方が中央に近いから動きやすい?、ということはなかった
    • ローカルでどちらも試して最終スコアで評価
  • 近いペアを取っていく(回転重視)
    • 2つ取りに行くときの移動距離が最小
  • 隣に不明点があるならめくっておく(コスト1のため。効く)

Submit (798499点)

https://atcoder.jp/contests/rco-contest-2019-final-open/submissions/4435574

実装の工夫点

  • 訪れる順にqueueに入れていく
  • インタラクティブ形式なのでprintデバッグできない。ログに吐く
  • ログでは現在の知っている情報や位置を可視化する

感想

  • 時間は過ぎてしまったが、思いつく解法で結構良い得点まで行ける
  • 実装力(バグ無し・実装速度・コーナーケース)が効いてくる
  • バグがあっても得点は出てしまう
    • バグってて低いのか、方針が悪いから低いのか
  • 家でやったが、日本橋会場だと周りが気になってしまうだろう
  • 4時間走った後はフラフラ

問題について

  • 設定がすごく分かりやすいのに工夫点は多いし差が出る、良い問題

少しのテストケースでWAになる時に解決する方法

  • seed値を変えていくつかローカルテストしたらWA判定が再現できた

他の人の解法Tweet A90万点

https://twitter.com/rickytheta/status/1101770598567428099