ヘクトのメモ

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

JAG夏合宿2017

チームnocowのうち2人が参加しました．(残り1人はインターンのため来られず???)


Day1
参宮橋で後輩のDiv9851と合流する。
13:00 オリセン着

初日はsnukeさんの問題セット
ixmelさんとnokotaroでチームを組みました．
結果から書くとA,B,D,E,F,H,J,Kの8完

コンテスト開始
ヘクト A nokotaro B ixmel C から3問飛ばしで読み始める

0:00
A:
しりとりですね。
サンプル1を見るととっさに面倒だなと思い、サンプル2を見てふーんと思い、制約を見るとn <= 10^9 だ。
26 + 26^2 <= n の場合は単語長が短い方から使うんだなと予想して、サンプル2を計算すると合う。

0:05
ここで順位表を見ると、Jが解かれているので、すぐに見る。
「約数の和が 98 になるような整数を全て求めてください。」
はい。という気持ちになったので、nokotaroにコーディングを任せる。

0:11 J AC

A(続き)
そうじゃない場合を考えると、しりとりだから有向オイラー路の気持ちを考える。単語長1は自己ループであることも思い返す。
そうすると、{1,2,1,2,...({1,2}を23回繰り返す)...,1,2,2,2,...(2を繰り返す),2} みたいな順で使えば良い。
コーディング

0:22 A AC

その間に順位表を見ると、DとKが解かれているので見る。
ixmelさんが、D問題の解法を思いついてくれる。
K問題はいやな貪欲かと思いきや、簡単な貪欲だなという気持ちになる。

nokotaroがEは構文解析をやるんだよと伝えられる。
昨年度のICPC アジア地区を考えると、自分が構文解析を書くべきという気持ちになり考える。

ixmelさんかnokotaroがDを実装する。
0:41 D AC

nokotaroにKを伝える。
0:46 K AC

E:
構文解析なんですが、expr関数やvector関数を用意すると、実装がカオスという気持ちになる...
exprとvectorを一まとめにすれば良いことに気づき、スカラーとベクトルはpair でまとめて、
スカラーの場合はsecondを-1にするみたいに対処
実装すると、多少バグらせるもサンプルが通る。

0:55 E AC

そうすると、残り解かれている問題がFとHになるので、Hを先にixmelさんとnokotaroが協力して場合分け
を考える。

1:39 H AC

B問題をなんか見てみる。
リス → LIS まさかね...
うまい列が求まるとLISで答えが分かる。
じゃあ、なんでこんなに解かれていないんだろう???
うまい列を求めるパートが難しいことに気づくけど、後ろからBIT + 二分探索ですね。

2:07 B AC

F問題も改めて見る。
極小は最小ではない。
左から到達判定をわざわざTrieを書いてチェックして、答えの右端を求めてから左端を求めるコードを書く。

2:34 F AC

この少し前にI問題が行けると言っていたので、実装してもらうけど、答えの1行目以外が合わない。

ここで，コンテスト終了
Gは解ける問題だったので、ちゃんと読めばよかった...

夜は東大のチームの人たちとワンナイト人狼やったり、以下のゲームを怒髪さんともやったりする。

Day2

2015 ICL, Finals, Div. 1
ラプラスさんとnokotaroでチームを組みました．
結果から書くとB,G,H,I,Lの5完

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

A
ヤバそうなのでパス

B
nokotaroが読んで、難しいと言っていたので、DPのアイデアを授ける
nokotaroに実装を任せてAC

C
やっぱりヤバそうなのでパス

D
クエリのヤバいそうなのでパス
後で、重心分解で解けると聞いて考えると、すごいなぁと思った。

E
キャリパーやれば、解けそうだけど、後回しにした。

F
ラプラスさんの考察で、 min i s.t. iの約数の総和の個数 = n
というのが出てきて、自分とnokotaroは頭を?にしながら、行けると踏んだ。
ただ、n=16などで探索が思いつかずタイムアップでした。

G
問題文を誤読する。
循環をバラして、2周の区間にする。
nokotaroに実装を任せてAC

H
Borderingを最初誤読する。
ちゃんと場合分けをして、nokotaroが頑張ってくれてAC

I
nCkと二分探索を実装する。
色々やらかしつつも、ACする。

J
方針が立ったので、ラプラスさんと自分で2回くらい書くけどWA
シンプルに難しいから放置した。

K
読んでない

L
setでほいほい。
multisetのeraseは全部消えるんですね...

F問題は非常に惜しかった... (最後に探索か)

その後にオリセンでCodefes qualaに参加する．



4完したので、人権が得られた。

Day 3
JAGセット
住建さんとnokotaro
結果から書くとA,B,C,D,E,F,G,Iの8完

