ゆらのふなびと

競プロ, Python, C++

JAG夏合宿2017参加記

昨年に続き 2 度目の参加。

うちのチームは 3 人とも夏合宿に参加していたが、3 日目の JAG セットだけ一緒に出ることにして、他の日はめいめいに他の人たちと組むことにした*1

1 日目

1日目は btk さんと一緒に参宮橋駅前のラーメン屋「空海」でお昼。

会場につくと shora さんや not さんが受付や会場の準備をしていて、夏合宿だなあという気持ちが高まる

jag2017summer-day1.contest.atcoder.jp

コンテストは snuke さんによる 3 時間セット。

imulan さん、yana さんの SyntaxSato チームが 2 人だったので入れてもらった。

解いた順に感想

J: 98 以下の数を全探索すればよさそうと言ったらチームメイトが書いてくれた

K: 担当した。貪欲みを感じたので何でソートするのかいろいろ試す。 G - C ? 違いそう。冷静になってカードの部分集合 S を召喚できる条件を不等式で書くと C + G の昇順にとれば良いことが分かったので書く。 数式をいじれば分かったけどもうちょっと直感的に理解できるようになりたい……。

D: yana さんが算数*2をしてくれて AC

A: imulan さんと yana さんが議論して通してくれた

H: 担当した。上下左右斜め 8 方向に進むコストを考えると、まず斜めに進めるだけ進んでその後上下左右に動けばよい。8 通り場合分けしてコードを書いたのでしんどかった*3

E: 問題を読んだ imulan さんに話を聞くと ‘*’ の両端が vector か expr かで対応を変える必要があって、そこが難しそうとのこと。似たような問題を解いた記憶があったのでアイデアを imulan さんに伝える*4。僕が書くと無限に時間がかかりそうだったので imulan さんとペアプロして解く。僕がざっくり方針を伝えると imulan さんが綺麗にコードに変換してくれてすごかった。

F: imulan さんと yana さんが O(|S|Q) 解法までは出してくれていた。その後 yana さんから S における各文字の出現位置を set で持っておくと次の文字に行くのが O(log|S|) でできる => O(Qlog|S|) で解けるという指摘が来て、解けそうな気持ちになったので僕が書くことに。僕が set の lower_bound の使い方をよくわかっておらず 2 人に助けてもらいながら書いた。 実は set を使わなくても dp[i][j] = 位置 i から最も近い右側にある文字 j の位置 を前計算しておくとできるというのを後で聞いてなるほどとなった。

結果は 7 完 11 位。結構健闘したと思う。0 WA なのもポイント高い

f:id:pakapa104:20170925194359p:plain

snuke さんの公式解説がわかりやすそう

twitter.com

夜は Yazaten, okaduki, btk, btkさんのチームメイトの地頭モンスター氏*5と一緒に sake で優勝しに行った。実質懇親会

宿泊棟の談話室でボドゲをしていた人々もいて、そっちも楽しそうだった

2 日目

朝食チャレンジに AC

codeforces.com

“2015 ICL, Finals, Div. 1” なる 5 時間コンテスト

競プロチームマッチングサービスとして名高い Twitter を活用し、 Div さんと ferin さんの I MUST GO チームに入れてもらう。

以下時系列順

L を読むが題意に確信が持てない。動かせるのが各レーンから高々 1 人なのか全体で高々 1 人なのか……。サンプルが弱いので検証のしようがない。とりあえず様子を見ることにして他の問題へ。

G が解けそうという話を聞いたので読む。確かに解けそう。直線で前にも後ろにも動けるなら移動距離が最小になるのは中央値というのは知っていたが、円環で前にしか動けないのでしゃくとりっぽくやる

L は他のメンバーにも読んでもらったところ「動かせるのは全体で高々1人」らしいので考える。O(n2) は自明だが n <= 105 なので O(n) でやらねばならず意外とめんどい。結局書いたのはどれを左右どっちに移すかを全探索するやつで、元の最大値を m として m の個数と m-1 の個数を持っておいて、(動かした後の最大値) * (その個数) でスコアを計算する、というようなことをやった。

B を Div さんが解いているがバグっていてつらそうなのでコードを読ませてもらうが、特に間違いが見つからない。方針転換ということで僕が別の DP を考え、Div さんに書いてもらうと AC。不明

