えびちゃんの日記

えびちゃん（競プロ）の日記です。

JAG 夏合宿 2019 参加記

JAG の夏合宿に参加していました． いろいろ忙しくて参加記を書くのを後回しにしてしまっていました．

jag-icpc.org

Day 0

夕方の飛行機で東京に向かうんですが，お昼前くらいに空港に行って遊んでいました． すみっコぐらしのボールペンを買ったりしました．

本当は何かしらの進捗を生む予定だったんですが，現実は厳しい．

すみっコぐらしのキャンペーンがロフト池袋でやっていて，東京に着いた後それに行こうと思っていたのですが，間に合わなさそうだったので諦めてホテルに行ってリステップをしていました．

Day 1

集合前にロフトに行けばいいか〜と思っていたんですが，所要時間を間違っていて間に合わなさそう（おいおい）．直接会場に行きます．

参宮橋駅から出て，道どっちだったかな〜と思っていたところ waku くんと olphe に会いました． 道を聞こうとしたら道を聞かれてえびちゃんの負け．

57-5 を撮ってノルマ達成．

名札をもらったり自己紹介をしたりしました．

コンテスト

つたさんが A でわたわたしてる． B を読むに，素因数を候補にして適当をするとよさそうなので変わってもらって書く．FA，うれしいね．

C をたぶくんと相談するけど，えびちゃんが誤読をしていてよくわからない会話をするやつをした．ごめん．long long にするべきところがなってないみたいなのでペナをもらうけど AC．

D は CRT を貼るといいらしい？ オーバーフローが怖いので __int128 を使うなどしてがんばる．AC．

E はポテンシャル付き union-find をするとよさそうらしい．掛け算で関係が定義されるっぽい？ log を取って計算するとか聞こえるけど誤差が怖いので Python でやるのを提案した．分数も使えるし．

fractions を import して使い忘れるやつをやってしまった．あとなんか RE が出てる？ ゼロ割りはしてないはずだし... と思っていたら再帰深度のことを思い出してたぶくんを見ると一瞬で「sys set recursion」とか言われる．天才か？

たぶくんは別のを考察中だったので，細かい書き方は聞かないで REPL の補完を見て書き方を調べて解決．sys.setrecursionlimit(300000) とかを書きました．AC．

J は最小を求める方は union-find で一瞬なので勝手に書いておく． 最大の方を相談すると，二部マッチングと言われ，なるほどなぁとなって Dinic を写して投げる，AC．

I のゾンビのやつは問題設定が面白い． 勝手にゾンビに向かって走っていって感染して，他の人間に感染させる人間，最初から実質頭がゾンビじゃんとか言って笑ってた．

ゾンビの初期位置を 0 に固定していいね〜と言ったらたぶくんが速度も 0 にしていいと言うので天才じゃんとなる．

CHT をしたいけど，整数じゃなくて実数なのでちょっとライブラリに手を加える必要がありそう． あと点でクエリするいつものじゃなくて，直線と交わる位置を知りたい． 「不可能か？」「毎回線形変換する？（）」とか言ってたら，にぶたんできるじゃんと言われて天才じゃんとなる．誤差に負けました...

K はつたさんが高速化をがんばってるけど結局間に合わず終了，つらい．

6 完のうち最速で 12 位．うむむ...

解説

「有名 mod は当然落とすべき」とかいう名言．

これすき（I の解説スライド参照）．

元ネタがあるのに教えてくれないのは悲しいので悲しい．

わいわい

せいかちゃんとお部屋でリステの話をしていました．

こたつがめが ABC をするのを見ました．提出欄に直書きで Pascal や sed や Perl を書いて，fastest/shortest を狙っていてすごかったです．

せいかちゃんとお風呂に行って，帰ってきた後もこたつがめが ABC を楽しんでいて，見ていて楽しくなりました．

お部屋では「お題 A に属する単語 a と，お題 B に属する単語 b であって，a と b の編集距離が与えられた定数 k である a, b を探す遊び」をしていました．派生して，「a の部分列から b を作る遊び」になったり，「そういう雰囲気の一番感動したやつ（雑）を作る遊び」になったりしました．

「アルゴリズム名から食べ物（編集距離 3）」に対して，こたつがめが「ダイクストラからイクラ」を即答していて天才だなぁとなりました．

