ヘクトのメモ

なんとなくいろいろ書いていくと思います．

JAG 2016 夏合宿

チームnocowのうち2人が参加しました．(残り1人はTWとMMAの合同CFTの運営のため来られず)


Day1
14:50 オリセン着
今年は最初から会場にいた．
ガイダンスを聞いて自己紹介を行う．
@snuke_ @37dbye @2557_lettersと相部屋になって，ハンドルネームの由来などを聞く.
そのあとは，snukeさんの持って来たthe bossというゲームで遊ぶ．


どのタイミングでベッドしつつ，相手の賭けを加速させるかが重要なゲームだなと思う．

19:00〜21:00　懇親会


日頃，Twitterで見かける人たちと交流を行う．
btkさんの「egg fire」やどんな練習をしているのかレーディングについて話し合う．

Day2
CERC 2014
yurahunaさんとnokotaroでチームを組みました．
結果から書くとC,D,H,Iの4完

C:
break文を無意識に書き忘れることによるWAの闇に飲まれる．
nokotaroは無自覚にbreak文を書けるためAC

H:
最大3桁の整数を全列挙してもられば良さそう．
yurahunaさんに実装を任せる．AC

D:
問題文から比を適当に計算して，接している歯車の回転は互いに逆向きになる．
歯車がうまく回らないケースは与えられないので，関係が木になっていると思ってコードを書く．TLE
木でなくてもうまくいくケースが見つかる(2部グラフでうまく回れば良いらしい) 頂点の訪問フラグを追加する AC

G:
manacherだと思って考察を進めるも漸化式を立てるのが無限に辛くて無理だった．
(これは本番で0ACなので，難易度の見積もりをミスる)

I:
nokotaroとyurahunaさんが一緒に取り組んでAC

F:
dpでうまくいくでしょと書く．そして，遷移を前計算しないとTLEするのはすぐに気づいたのでちゃんと書く．
文字列はダミー文字で長さを調整する．サンプルは通る．投げる TLEとWA ...
何回か修正して投げると，長さ10^6のdp配列の初期化を毎テストケースしていることに気づく．
修正して，AC and WA...

ここで，コンテスト終了...
Fはダミー文字のアルファベット順序を'z'+1にしていたのがバグの原因だった...

解けなさすぎて辛かったので，この日は真面目に復習してAとFとJを通す．


Day3
11:00〜16:00 JAG模擬地区コンテスト @LINE

@37dbyeさんとnokotaroでチームを組みました．
結果から書くとA,B,C,D,Eの5完

A,D,G,JとB,E,H,KとC,F,Iと分けて読み進める．

A
全探索すれば良いので書く AC

B
nokotaroと少しだけ悩んで姫と騎士の最短距離を求めて比較すれば良いことに気づく．
nokotaroに実装を任せてAC

E
なんか，解かれているので取り組む．
木の同型判定かなと思い，ローリングハッシュとdfsを組み合わせたコードを書く．
サンプル3で木の同型判定ではなく，別の類似判定だということに気づく．サンプル通る．
投げるWA ハッシュの基数が少なすぎる? 4つも使うがWA
ダメか... と思っていたら，リジャッジが走ってAC

D
@37dbyeさんとnokotaroが頑張ってくれてAC
解説聞いたらかなりシンプルだった．

C
Binary Indexed Treeを利用して実装すれば人数のカウントができる．
がんばって実装するけど，何か合わない．
モチベーションの順序を間違えている... サンプル通る
けれど，WA... 3人で並列デバッグするとアンダーフローに気づく
AC

G
凸包のコードを書くけど，方針が右往左往してタイムアップでした．

解説
G問題の解説を聞くとそういえばという感じだった...
J問題のtokoharuさんのコードを見てみたい．(1000行オーバー...)


その後にオリセンでAGCに参加する．2完しかできなくて悲しみ...
C問題は終了1分後くらいに気づく．
この日の夜はsnukeさんとsublime textの話をする．(そのうち課金しよう)

Day 4
11:00〜15:00 OpenCup @Klab
Yazatenさんとsatashunさんとチームを組みました．
結果から書くとA,C,D,H,I,Lの6完

A,D,G,J,MとB,E,H,KとC,F,I,Lと分けて読み進める．

