あったこといろいろ

ほぼ自分用備忘録です。

JAG夏合宿2016参加記

9月の2日~5日にかけて開催されたJAG夏合宿に参加しました

1日目 東京到着・ガイダンス

夜行バスで早朝に到着したので、yurahunaさん,37dbyeさん,T.M君と新宿のロッテリアでたむろしていました。

ガイダンスまでは時間があったので、模擬地区2012をyurahunaさんと一緒に解きました。
結局二人でDictionaryとMedian Treeを解き、Stack Mazeが解けず。

以下問題のネタバレなので白文字
「Median Treeは半信半疑で最小全域木を張ったら通ったのですが、解説を見るとキレイな証明が書いてあり面白い問題だと思いました。」

2日目 Central Europe Regional Contest 2014(CERC2014)

チームJag2015Mogichiku( @konjo_p + @nola_suz + @Yazaten )で出場しました。
CERCとはヨーロッパの激戦区の地区予選らしい。

寝坊でチーム決めにTLEしたのですが、2人で出場予定だったkonjo_pさんとnola_suzさんのところに入れてもらうことができました。


開始直後はA~Cをそれぞれ読む方針で僕はB問題を読む。
今いるところから見える一番近い山の斜面はどれですか みたいな問題だったけど斜面の数が結構多くて放置。
あとで聞くと実際ヤバい問題だったらしく良い判断だった。

その間に@konjo_pさんがC問題*1の解法を思いついたらしく書いてもらう。
なんか合わないらしく解法を確認していたが、実装のミスが見つかり無事AC。

その後H問題*2の概要をnola_suzさんに聞き、「なんか組み合わせをDFSで列挙して二分探索でホイみたいな感じですね」と言ったらnola_suzさんが実装をしてくれてAC。(実は列挙しても組み合わせは高々1000以下なので二分探索は不要だった。ごめんなさい。)

その後、僕がD問題*3、他の2人がI問題*4をAC。

この段階で解けそうな問題はF*5かL*6で、Fはチームメンバーが実装してくれそうな感じだったのでLを考える。
区間DPして欲しそうな制約だったがイマイチ区間の持ち方がわからず、いろんな貪欲とかを考えていた。

Lは結局わからないままコンテスト終了だったが、僕を除く2人が熱意でFをACしてくれたので8位といういい感じの順位を取れた


Lは距離と時間を要素にした二次元平面を考えると、「一番遠くで発生する攻撃は必ず打たなければならない」ことからその左側と右側の2つの区間に綺麗にわかれるのでいい感じに区間DPができたらしい。なるほどなぁ

3日目 JAG 模擬アジア地区予選2016

チームBlackSeven( @shora_kujira16 + @yurahuna + @Yazaten )で出場しました。
( 由来はしょらーさん(@shora_kujira16)の言った「NAのB棟7Fはブラック」というローカルネタ )
LINEさんのオフィスを借りての開催で楽しかったです。


2日目同様、開始直後はA~Cをそれぞれ読む方針で僕はB問題*7を読む。
よくあるBFSなのですぐ解ける。A問題*8がACするのを待って連続AC。

C問題*9をyurahunaさんと考えている間にしょらーさんが「Eはこれハッシュでしょ」と言って提出。WAを食らったので諦め、D問題*10を考えてもらう。
するとここでE問題にリジャッジがかかり時間差AC。

D問題の条件を満たす括弧列には規則性があるらしく、いい感じに生成するプログラムをしょらーさんに書いてもらう。実装ミスでWAをもらいつつAC。

F問題以降はわからなかったのでC問題をセグ木を使ってyurahunaさんとペアプロ。
時間ギリギリに「サンプル通った！よっしゃいくぞ！」と提出したらめっちゃWAが出て終了♨


模擬地区は解説を聞くと「確かに〜〜」となるような問題が多く面白かったです。

4日目 2015-2016 XVI Open Cup

チームMILK_TEA( @osrehun + @satashun + @Yazaten )で出場しました。
( その辺にミルクティーのペットボトルがあったのでこうなった )
KLABさんのオフィスを借りての開催でした。大人の事情でラブライブの写真を取るのは禁止でした、残念。

前日hecさん(@osrehun)がTwitterで組む人を募集していたので一緒に出ることに。
あとは会場でのランダムマッチングでsatashunさんが加わり、プロ＆プロ＆僕(´･_･`)という感じになりました。


開始直後はC問題を読んだのですが英語がわからず結局satashunさんに助けてもらった(英語弱者感)
その後読んだF問題では閉路を列挙すればいいと一瞬思ったが、一般にグラフの閉路はめっちゃあるらしくて厳しいらしい。

C問題がいけそう、 D問題もRMQ書けばいけそうという感じでstashunさんとhecさんが取り掛かる。

Aが結構解かれていたので僕が考えていたが計算量を落とす工夫が思いつかない…。
結局hecさんに助けてもらいながらなんとかACしたものの、他の問題には全くと言っていいほど関われなくて申し訳なかった。


F問題の最短経路木を考えると良いと言うのが面白かったです。


おわりに

自分より強い方々とチームを組めたので、いい勉強になりました。
今回の合宿で、ICPC系のセットは「解法のわかりやすい問題をいかに高速に片付けられるか」が大事だと感じました。新しいアルゴリズムを覚えるのも大事ですが、解ける問題をしっかり解く練習もしていきたいです。
夏合宿でチームを組んでくださった方々ありがとうございました。おかげさまで楽しい合宿になりました！


おまけ

夏合宿9日目(家に帰るまでが夏合宿です)にマジカルミライ2016に行きました。
行くのは今年で2度目なんですが、今年も神イベントでした。
興味がある人には超オススメですが、ライブ以降テーマソングを聞くと泣きそうになるという弊害があるので要注意です。

*1:連続する整数の和がNになるような式を求めよみたいな問題

*2: 眠い人が携帯電話で数字を打つ問題

*3:一つの歯車を回すと他の隣接した歯車もまわるので、それぞれがどれくらいどちら向きに回転したかを答える問題

*4:x個の'B'とy個の'W'からなる文字列が与えられるので、'B'の個数:'W'の個数 = x:y となる部分文字列に分解する問題(?)

*5:'?'を含む文字列が3つ与えられるので、それらがsortedであるような'?'の組み合わせの総数を求める問題

*6:敵の攻撃がいっぱい来るのでビームで全部破壊して生き残る問題

*7:お姫様とそれを追う兵士がグリッド状にいて、姫は逃げ切れますか？という問題

*8:読んでない

*9:やる気上位20%しか働かない会社に人間が出たり入ったりする問題

*10:括弧をバランスさせるためにスワップがN解必要な括弧列のうち辞書順最小のものを答える問題