うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

ACM-ICPC JAG夏合宿2018

ICPC

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時間の遅刻をした（某が人間的な時間に出社できていたらしいのが本当に解せない）




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

就業体験日記 #5

ｲｿﾀｰｿ
  • 前日の推定就寝時間 : 2:00
    • なんか風が強かった気がする
  • 起床時間 : 10:30
    • 本当に何もかもダメ
    • 出社したらちょうどミーティング的なものが始まる時間だった
  • 無限にわからん〜、って言いながらちまちまコードを読んでいて進捗スピードがお察し
  • 文法はわりとどうでもよくてとにかく伝われば良いみたいな英語を生成する時には、google翻訳で英語->日本語の状態で、翻訳された日本語を見て大意がずれてないか確認しながら英文を書くのがオススメです（ほんまか？）
  • 社で 🆓🍺 を飲んだ
  • 研究室のOBの先輩にご飯に連れて行ってもらった
    • 社会人ぱわーを感じた
  • 4日連続で飲酒しているが？
    • まぁ今日は華金なので仕方がない


就業体験日記 #4

ｲｿﾀｰｿ
  • 前日の推定就寝時間 : 3:30
    • はい
  • 起床時間 : 10:00
    • はい
  • 昨日こなした簡単なタスクがミスっていることに気づく
    • 英語力がないのに斜め読みをするべきではない
    • 修正したらデプロイされた
      • :gong:
  • ようやくプロジェクトが始まる
    • 全く扱ったことのない技術が無限に立ちはだかる
      • 無限にめっちゃ教わる
      • こんなんでおちんぎんもらってよいのだろうか
  • チームの人たちに誘われて飲みに行った
    • なんで俺は3日連続で飲んでるんだ






就業体験日記 #3

ｲｿﾀｰｿ
  • 前日の推定就寝時間 : 2:30
    • はいダメ
  • 起床時間 : 9:40
    • 本当はもう少し早く起きたが、日本酒を飲んだ翌日に華麗な起床は難しいので
    • 出勤時刻が順調に遅くなっている
  • 1本で半日分の野菜が摂れるジュースを1日2本飲むのが日課になってきた
  • 人事の人にも りあんくん と呼ばれていることに気づいた
  • メンターの方に助けてもらいセットアップに完全勝利する
    • 本当に頭が上がらない
  • ついでに簡単なタスクをひとつこなして退勤
  • なぜか研究室に行き日本酒を2合くらい飲む
    • アホでは？

就業体験日記 #2

ｲｿﾀｰｿ
  • 前日の推定就寝時間 : 22:00
    • 帰宅したとたんに力尽きた
  • 起床時間 : 6:30
    • さすがに意味不明なので2時間くらい布団でゴロゴロしていた
  • せっかくなので早めに社に行って朝ごはんを食べた
    • おにぎり、たまに食べるとクソ美味くて困る
    • あとドライマンゴーが食べ放題なことに気づいた
  • あるｲｿﾀｰｿ生の研究室同期の進捗がヤバい話を聞いたり聞かなかったりした
  • デスクトップPCのセットアップに無限に手こずる
    • まぁ、一つも欠かすことなく上から順に実行してね！ って書いてあるのをわりと適当にやっていたので自業自得なんですが
    • 退勤しようかなというタイミングで、わりと序盤にあるコマンドを一つ読み飛ばしていたかもしれないことに気づき虚無になる
      • 虚無のまま退勤
  • なぜか退勤からの研究室に行き、日本酒を2合くらい飲む