他にも，単語 a から始めて，編集距離 k の単語をつなげて単語 b を作る遊びもしました． お題「徒歩→新幹線（編集距離 2）」に対して，「徒歩」→「」（空文字列）→「線」→「幹線」→「新幹線」と一瞬で終わったのが面白かったです．

せいかちゃんがえびちゃんのおふとんで寝ちゃっていたので，そのまま一緒に寝ました．

Day 2

朝方に目が覚めて，飲み物を買いに行こうとしたんですが，寝ぼけていて眼鏡をかけ忘れたままお外に出て何も見えない人をしました．うっかりさんなので．

ゆるふわコンの問題を見て考えながら二度寝しました．

コンテスト

B わからない．

E を読むとギャグすぎて不安になったけど，書くと AC，それはそう．

I を詰めるのが現実的そうなので詰めてみる． union-find で同じやつを管理する？ 面倒そう？ 結局，回文ができるかの判定と，回文の個数を数えるのをするとよさそう．

回文の個数を間違えると AC．？？？

FA だったので喜んでいるとジャッジが壊れているらしいアナウンスが入って泣いちゃった．

一応チームに解法を共有すると間違いに気づいたので一応投げておく．

D を誤読してて 0/1 を出力していたけど，bit DP でいいらしいとなって，結局つたさんに丸投げしてしまう．ごめんなさい．

F の考察をするけど，無限に解法ガチャに失敗するので別のを見るのを提案．

J は，式変形をがんばってもらうと，Lagrange 補間でできそうな形に見えるので，がんばろうとするけど，気をつけるべきところに気づけなくて一生不可能になってた．ごめんなさい．

4 完の早い方で 15 位，うーんうーん．

わいわい

と見せかけて，懇親会までは疲れてお部屋で寝ていました．

懇親会

monkukui や Darsein さんとちょっとお話した後はずっとびーとくんとらてくんにくっついていました．

最近母関数が流行ってますね〜と言ったら「母関数はおもちゃ」とか言われてそうなんだ〜となりました．セグ木はもうオワコンらしい．

包除は頭こわれるけど母関数は式変形すると勝手にいい感じになるとか言われたけど，えびちゃんは母関数で頭をこわしています...

びーとくんが Second Sum の説明をらてくんにしてるのを聞いたりしていました．ところでこれ，ウェーブレット行列で解けそうですね．

追記：できました（提出コード）

びーとくんが ABC の問題をリークしていました．

「一問目は toptree」

「二問目は多倍長整数．Python だと掛け算が遅すぎて死ぬ」

「三問目はヤバい幾何．コーナーケースが 100 個くらいある」

「五問目は証明できてないけどなんかそれっぽいから置いた」

（四問目はどこ...？）

あと，この話を何人かにしたところ，五問目に対してみんな「こどふぉか？」って反応をしてたのが面白かったです．

Day 3

朝はばたばた．

つたさんが writer なので，代わりに monkukui を入れてチームを組みました．チーム名は tsutaj です．

コンテスト

A を monkukui がちゃんと AC していてえらい．

D が楽しそうで考えてみるけど一生失敗し続けてた．

C はわりと直感的．座圧しなきゃだねというのをたぶくんに指摘したり，ペナをもらって直したりして AC．

B，これはなんですか...？ こういうのは逆からするしかありませんね...？（嘘） がんばって逆から復元するのを書いて，AC．たぶくんえらいなぁ． 単調性には気づいてたはずなのに，発想がにぶたんに至らなくて，本当に青コーダーですか...？ という気持ちに．

J のパズルが楽しそう．もう一歩っぽさを感じるけど不可能．

結局この日えびちゃんは 1 AC もしていません... ごめんなさい．

わいわい

解説がゆるいの，おもしろくてすき．

解散した後は，せいかちゃんとフェリンさんとたぶくんと一緒にいました．

「えびちゃんはこのあと池袋のお店に行きたいんですが」と言うとついてきてくれるらしくて，人々やさしいなぁとなりました．

たぶくんに「すみっコぐらしですか？」と言われて，さすがだなぁと思いました．

えびちゃんの影響ですみっコぐらしをかわいいと認識してきたとか言われて，なんかうれしくなりました．

キャンペーンのやつを無事に手に入れられました．

そのあと，みんなでラーメンを食べました．おいしかったです．

ACPC に参加するため，会津に向かいました．気づいたら途中でご当地のすみっコぐらしグッズを買っていました...