JAG 2015 夏合宿
今年は2泊3日の合宿2本立てだった．
2年前の1人参加とは違い，チームnocowとして参加しました．自分はDay1からDay3のみ
チームメンバー
@osrehun
@icchyr
@xthexworldx
Day1
10:00〜17:00 研究室のミーティング
その後，特急あずさの予約をしてからオリセンへ
18:00 オリセン着
19:00〜22:00 打ち上げ
とにかく狭いので，あまり交流できず... (料理も少なかった)
Day2
早朝に地震があったので6:00前に起床
朝ごはんを食べる．(チームメイトの1人が朝食TLEしたことを知る)
開始前にネットワークトラブルが発生する．(チームメイトに任せる)
10:40〜15:40 コンテスト(筑波大+sugim48 セット)
結果から書くとA,B,C,Dの4完
A:
最初にチームメイトが取り組む
まず，分子と分母のGCDで割って既約分数a/bにする．そのままbを出力する．WA
バグっているっぽいので自分がコーナケース探す．1/4とかいうあからさまなケースが見つかる．
b=素数pの累乗ならば，pを出力すると書いて提出する WA
詰まっているっぽいのでBを先に通した後に
1/18というケースに気づく．
bを素因数分解して，素因数を掛け合わせて出力すると書いて提出する 2AC
B:
自分が取り組む
問題を見た瞬間にヨセフス数を思い出す．
Tech Tips: ヨセフス数（Josephus Number）の求め方
1回の処刑による番号の変化を関数の写像として表せば良いと気づく．
答えの数が大きいなと思い二分探索だと思って書く．
実行したらサンプルケースが通るので提出 1AC
C:
A,Bを通したあとにチームメイトに投げる
自分は他の問題を読んでいく．
最初にDPかと思ってヒントを投げたけど，違うっぽいのでdfsで書いていく．
遅いので，枝刈りをする．TLEとWAが多発
最終的に取り除くABC以外の文字の種類が3種類の時を枝刈りしてACしているみたいだ．4AC
D:
最初にチームメイトが取り組む
解けそうだと思ったので，自分が読む．
暗い部屋の数の上限が16なのが気になるなと思い，bitDPを思いつく．
暗い部屋に人がいるかどうかを状態として持って状態遷移を書いて，ループで回す．
DPの過程で閉路が生じていることに不安を感じながら出してみると，WAとTLE
不安は的中したかつ状態遷移の作成をサボりすぎたので、bfsできちんと書く．提出 3AC
G
グラフを縮約すれば解けそうと思い，なぜか強連結成分分解を書く．本当は二重連結成分分解を書くべきだった．
そして，縮約したグラフの頂点に属している頂点数でマージする．
最後に木DPを書く．WA ４ケース通らなくてTime Over
2年前の最大2完に比べると成長したなと少しは実感できた．
チームメイトはあまりに解けなくて辛いと言っていた気がする．
このセットは実験してみないと分からないことが多いなという感想だった．
状態数の削減の仕方がとても面白い．
部屋に戻って，K問題の駒空逆について少し考えてみるとサンプルケースは分かった．
いくつか考察したものを提出すると半分くらい通ったけど，致命的なケースがあってよくわからず放置
Day3
朝ごはんを食べる．(チームメイト全員ACした)
10:00〜15:00 コンテスト(tourist セット)
A~C,D~F,G~Jを分けて最初に読む．
B
AOJ 0299が類題だなと思いながら実装する．1AC
J
問題を読み直し，J問題解けそうだなと思い式変形する．手詰まり(ここでbruteforceすると気付けなかった)
H
その後，チームメイトにH問題を任せる．残り1時間でH問題が通らないので自分も加わる．書き直して，修正すると通る 2AC
E
自分はCodeFestivalで見覚えがあったE問題に取り組むけど，バグが多くて時間切れでした．
解説を聞くと，手をつけた順は間違っていないみたいだ．(A,D,F,I問題は解ける気がしない)
touristセットは要復習，ロシア怖い，rngさん面白かったです．
夕食をとって帰宅．
帰宅後にCとJを通す．
Day 4
あずさの車内から参加しようとしたけど，電車酔いしたのでやめる．
(Day 4〜Day 6)
諏訪湖で2泊3日の研究室合宿に行った．楽しかったです．
感想
夏合宿の問題セットは考えさせられる物が多くて非常に楽しめました．
あとできれば，参加者やスタッフと交流する機会を増やしてほしい．
あと，宿泊メンバーとの交流が少なかったな...