C
satashunさんがすぐに解法を思いついたので，実装に移る．
サンプルが通らないので，自分もテストコードを書いてサンプル3の初項と公比と項数を列挙する．
見逃していた場合に気づいたので実装をさらに進める AC

D
行数で二分探索だと最初は思う．
しかし，satashunさんに行数と幅の関係は単調増加ではないと反例を教えてもらう．
また，RMQがあれば解けると教えてもらう．計算量を見積もると良さそう．
そこで，自分がsparse tableを実装する．WA
オーバーフローをやらかしたことを指摘されて，修正 AC

L
nが奇数の時に3*(n+1)/2-1，nが偶数の時にn/2になるので収束すると予想．
satashunさんが実装を行う．メモ化部分の上限値を3*10^6くらいで投げる．RE
遷移していく中で取りうる値はかなり大きいかつ疎らななのでmapで置き換える．WA
オーバーフローを引き起こしていることに気づく． AC

H
問題文を読む．クエリを大量に処理する問題
読むと，実装が辛そうに思えたので，satashunさんに任せる．
サンプルが通ったので投げるけど，WAになるので紙デバッグする．
ふと，問題文を見直しするとこの世界の暦は1年が100ヶ月，1ヶ月が100日もあることに気づく．
そこを修正してAC (普通，常識的な暦だと思うでしょ...)

I
カジノをやる．
問題文をちゃんと読んで，入出力の解釈がよく分からないと思ったらインタラクティブだった．
スロットの内部パラメータが2^20通りしかないので，40回くらいスロットで適当に遊ぶと40bitの情報が得られるのでパラメータ推定可能でははと考える．satashunさんと一緒に検証しながら問題を解く．実装を終えたので投げる．「Idleness limit exceeded」!
入力の受け取り時やスロットの処理判定のバグを直してもITEになる．そこで，printfをcoutに書き直す． AC
(辛すぎる...)

F
解けそうということで全員で話し合う．
閉路の列挙? サイクル基底という概念があるけど，難しそう．
そこで，最短経路木を作って，そこに含まれていない辺を使って，最短経路木の根とそれ以外の頂点を結べば
上手くやれるのではないかと考える．実装するが，WA なので辛い...

A
Yazatenさんに任せる．O(n^3)から落ちないと相談を受けたので，
アルファベットの種類と個数を管理して，queueで処理すれば良いと伝える．
実装を終えて，バグがいろいろあるのでデバッグを手伝う．
投げる WA　PCを借りて?のケースに対応できていないことに気づく．
修正して投げる．TLE 　timeコマンドで最大ケースを投げてチェックすると問題ないので，入出力がやっぱり遅いのでは?
cin/cout から scanf/printfに書き換える．

J
satashunさんと話し合うと，DPで解けるということなのでsatashunさんが実装する．
上手くいってそうだけど，WA

ここでコンテスト終了でした．
JはDP配列を使いまわすと経路復元が正しくできなかったのが原因だったらしい...
Fは2頂点のLCAが根かつ，最短経路木の辺の両端となる2頂点でないようなものを求めればよかった模様．

Extra
合宿参加者合計7人で築地に向かって，競技プログラマーの英知を結集して

カフェで休憩してから海鮮丼を食べに行く．(自分はいくら担当)

コンテストの感想や雑談をする．btkさんとmykさんのやりとりが面白い．
海鮮丼を食べながら，Atcoder上で開けそうなエクストリームコンテストの案をいくつか考える．
海鮮丼コンテスト，1問題で1言語を消費するコンテストなど
次はICPCアジア地区で会いましょう

感想
夏合宿の問題セットは今年も面白かった．
ICPCの海外地区やOpencupの問題もそろそろ目を通すか．
去年のblogの感想にあった事項はしっかり達成できたと思います．
なにより，普段のチームメンバー以外の人と組めて楽しかった．
そうすると，普段は司令塔みたいな役割をしているけど，補助やコーダーみたいな役割も経験できたのが良い．
あとは，他大の人もいろいろ設備や後輩の育成とかで悩んでいて，いろいろな意見交換もできたので，サークルの運営に生かしていきたいな．
チームメンバー間の実力差が大きい場合の戦略をどうするかは課題として大きいな...

最後に
夏合宿の参加者や運営の方 ありがとうございました．