hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

JAG 夏合宿 2018 参加記

初めて JAG 夏合宿に参加しました。同じ大学からは four-t のチームメイト (rsk0315 君と TAB 君) と waku 君も参加しました。以下、雑に記します。

0 日目

札幌から東京まで移動した。なんか自分が離陸した後に新千歳行きの電車が止まったらしく、わりとあぶなかった・・・

無事成田空港に着陸し、その場で本日の分の宿を取る (は?) なんとか新宿の宿が取れてよかった。計画性を身につけたい。

1 日目

オリンピックセンターに集合する前に four-t の愉快な仲間たちと昼食に行った。確かカツ丼を食べたような・・・

ご飯を済ませてオリンピックセンターに向かう途中、いつもの人々 (TL で限界をしがちな人々) がいたので一緒に会場まで行くことに。TAB 君が道案内のプロだった。

ガイダンスがあった後に自己紹介があった。名乗るだけで笑いがおきるこたつがめしゃん

チーム決めの時間があったがすでにチームが決まっているのでおしゃべりをする。そうこうしているうちにコンテストが始まる。1 日目は海外リージョンの国内予選の問題だったようです。

チーム戦の時は TAB が A を、rsk0315 が B を、自分が C をまず読むのが固定化されているので、今回もそれにしたがって読んでいった。C 問題はいもす法を知っていれば解けるやつだったのですぐ解けた。A も B もすぐ通ったので、3 完した時点で一瞬 1 位になっておもしろかった。

D は何すればいいかはわかるけど実装が大変・・・という感じだったが rsk0315 が 「list で常勝w」 とか言っていたので書いてもらった。通った。はいプロ

この辺で E を TAB と一緒に解くが永遠に通らなくて悲しくなった。その間に、不可能に見えていた F を rsk0315 が頑張って考察して通していた。凄いなあ。

結果は 5 完でした。自分 1 人だったら 3 完で終わってそう、チームメイト様々でした。

コンテスト後に解説があって、その後は部屋に移動。今年は 3〜4 人で一部屋を使うようで、 algon さんと imulan さんと一緒の部屋になりました。

この日の夜に AGC があって、談話室で参加。C が解けたためレートが上がって嬉しかった。

2 日目

Writer が豪華なセットでした。

A は若干詰まっていたらしいので見る。 109 + 7 ずつ増やして全探索すれば良さそうということがわかったのでそれを伝えて書いてもらう。通った。うれしいね。

B も詰まっていたらしいので見る。1, 5, 10, 50, 100 円玉を使うパターンはとても少ないので全探索すれば良いことがわかったので書く。通った。うれしいね。

C は見たけど数学が壊滅的な自分には解けないのでチームメイトに解いてもらう。その間に他の問題を見てみたが、なかなか虚無で・・・ (この後 3 時間くらい無が訪れる、考察はしていたけど)

H は prefix の包含関係による重複数え上げをどうにかしたい気持ちになったので、Suffix Array と Rolling Hash を使ってどうにかする解法を思いついたので書く。通る。やったね。

E も解法はだいたい思いついたが高速化部分がどうも思いつかない (bitset 使ったけど TLE を食らった)。終了 15 分前くらいに FFT で行けることに気づいたけど時既に遅し、あまりにも時間が足りなすぎて終了。悲しいなあ・・・。

この日は 4 完でした。E は FFT もっと早く思いついていたら確実に解けていたので、本当にもったいない。こういうミス無くしたいですね。

3 日目

この日は JAG のセットでした。典型詰め合わせみたいなセットで割と好き。

A がなんかつらそうだったので見る。解法の確認をして落ち着いて通した。B は全く見てないけど rsk0315 が通してた。C はよくある DP をやれば終わりなので書いて通した。

この後に何をやるかは少し迷ったが、順当に順位表で解かれているやつを中心に考察をした。まず J は TAB と一緒に考えたところ偶奇で分けて考えると素直に解けることがわかったので自分が書く。少しバグったが通った。次に I は自分が J を書いている間に TAB ・ rsk0315 が大体考察を終えてくれていて、実装時に自分も少し手伝って通した。

この時点で G はあまり解かれていなかったが、なんか解けそうだったので考察していた。前から見ると今考慮している数字が何の位なのか扱いづらかったので、後ろから見ていく DP をすることにした。実装方針はかなり気をつけなければならないが、 TAB が条件を簡単にしてくれて助かった。ちゃんと紙で考察したのもあって一発で通ってうれしいね。

終盤になって、他がよく通している F が残っていたので通したいねーという気持ちになった。実験してみると条件はだいたい見えるが例外があるのかよくわからなくて怖い。とりあえずわかっている条件を全部書いたら通った (えぇ・・・) これは反省なんですが F を通すのが遅すぎで、もっと早くに実験すべきだと思った。これは自分の戦略ミスです。

総括

3 日間とても短かった。あと一週間長くても良いくらいだった (ホンマか?)

今回思ったのは長時間コンテストになるとライブラリの豊富さとか、そのへんの知識が結構要求されますね。もっと知識をみにつけていきたい。

ちゃんと復習もしつつ、明後日の会津合宿の準備もしつつ、精進していきたい!!!