日々drdrする人のメモ

今日もdrdr、明日もdrdr

JAG夏合宿 2017 参加記

ICPCアジア地区予選に向けた練習も兼ねて、チームIQ1のメンバーである自分とkuwa氏とちゃっくの3人でJAGの夏合宿に参加しました。

2017/Practice/夏合宿/案内 - ACM-ICPC Japanese Alumni Group


9/22~9/24の二泊三日の合宿で、会場は国立オリンピック記念青少年総合センターでした。
今回は、家から会場まで通える距離だったので、宿泊せずに参加していました。

合宿中は計三回のコンテストが行われ、全てチームIQ1のメンバー3人で参加しました。

1日目

朝9時くらいに起きて、ぼけーっとしてたら11時くらいだったので出発。12時半過ぎに会場に到着。
その後、ちゃっくとkuwa氏も会場に到着。

13時からこの合宿の説明を受け、コンテストの準備を行う。
14時からコンテストが開始。

Japan Alumni Group Summer Camp 2017 Day 1 - Japan Alumni Group Summer Camp 2017 Day 1 | AtCoder

3時間11問のコンテスト。
問題は難易度順に並んでいるとは限らないらしいので、チームの方針としてはとりあえず各々が別の問題を読んで、解きやすい問題から解くようにした。

まず、kuwa氏が簡単なJ問題に手をつけ、ささっと通す。

自分は、D,E,F,Gあたりから読み、できそうなH問題から手をつける。
とりあえずX≧Yの場合に絞って、X≧1の時は(X-Y)と一致するまで行って右上に行く、X<1の時は下行って左行く方針で回数を計算してみる。しかし、いくつか特殊なケースがあることに気づかず、WAを出し頭抱える。そこから見逃しているケースを見つけて修正し、なんとかAC。

次に、K問題を考える。
なんか総当りしそう(無理)とか考えてたら、 {\sum_{i \in I}(C_i + G_i) \le \sum_{i} G_i}という式が降ってきて集合Iを貪欲に求めるように実装したらACできた。
K問題を考えている間にkuwa氏がD問題の反射を折り返して考えることで通してくれた。

次にF問題に手を付ける。
F問題をみて、最初の文字から右に文字列のマッチングし、マッチングした最後の文字の箇所から左にマッチングする方針でできそうだと考え、そしてマッチングは、各文字で次に各文字が出現する位置を持っておくことにより {O(|T_i|)}でできそうだと考える(最近解いたARC081のE問題と少し似ていたからすぐ思いついた)。この方針で実装して、少しバグらせながらもAC。
これを解いている間にちゃっくがA問題を通してくれた。

最後はちゃっくと一緒にB問題を考え、BIT使って解けそうだと考えるも時間が足りず終了。kuwa氏はE問題のparseで最後まで苦戦してた。

チームとしては、ADFHJKの6完。自分はFHKの3完。
H問題をきちんと実験せずに無駄に時間を使ったのが反省点。
f:id:smijake3:20170925012526p:plain


その後はオリンピックセンターの食堂で夕食を食べた。数種類のメニューから1つを選択する形で、さらに野菜やデザートを自分でとる方式だった。

その後は問題の解説を聞いて、帰宅した。

2日目

起きて家でのんびりしてたら8時半になってた。すぐ家出て、会場には9時40分くらいについた。ぎりぎりだった。
kuwa氏もちゃっくも開始前に到着。10時からコンテスト開始。

2日目はCodeforcesの"2015 ICL, Finals, Div1"という過去のコンテストの問題セット
Dashboard - 2015 ICL, Finals, Div. 1 - Codeforces
5時間12問のコンテスト。問題文は英語。

とりあえず1日目と同様、3人で分かれて問題を読む。自分はD,E,Fあたりを読み始める。
D,E,Fを読んでむずそうという気持ちになり、別の問題を読む。

kuwa氏はG問題, ちゃっくはB問題に取り組み始める。自分はできそうなL問題から取り組み始める。
kuwa氏がG問題を実装するもWAを出す。自分もL問題で最も多いlaneから人を移して計算する {O(N)}の方針が立ち、実装するもWAになる。L問題を考え直している間、ちゃっくがB問題で困っていたので、問題を見てうまくDPで解けそう、などと議論していた。