H は ferin さんが解いてくれた

結果は 4 完。あとは I が解けるか解けないかという感じだった

昨日ボドゲをできなかった無念を晴らすため snuke さんにちょっとだけボドゲを教えてもらった(きゅうりのカードのやつ)

夕飯は夏合宿の聖地「万豚記」へ

僕は辛いものが苦手なので普通のラーメンにしたけど、隣の nvip さんが頼んでいた唐辛子マーク 4 つのやつは運ばれてきた途端香りだけで辛くてやばそうだった

帰宅後は談話室でこどふぇす予選 A オンサイト

D がそもそも構築とかいう発想がなくほげという感じだった

JAG の人が Wi-fi 環境を用意してくれて感謝

3 日目

jag2017summer-day3.contest.atcoder.jp

JAG による 5 時間セット。

Yazaten, ratea と sparsely_populated_regions で出た。

問題が難易度順に並んでいるかどうかわからなかったので、適当に読めそうな問題から読んでいくことに

A: A はさすがに簡単だろうということで、PC の前に座っていた僕が A を読む。O(n3) でもいけるけど ‘*’ の位置の深さを求めればいいだけということに気づいたので書く。

B: まだ読まれていなかったので読む。解けそう*6。「X周以内でクリアできるか?」でにぶたんした*7

C: Yazaten がバグらせていて辛そうだったので話を聞く。外周から1周ずつぐるぐるはぎ取っていくという解法でやっていたらしいが、それより上から1行ずつ埋めていく方が楽そうという話をする。Yazaten が書いて AC。

F: 僕と ratea で考えた。問題を理解するのに 10 分くらいかかった*8。 まず二部グラフだと必ず無限ループするということに気づく。 二部グラフでないときは、奇数長の閉路に含まれる辺の両端が current に含まれるとそこから current が広がっていくので必ず有限ステップで終了する。 そこで解法としては、各辺の両端が初めてともに current に属するまでのステップ数を求める -> その情報を使って全頂点が被覆されるまでのステップ数を BFS で求める、というようなことをした。 解説を聞いたらもっとシンプルでひょええとなった*9

解いた問題はここまで。

D: bitDP解法は思いついたけどずっと O(4N) で間に合わないと思っていた。部分集合の部分集合をすべて考えると O(3N) になるやつは知っていたのに気づかなかったのが悔やまれる

E: 掛け算の中でまず DP をしてその後足し算の世界で DP をすればよさそう。Yazaten に実装してもらっていたけど間に合わず

結果は 4 完 29 位。このセットできっちり 6 完できるようにするのがアジア地区に向けての目標になる気がする。

終了後チームの 3 人で築地にお寿司を食べに行った。とてもおいしかった(写真は他のメンバーが上げてくれるはず)

うにを食べた Yazaten が、retea に話しかけられたとき「今うにが美味しくて忙しい(から話せない)」と言っていたのが面白かった*10

まとめ

JAG スタッフのみなさんありがとうございました。

つくばに行く人はまたつくばで会いましょう。

そうでない人もまたどこかで会いましょう*11

懇親会がないのはちょっとさみしかったです*12が、チーム戦やボドゲを通じてまた新しい人と知り合えたのでよかったです。

正直言うと最近全然競プロをしていなくて、自分が夏合宿に行っていいのかと思っていたのですが、チーム戦を通して「やっぱり競プロは楽しい」という気持ちを取り戻せすことができたのは大きな収穫でした。

またアジア地区に向けてチーム練をやっていきたいと思います。

来年は運営側にいる気がするので、†全方位よろしくお願いします†。

*1:交流の機会は貴重なので

*2:yanaさん談

*3:斜めが右上しか得しないことを考えるともう少し楽に書けそう

*4:構造体にフラグを持たせる的なやつ

*5:Twitter id がわからない……。

*6:この辺りで結局難易度順に並んでいそうだということに気づく

*7:「X日」だと単調性はないが「X周」なら単調性がある

*8:疑似コードをちゃんと読みましょう

*9:解ければ勝ち

*10:実際うにはおいしくて言葉を失った

*11:直近だと KUPC 京都オンサイトには行きます

*12:日程的に仕方ないですが