GigaCode 2019
今回はオンラインではなく,Yahoo! JapanのLODGEで開催されたオフサイトイベントでの参加.こういうイベントに参加するのが久々過ぎて,初対面の人とどう会話するか本気で困ってしまうというコミュ障っぷりを発揮した.それでも同じテーブルにいたメンバーのうち二人は社会人で,まだ話しやすかったのが救いではあった.
今回のイベントの参加者は高校生・高専生・大学生がボリュームゾーンで,最年少は中学2年生という感じで平均年齢はかなり低めだった.一方で,40代で青コーダーという方も参加されており,自分もまだまだ頑張らねばならぬと思った.
コンテストでは青,橙,黄のガチ勢がものすごいスピードでACしまくってて,「あ、アイツら・・・一体どんな動きをしてやがるんだ・・・?!」みたいな感じになった. そういうのを間近で見るだけでもいい勉強になったし,LTはどれも面白かった.一人OpenMPの話してる人がいたので,もし次回があったらMPIかGEMMの話でもしようかなと思った.
今回のコンテストは出題が8問,制限時間が3時間で,集中力を維持するのが大変だった.開始から2時間ぐらいで一度完全に集中が途絶えてしまい「もうダメかな」と思ったが,最後の10分ぐらいで通せなかったサンプルを通して部分点を追加したりできて,「一見お手上げでも最後まで諦めなければスコアを伸ばせることもある」ということを体験できたという点は良かった.
結果
- ペナルティなし,部分点ありなので遠慮せずに出しまくるという頭の悪い戦法をとって部分点を稼いだ
問題 | ACまでに要した時間 | AC | WA | TLE |
---|---|---|---|---|
A | 15:42 | 1 | 1 | 0 |
B | 4:37 | 1 | 0 | 0 |
C | 17:02 | 1 | 1 | 0 |
D | -(部分点28点) | 0 | 5 | 0 |
E | -(部分点15点) | 0 | 7 | 0 |
F | -(部分点13点) | 0 | 3 | 0 |
スコア | 全体順位 | オフサイト順位 |
---|---|---|
356 | 259 | 確か31ぐらいで,これは経験者枠の中だとケツから2番目か3番目..まだまだ未熟である. |
A
- 瞬殺かと思ったら問題読み違えて一手WAした..
- A問題でも最低サンプルは通さないといけないと深く反省した.これがABCなら詰んでた.
B
- 簡単なシミュレーションなのでそのまま解けば良い.ぐるぐる で解ける.
C
- longで定義するべき変数をintで定義して1サンプル落として一回WA食らった
- 計算途中に一個でもintでは足りない変数がでてきたら整数は全部long longで定義するぐらいの安全策を取ったほうが無難かもしれない.この辺の定石がまだ分からない.
D
- ACは無理なので,H=1の場合に限定して部分点を取りに行った.
- 個人的にはかなりムズいと思った.
- 完全回答としては二次元累積和を使って事前に計算したあとに条件に合うかどうかをチェックすれば良かったらしいが,まだ完全には理解してないので後で考える
参考回答
E
- ACは無理なのでH=1の場合に限定して部分点を取りに行った
- H=1の場合は「乗り換えが必須かどうか」「乗り換えが必須でなく,乗り換えが可能かどうか」という2つの分岐で解くことができる
- H>1の場合は特定のポイントまでの時間を最小化する(もしくはスピードの合計値を最大化する)DPを行う必要があるが,相変わらずDPが苦手なので実装できそうにないと判断した
参考回答
F
- 感覚的には分かるが定式化できそうにないなと思ったので大人しくH=1の場合に(ry
- H=1の場合は「連続した何もおいてない床」の個数を数えるでFAであるが,二次元になるとどう解くのが良かったのか..正直今でもよくわかってないのでゆっくり考える