このまま0完の状態でお昼になり、弁当を食べていた。午前中は実質座ってお昼食べただけ。

弁当を食べた後、L問題のミスを修正して提出し、1つめのAC。

次にH問題を読み始めるが、英語が読みづらくて苦しむ。
kuwa氏と問題文について少し議論して、方針立ったので実装したが、WAになる。きちんと読むと、問題文を誤読していることに気付き(なんか最初は隣と端っこのfloating leavesに飛べると思ってた)、根本から間違っていることに気付く。その後、考察し直して実装しAC。

kuwa氏は通らないG問題をおいてF問題を考え始めてたので、代わりにG問題を考える。
最初に全ての時計を1箇所に合わせて、N個の箇所に順番にまとめて合わせながら計算するというkuwa氏の方針で間違ってなさそうだったので、その方針で実装してみる。
実装ミスで一度WAを出すも、修正しAC。

チームとしてはGHLの3完。
英語の読解とバグでハマってなかなか通せなかった。二人もハマってたので、もう少し解く手助けをすればよかったと反省。
f:id:smijake3:20170925012602p:plain


この後は解説を聞き、オリンピックセンターの食堂で夕食を食べた。野菜としてそうめんがおいてあったのは謎だった。
夕食を食べた後、帰宅した。

この夜はCode Festival 2017の予選Aがあったので参加。
結果はABCDの4完で152位 (国内51位)だった。もしも本戦行けたらいいなって感じの順位になった。

3日目

7時半起きて、8時ぐらいに家を出発。9時過ぎたくらいに到着した。
その後、ちゃっくとkuwa氏も到着。

Japan Alumni Group Summer Camp 2017 Day 3 - Japan Alumni Group Summer Camp 2017 Day 3 | AtCoder
5時間11問のコンテスト。問題文は英語。

始めは、とりあえずチームで分かれて読む。自分はG, H, Iあたりを読む。いい解法が思いつかなそうなのでパスすることにした。とりあえずkuwa氏が読んでた別の問題の説明を聞き、E問題が解けそうだと思い取り組む。kuwa氏はF問題に取り組む。
ちゃっくはA問題から読み、A問題、B問題と順番に通してくれた。

E問題は積だけのBFSと、積と和両方のBFSの二回をすればよさそうと思い、Pythonで間に合わないことを想定しC++で実装してみる。実装が多くなってつらくなりながらも書き上げるがサンプルがあわずバグる。バグの箇所を調べるために一度、F問題を実装するkuwa氏に交代して考える。ついでにお昼の弁当を食べる。

弁当を食べてから、実装を再び再開しデバッグを行い、サンプルがうまくあったので提出しAC。その後、F問題をkuwa氏が通してくれた。

順位表を見て、多く解かれてたD問題を自分とkuwa氏で考える。先に {2^{2N}}のbitDP解法を思いついたが、間に合うか怪しかったので他にうまい解法がないかを探る。その間にちゃっくがC問題をAC。

D問題のいい解法が思いつかないので、kuwa氏にbitDP解法の実装を頼み、自分とちゃっくはG問題を考える。
G問題の考察を進めるもいい解法が思いつかず。SATやフローになりそうとかいろいろ言ってた。そしてそのままコンテスト終了。kuwa氏のD問題の実装は時間が足りずという感じだった。

結果、ABCEFの5完で、自分はEの1完。
D問題をもう少し早くbitDP解法で実装する判断をしておけば通せたかもという点が悔やまれる。
f:id:smijake3:20170925012626p:plain


この後は解説を聞き、合宿が終わって解散した。

感想など

3回のコンテストを通して、チームメンバーが1つの問題にハマり続け、時間だけが過ぎるみたいな状況が何回かあったので、チームでフォローするようにうまく動くべきだった、という点が一番の反省点でした。

今回の合宿は、早起き+コドフェス予選Aも含めて 3+5+2+5 = 10時間 コンテストに参加、だったのでめっちゃ疲れる3日間でした。それでも楽しかったし、アジア地区予選に向けたいい練習になりました。JAGスタッフのみなさん、ありがとうございました。

あと、各コンテストではkuwa氏が持ってきたUS配列キーボードを使って解いてて、キーの配置が分からなすぎてgdgdして実装つらかったです(特に*, ", 'が打てなくて総当りしてた)。これは常に使って配置に慣れたほうがよい気がしますね...。