うにゅーん、って感じだ

SRM highest:1959. C#を書きます.

ACM-ICPC JAG夏合宿2018

JAG の夏合宿に参加していました。いま修士1年で1995年生まれなので、選手としては確実に最後の参加になりますね。


コンテストは 3 日間とも narianZ(なり、りあん、ぴろず)で出ました。これまでの戦績は、模擬国内 3 位、国内予選 2 位です。

〜 0日目

イソターソにより労働の僕となり、全く競プロとかいうのをしておらず困った

お風呂の排水口が詰まる


1日目

荷造りを始める

荷造りを終える


到着


自己紹介フェーズに困りネタに走る(誰とは言いませんが普通に自己紹介しただけで笑いを取る人、ずるくないですか?)


コンテスト

この日のセットは2017年の台湾の国内予選。8問3時間

Bを読んでめんどくさいなぁ、typo が怖いなぁ、と言いながら通す。FA(やったぜ)
E の概要をぴろずさんから聞いて、半径で二分探索はそんなに時間をかけずに思いついたが誤差が怖いので他の方法を考える
 → やっぱりなさそうなので諦めて二分探索する
  → WA(つらい)
   → 思考停止 double -> long double
    → WA(そうだね)
このときなりくんも F 問題をバグらせていてつらそう、というかつらい時間だった
その後お絵描きしていたらうまくいかないケースに気づく。困った〜、って言っていたらぴろずさんから残り1辺の長さで二分探索すれば良いのでは、という解法が降ってきて、考えるとおそらく正しそうなので書く
 → WA(つらいね)
色々なケースを試してみるが、なかなか落ちるケースが見つからない。仕方なく、誤差により asin の引数に 1 より大きい数が入っている可能性にかけ asin のラッパーを書く
 → AC(うれしい)
そのあとは F をちゃんと考察を詰めて書き直して AC したり、G を書くなりくんを cheer up していたりした。

結果は 7 完で 3 位(オンサイト 2 位)、うれしい



問題 考察 実装
A ? なり
B りあん りあん
C ? なり
D ? ぴろず
E ぴろず、りあん りあん
F ぴろず、なり なり
G ぴろず なり
H

こうして見るとぴろずさんがめっちゃ解法生成していてすごい



AGC は B が解けずにめっちゃ冷えた。いや、C はオートマトンの気持ちになれば自明なんですが。


2日目


コンテスト

この日のセットは 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 位)、うれしい




これがわかっていてなんですぐ Mod を取れなかったんですかねぇ……


Gもコンテスト中に一瞬ピックの定理の話が出てきたし、もしかしたらワンチャンあったのかもなぁという気持ちがなくもない(まぁ無理なんですが)

問題 考察 実装
A なり りあん
B なり なり
C ぴろず ぴろず
D
E なり、りあん なり
F りあん なり
G
H りあん なり
I
J ぴろず、りあん なり
K

A問題しか実装していない……そしてなりくんが後半全部実装していてすごい(申し訳なさすぎるなこれ)


このセット、ロシアに送ったセットに簡単な問題を 8 問追加したまじ? ソビエトロシアでは 0 完が narianZ する
yosupo.hatenablog.com



売店に行って部屋に帰ってきたら部屋で何かが行われていました


3日目


コンテスト

この日のセットは JAG のセット。11問5時間

写真を撮るのを忘れた


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 位)、うれしい


他のチームがどこもめっちゃ強くて、中終盤めっちゃビクビクしていた


H も牛ゲー感は感じ取れていたが、さすがにあそこまで正確に考察して最小費用流を流すのは無理でしょという気持ちになった。

問題 考察 実装
A りあん りあん
B ぴろず ぴろず
C りあん りあん
D りあん なり
E なり なり (WA)
F りあん なり
G ぴろず ぴろず
H
I りあん りあん
J ぴろず、なり ぴろず
K りあん りあん

3日目はけっこうバランス良い感じになったかも? WA が多かったのでもったいない





4日目

イソターソに4時間の遅刻をした(某が人間的な時間に出社できていたらしいのが本当に解せない)




明日から会津合宿らしいですね、ちなみに私は勤労です(勤務時間中にコンテスト参加できないかなぁ)