ACM-ICPC JAG夏合宿2018
JAG の夏合宿に参加していました。いま修士1年で1995年生まれなので、選手としては確実に最後の参加になりますね。
コンテストは 3 日間とも narianZ(なり、りあん、ぴろず)で出ました。これまでの戦績は、模擬国内 3 位、国内予選 2 位です。
〜 0日目
イソターソにより労働の僕となり、全く競プロとかいうのをしておらず困った
最近勤労に勤しみすぎていて競プロとかいうやつ全くできてないので、JAG夏合宿では睡眠を担当します
— りあん[50/158] (@rian_tkb) September 14, 2018
お風呂の排水口が詰まる
お風呂の排水口を詰まらせて死んでる
— りあん[50/158] (@rian_tkb) September 14, 2018
1日目
荷造りを始める
荷造りの進捗です pic.twitter.com/YSov7bpim1
— りあん[50/158] (@rian_tkb) September 15, 2018
荷造りを終える
荷造り完了です pic.twitter.com/DeaAFPeeuA
— りあん[50/158] (@rian_tkb) September 15, 2018
ティッピー、45Lのゴミ袋に入っている
— りあん[50/158] (@rian_tkb) September 15, 2018
到着
りあんさんティッピー pic.twitter.com/t0EeccKlKj
— みくにゃん先輩@会津合宿 tm370円 (@mel_fall524) September 15, 2018
巨大ティッピーと触れ合った
— そすうさ(素数うさぎ) (@wk1080id) September 15, 2018
自己紹介フェーズに困りネタに走る(誰とは言いませんが普通に自己紹介しただけで笑いを取る人、ずるくないですか?)
自己紹介で自己の紹介をしないことに成功した
— りあん[50/158] (@rian_tkb) September 15, 2018
???「これはティッピーで、これはキスショットです」
— beet (@beet_aizu) September 15, 2018
コンテスト
この日のセットは2017年の台湾の国内予選。8問3時間
JAG夏合宿で去年の台湾の国内予選セットを使おうかと思ってるんですけど、さすがにこんなのまで目を通してる人はいないですよね…?(まだ見てない人は見ないで!)
— not (@not_522) September 13, 2018
Bを読んでめんどくさいなぁ、typo が怖いなぁ、と言いながら通す。FA(やったぜ)
E の概要をぴろずさんから聞いて、半径で二分探索はそんなに時間をかけずに思いついたが誤差が怖いので他の方法を考える
→ やっぱりなさそうなので諦めて二分探索する
→ WA(つらい)
→ 思考停止 double -> long double
→ WA(そうだね)
このときなりくんも F 問題をバグらせていてつらそう、というかつらい時間だった
その後お絵描きしていたらうまくいかないケースに気づく。困った〜、って言っていたらぴろずさんから残り1辺の長さで二分探索すれば良いのでは、という解法が降ってきて、考えるとおそらく正しそうなので書く
→ WA(つらいね)
色々なケースを試してみるが、なかなか落ちるケースが見つからない。仕方なく、誤差により asin の引数に 1 より大きい数が入っている可能性にかけ asin のラッパーを書く
→ AC(うれしい)
そのあとは F をちゃんと考察を詰めて書き直して AC したり、G を書くなりくんを cheer up していたりした。
結果は 7 完で 3 位(オンサイト 2 位)、うれしい
実質人類1位です! pic.twitter.com/Qj1ETemrCW
— りあん[50/158] (@rian_tkb) September 15, 2018
E の本質です pic.twitter.com/2J86AMPkBt
— りあん[50/158] (@rian_tkb) September 15, 2018
問題 | 考察 | 実装 |
---|---|---|
A | ? | なり |
B | りあん | りあん |
C | ? | なり |
D | ? | ぴろず |
E | ぴろず、りあん | りあん |
F | ぴろず、なり | なり |
G | ぴろず | なり |
H |
こうして見るとぴろずさんがめっちゃ解法生成していてすごい
AGC は B が解けずにめっちゃ冷えた。いや、C はオートマトンの気持ちになれば自明なんですが。
これは秘密なんですけど、Cの考察をしていて、これ非自明だよな?出すの怖いなぁと言いながら順位表を見たら、りあんさんがCを光速で解いていて、解法に確信を持ちました
— リッキー (@rickytheta) September 15, 2018
2日目
— りあん[50/158] (@rian_tkb) September 15, 2018
名刺代わりに常にキスショットを持ち歩くようにしているんですが、常にぬいぐるみを持ち歩いている22歳男子修士学生、冷静に考えて本当にヤバすぎる
— りあん[50/158] (@rian_tkb) September 15, 2018
コンテスト
この日のセットは yosupo, sigma, sugim, maroon の激ヤバセット。11問5時間
A を読んでえー、って言ってたらなりくんが爆速で B を通す(FA)。その上 A の解法を教えてもらうという介護っぷり。
そのあと D 以降全部読んで、解けそうな問題が存在しなくて困る。
H が似たような発想を使う問題を作問したことがあり、なりくんに Suffix Array 上で共通接頭辞の長さを管理できれば解けそうな気がするなぁ……って言ったら、なんとそれを実現する LCP Array というものが存在するんですよね〜、となる(蟻本を真面目に読んでいないことがバレる)
なりくんに実装を任せているうちに考察が進み、さらに実装が軽くなりそこまで苦なくAC(オンサイト FA)
E はそこまで遅くないタイミングで a + b = c となるような 3 組を見つけられれば終了というところまでは行くが、どうすればそれが求まるのかわからず。
なんとなく bitset 高速化と FFT が思いつくが、FFT は自分はなんと使ったことがないので、なりくんに bitset を囁く。
なりくんが bitset のサイズを 10 倍にしていたり入力を受け取らないコードを提出していたりしていたが、なんとか AC。count() を any() に変えたら倍近く速くなったシーンは涙なしには語れない。
その後はJの本質の考察をぴろずさんがしてくれて、それを自分が最小値を求める問題だと言ったらいつの間にかぴろずさんがセグ木に乗る形にしてくれ、なりくんが書いてAC(オンサイトFA)
その後はだいたい F をやっていて、最初はある程度複雑な座標に行ったら戻ってこれないのでは、という話になってぴろずさんが BigInteger で頑張るが、さすがにきびしい。
自分が式を無駄にいじくり回しているとこれは明らかに四則演算のみからなる写像だよなぁとなり、もしかしたら Mod の下でやっていいのでは? となり、なりくんに実装してもらったらサンプルが通り、まじでか……と言って投げたら AC。ほんまキレた。
結果は 7 完で 3 位(オンサイト 1 位)、うれしい
人類1位です! pic.twitter.com/ipt5n1PNd8
— りあん[50/158] (@rian_tkb) September 16, 2018
— りあん[50/158] (@rian_tkb) September 16, 2018
suffix array も遅延セグ木も書いたことはないけどそれらを用いた考察はできます
— りあん[50/158] (@rian_tkb) September 16, 2018
ぴろずさんの話を聞いて、a + b = c なる組が存在するかどうかが一般に O(N^2) で求められないなら、計算量に要素の最大値の大きさが絡んでくるのでは、となった(ので bitset や FFT を考えた)
— りあん[50/158] (@rian_tkb) September 16, 2018
これがわかっていてなんですぐ Mod を取れなかったんですかねぇ……
codechef に出ると b/a を Mod 10^9+7 で整数にして出して、みたいな問題を無限に見ることができます
— りあん[50/158] (@rian_tkb) September 16, 2018
Gもコンテスト中に一瞬ピックの定理の話が出てきたし、もしかしたらワンチャンあったのかもなぁという気持ちがなくもない(まぁ無理なんですが)
問題 | 考察 | 実装 |
---|---|---|
A | なり | りあん |
B | なり | なり |
C | ぴろず | ぴろず |
D | ||
E | なり、りあん | なり |
F | りあん? | なり |
G | ||
H | りあん | なり |
I | ||
J | ぴろず、りあん | なり |
K |
A問題しか実装していない……そしてなりくんが後半全部実装していてすごい(申し訳なさすぎるなこれ)
このセット、ロシアに送ったセットに簡単な問題を 8 問追加したまじ? ソビエトロシアでは 0 完が narianZ する
yosupo.hatenablog.com
売店に行って部屋に帰ってきたら部屋で何かが行われていました
完成したらしいです(本人のプライバシーに配慮され画像が加工されています) pic.twitter.com/3YgKxrMnmK
— りあん[50/158] (@rian_tkb) September 16, 2018
3日目
— りあん[50/158] (@rian_tkb) September 16, 2018
荷造り完了した pic.twitter.com/zIMZgyr5Iz
— りあん[50/158] (@rian_tkb) September 16, 2018
コンテスト
この日のセットは JAG のセット。11問5時間
写真を撮るのを忘れた
協調性が欠けているので勝手に自分のチームの机だけ L字型に変形した
— りあん[50/158] (@rian_tkb) September 17, 2018
Aを読む。どうすればいいのかよくわからなかったがとりあえず書き始めるとなんとなく行けそうな解法が思いつきそのまま実装し FA(やったぜ)
Cもはいという感じだったのでささっと実装した。
いつの間にか J の考察が終わっていて通っていた(オンサイトFA)。
I は立式ははいだったが実際にどこを掛け合わせればいいかで少しテンパったがなんとかAC。
F は Nim の気持ちになったら xor を 1 にしたい気持ちになるので適当をした。コーナーケースもわりとすぐに見つけて適当をしてAC。
G は一見険しそうに見えたが、ぴろずさんが右からやって行けば確定していない値をキーで持つ必要がない、と言っていて天才じゃんとなる。多次元 DP はややこしいのでバグるがデバッグの手伝いをしてAC(オンサイトFA)(人のコードの粗探しをするのが上手)
その辺りで K を読んだらえーこれ自明じゃんとなる。しょうもないバグでつらい気持ちになるがなんとかAC。
D は前日の問題が頭に強く残っていて考察ガチャに失敗し、trie やらロリハやら使うめっちゃ険しい実装をなりくんにやらせてしまった。それでもなんとか通してくれてよかった。
そのあとはなりくんがめっちゃ E を実装していた。あと 1 時間くらいあれば通っていそうだった。
結果は 9 完で 3 位(オンサイト 2 位)、うれしい
人類1位です! pic.twitter.com/Kp3eu9WRw9
— りあん[50/158] (@rian_tkb) September 17, 2018
A の FA を取りました
— りあん[50/158] (@rian_tkb) September 17, 2018
他のチームがどこもめっちゃ強くて、中終盤めっちゃビクビクしていた
9完多すぎでは? 人類強すぎる
— りあん[50/158] (@rian_tkb) September 17, 2018
H も牛ゲー感は感じ取れていたが、さすがにあそこまで正確に考察して最小費用流を流すのは無理でしょという気持ちになった。
問題 | 考察 | 実装 |
---|---|---|
A | りあん | りあん |
B | ぴろず | ぴろず |
C | りあん | りあん |
D | りあん | なり |
E | なり | なり (WA) |
F | りあん | なり |
G | ぴろず | ぴろず |
H | ||
I | りあん | りあん |
J | ぴろず、なり | ぴろず |
K | りあん | りあん |
3日目はけっこうバランス良い感じになったかも? WA が多かったのでもったいない
jag夏合宿お疲れさまでしたーーー
— りあん[50/158] (@rian_tkb) September 17, 2018
きたくしたら、お風呂の排水口が詰まっているという現実に直面してしまった
— りあん[50/158] (@rian_tkb) September 17, 2018
4日目
イソターソに4時間の遅刻をした(某が人間的な時間に出社できていたらしいのが本当に解せない)
あの、いまおきました
— りあん[50/158] (@rian_tkb) September 18, 2018
やはり勤労からの夏合宿からの勤労には無理があったか……
— りあん[50/158] (@rian_tkb) September 18, 2018
実績解除 : イソターソ先で誤って大音量で Guilty Eyes Fever を流す
— りあん[50/158] (@rian_tkb) September 18, 2018
明日から会津合宿らしいですね、ちなみに私は勤労です(勤務時間中にコンテスト参加できないかなぁ)