ヘクト A,D,G,J nokotaro B,E,H,K 住建さん C,F,I と分けて読み進める．

A
どうせ難易度順だろと思ったので、問題を読んだらすぐに書き始める。

A 0:03 AC

B
nokotaroが思いついたとのことで書いてもらう
B 0:44 AC

C
住建さんに任せると、実装が面倒と聞き、実装してもらうとバグったらしいので、紙コーディングに移行する。
この間に、D問題は読めていたので、実装を始める。

D
N <=14 なので、どうせ3^n系DPだろうと思って解法を考える。
最初は、プレイヤー1の優勝確率の計算だろうと思っていたら、実装している最中にプレイヤー1の優勝確率の最大値の計算に気づく!
ただし、実装はほとんど変更する必要はなかった。
そのラウンドでの確率なのか、全体の確率なのかをごっちゃにして、RPSをRSPと読み間違えて手間取るが、サンプル通る。

D 1:17 AC

E
その間にnokotaroがEの解法を思いついてくれたので、バトンタッチ

Cの印刷が来ないので、住建さんとFを考える。
(ただし、トナー切れでプリンターが動かないので、印刷物が約30分~60分くらい来なかったらしい。)

F
偶数の時刻を考えると、頂点の集合が増える。
偶数時刻の頂点の最大値と最大値-1を考えれば良い??
いや、奇数時刻の頂点の最大値を考えれば良いじゃん。
ARCの偶数メートルみたいなグラフを考えつくと、辺の数が抑えられて勝ち

Eをバグらせたので、ちょっとバトンタッチして、さっさとBFSを書く。

F 1:52 AC

Cも印刷物が到着して、デバッグ完了

C 2:00 AC

Eもバグ取りが終わる。

E 2:05 AC

ここで、Gをやる。

G
計算量 O((NM)^K) の解法が思いついたので、これを書く。
WA

ここでチーム全員でプリントデバッグ

1. 盛大に全探索をバグらせる。
2. K回未満のケースを忘れる。
3. 変数を間違える
4. 関数の最初の呼び出しを間違える

などを修正して
G 3:09 AC

I
チームメイトが考察をしていたので、話を聞く。
操作は1回ずつのスワップに分解すると良いのではという話をする。
まぁ、バブルソートを書いてチェック サンプルが一致したので、計算量を落とすことを考える。

どういった操作が欲しいかを雰囲気で感じると、
領域木??? BITにsetを持たせるか??? BIT中にk番目が欲しくなる! BIT in BIT を思いつく()
実装はまだできるレベルだったので、自分が気合で30分くらいで実装する。

住建さんにコストの計算式を考えてもらい、nokotaroに0-indexedと1-indexedの違いを指摘してもらいなんとかサンプル通る。
(分割統治の方が楽だったかな...)

I 4:34 AC

あとはJを考えるけど、無理じゃんとなり、冬の順位表で遊ぶ。

ここでコンテスト終了でした．
コンテストが終了したら春になったので、面白くない。

Hはちゃんと考えるべきだった。(幾何で計算量が悪いけど、実装軽い解法を思いつけるべき)


感想
夏合宿の問題セットは今年も面白かった．
Day3 I問題は、問題設定が自然だけど、こんな解法になるのかと驚きでした。
キャリパーや、smallest surrounding rectangle ちゃんとやるべき

チーム
nokotaroが色々頑張ってくれて、有り難かった。
全般的に自分が実装した問題数が、解いた問題数の1/2程度なので、比較的消耗の少ないコンテストだった。
このパフォーマンスならICPC WF を狙えるのではと実感できました。

司令塔みたいな役割は結構上手くいったかなと思います。
何より今年は去年に比べて非常に強くなっている。(2次元BITになんて去年の自分が書けるとは思えない)
あと、軽実装の能力が高まりつつある。

ICPCの海外地区はどこに遠征するかは今回の合宿で決めました。(理由は修論の時期との調整)

ライブラリの調整が必要だなと思った。
(なんというか、写すことを目的としたライブラリにすべき)

あと、3日間の間、組んでくれて皆さま、ありがとうございました。

最後に

夏合宿の参加者や運営の方 ありがとうございました。
学生として参加する夏合宿はこれで最後です。
競プロ(プログラミング)を初めてまもない頃に来て、大いに刺激を受けました。
チーム戦をやると、他のチームの雰囲気を知れるし、どういう立ち回りをすべきかを考えるのは楽しかったです。
(ABCのwriterをやり始めたこともあって、教育的な競プロ合宿も面白そうと思えた。)

さて、あと3ヶ月の間に何を対策しましょうか?