読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

ACM-ICPC 2015 国内予選参加記

6/26に参加してきました.今年で2回目の出場です.
結果は4完,全体20位で大学内1位なので地区予選進出だと思います.
去年はチームメンバー違いますが0完だったのでとても嬉しい.

以下チームメンバー略

  • 自分:B3
  • N: B3
  • T: B4

本番前打ち合わせ

A問題を自分が担当,BをN
CとDの早く書けそうな方を自分かTが片付けるという簡単な打ち合わせをしました.

簡単な経過

0:00 開始

問題文を印刷.
A問題を自分が読み始める.
最大化する優先順序とか頭でごっちゃごちゃになって理解に5分ほど時間をかける.

0:15ぐらい Aのコード完成

この時点でA問題目標時間の3倍で死にたくなる.
そしてVisual Studioのビルドがうまくいかないトラブル発生.プロジェクトを作り直す.

0:20ぐらい A問題提出,1回目と2回目のソースが違うと怒られる.

ソースコードを間違えて更新してしまったのかもしれない.原因はよくわかっていない.
このペナルティはないみたいなのでセーフ()

0:22ぐらい A問題AC

自分がいろいろ死にたくなってる間にNがBの疑似コードを完成.Cもほぼ解ける状態らしい.ますます死にたい.

0:35ぐらい B問題AC

実はB問題の内容すら知らない.
この間に自分はD問題を読み始める.読み始めて最初に出た声は「楽しそう」
TがC問題の疑似コードを完成させていたので託す.Cの内容も知らない()

0:50ぐらい C問題AC

E,F,G問題をチラ見する.すぐ捨てる.
D問題がDPっぽいと自分の直感が騒ぐ.
このとき店の回る順が自由だと勘違いしていた.

1:00ぐらい

勘違いをTに指摘される.
ここでお店を選ぶ選ばないの2通りなので両側全探索も少し考え始める(すぐ断念)

1:05ぐらい

これはDPだと神のお告げが下る
DPをするためのいくつかの仮定を立て始める
状態を,(今何番目のお店)x(持っている100円以下の小銭)

  1. 各状態において,できるだけ取得500円を多く,そのうえで支払金額をできるだけ小さくという貪欲が適用できる(真)
  2. 小銭の内訳は気にしなくていいのではないか(真)
  3. 2が成り立つなら持っている小銭は1000未満なのではないか(偽)

1は確実だと思います.
多分一番の胆は2,どうやらあっているっぽい.

1:40ぐらい

自分があと20分だと勘違いする.
あと1時間以上あると聞いて落ち着き,コードを書き始める.
同時進行でTがEを考え始める.

1:55ぐらい D問題WA

合っていると思っていたのでコーナーケースがないか入出力の確認を始める.テストケース長すぎ.
TがEを書き始める.

2:20ぐらい

コーナーケースが全部正しそうなので闇に落ちかける
神のお告げで仮定3が間違っていることに気づく.
小銭は最大でお店x500まで持つ可能性がある.
同時にTがEの解法を間違っていたことに気づき自分にPC交代.

2:45ぐらい D問題AC

計算量が結構ギリギリでデバッグモードのままだとなかなか結果が出ない.
Releaseモードに変えたら一瞬で答えが出た.流石.
この時点で国内予選突破がほぼ確定したので問題を解くのを諦める.疲れた.

3:00 終了

お疲れ様でした.
マジで疲れた.

ほとんどの時間をDに費やした上にB,Cの内容を知らないので書く内容に偏りがあります.