ICPC 2019 Asia Yokohama Regional 参加記

参加記 ICPC2019

okimochi(idsigma risujiroh kort0n)でICPC 2019 Asia Yokohama Regionalに参加してきました

Day.1

かなしい...

おいしい...

韓国で買ってきたお土産毒を配る

 

 

 失礼な奴らだ

 

Practiceが始まる

C、Dは過去にチーム戦で出てきた問題

A、Bは初見だけど流石に無

Aを通す

Bをidsigmaさんが通す

 

Cはチーム練ではrisujirohが通していた為、僕が通すことに

これ確かチーム練だとTLEが出ていた問題なんだよね 注意しないと...

risujiroh「これTLE気を付けてね」

言われなくても分かってるよ えーっと...

 

よし！next_permutationで全探索すればokだな！

ウキウキで実装 submit

 

PROBLEM C TIMELIMIT

 

SeoulのPractice-Bの仕返しと言わんばかりに煽られる しにてえ

ちゃんと実装し直して通す

 

2つ隣のUKUNICHIAのつぶあんと目が合う まだCが通ってなさそうだったのでとりあえずCの風船をアピールすると、無限に親指を下げられた サイコ〜ｗ

 

risujirohがDの実装を始める

サンプルが合ったらしいので投げるがWA

何かハマってるので印刷練習も兼ねて印刷して全員でデバッグ

バグを見つけたので指摘して直してもらうと、サンプルが合わなくなる は？

よく調べると、3箇所バグってて、何故か噛み合って奇跡的にサンプルが合っていた なんでだよ

無事 AC

再びつぶあんと目が合う Cの風船をアピールしてきたのでDの風船をアピールすると、無限に親指を下げられた サイコ〜ｗ

 

clarも練習しておく

 

チーム紹介が始まる

みんな、TopCoderを、やろう！

 

これすき

あとchoKOdaiのハンドスプリングビックリした

 

10人くらいで中華街に行く

 メンバーの中で自分が年寄り側だと誤認していたので支払いで「若い人少なめで良いのでは」と言ったら自分が若い側で、無事社会性0になる いやほんとごめんなさい

 

 絶対に許さないからな。

 

 

自宅からだと相当早起きしないといけないので、会場まで1駅のカプセルホテルに泊まる

設備自体は値段を考えれば不満は無いが、近くのおっさんが一生独り言を言っていて本当に怖かった 今度から宿代はケチらないようにしようと思った

 

ABCがあった 「Eの解法2すごい！」とTLで言ってたら「いやそっちがすぐ思いつくだろ」と言われる 枕を涙で濡らしながら就寝

 

Day.2

起床即TCO Algo Finalわくわくでゲラゲラ笑う 最高の目覚め

 いや持ってこいや

「TwitterだけじゃなくてSlackも見ろ」と怒られる スマン

 

コンテストが近付いてくる (Yokohamaは前に易しい問題が存在することが保証されているのもあって)初動はSeoulのときと変えて、

idsigma:開始即環境構築 終わったら後ろの問題を読む

kort0n:環境構築後Aをやる

risujiroh:Bを読む 実装が軽ければそのままやる 重ければ実装をkort0nへ投げて後ろの問題へ

となっていた どうしても弊チームは考察が弱めで完数で勝ちづらいので、序盤からペナを切り詰めていきたいということでこのムーブに

 

9:10頃、ちょっとお腹が痛いのでトイレへ

少し混んでいて焦ったが、9:20頃にはコンテスト会場へ戻る

その後、9:24頃にrisujirohがトイレへ

あと5分か〜 しっかり初動のイメトレしないとな Seoulと違ってYokohamaは問題が3部あるから、自分のを取って残りはチームメイトが取りやすい位置に置いて...

 

...なんか周りがざわざわしてるな 何でだ？

ぼく「なんか周り騒がしくないですか？何かあったんですかね」

idsigma「なんか開始を5分早めると言っていませんか？」

 

・・・

 

（＾ｖ＾）？？？？？？？？？？？？

 

え、やばいって まだ人揃ってないって

ICPCルールは初動が大切なんだって 開始直後人いないの致命的だって

やばいって

え、どうしよう

 

などと騒いでいるうちに

ICPC 2019 Wakuwaku Regional Contest スタート

 

コンテスト

まあいないもんは仕方ない risujirohがB担当だったのが不幸中の幸い

Aの問題文を読みます 題意が分かりません

もう一度読みます 題意が分かりません

かなり帰りたくなる

サンプルエスパーで題意を把握する

この辺でもう環境構築が終わる 待って まだ考察始められてない

 

とりあえずPCが空いているのも勿体無いので、ガバガバ考察でAのコーディングを始める

なんか多分この辺でrisujirohが帰ってくる 本人も焦ってた それはそう

「上げる高さの最大値決め打てば最適なスイッチの押し方は流石に自明だし、上げる高さの最大値を全探索すればええやろ！」と言って実装する

サンプル1, 2でok

サンプル3で実行に無限時間掛かる 誰か殺してくれ

引き算を毎回馬鹿真面目にやっているところを割り算でサボれば良いのだが、なんかもう色々焦ってるので「上げる高さ限界ギリギリのときだけ試せばいいだろ！」とか考え始めて別のところで高速化しようとする 証明とかなんもないけどサンプル試すと

f:id:kort0n:20191121001700j:plain

まさかA問題からこれをやることになるとは...

なんとA問題を通すまで19分 最悪の滑り出し

 

...と思いつつ順位表見たら10位くらいだった とりあえず大戦犯ではなかったようで安心する

 

後ろの問題を読むに当たって「何読めば良いですか？」と聞くと、「IとJのFAが出てる」と伝えられる え、マジ？

見ると確かにそれっぽい色の風船がある

ということでIを読む あーなんか出来そうだな え、でもこれ開始数十分で通るの？マジ？

Jに軽く目を通す そっ閉じする

 

この辺りでrisujirohがBを通してた 自分はこのときIを読んでたけど、なんかCが出来たとかやっぱり嘘だったとか後ろでやってたらしい(?)

 

それにしてもIが簡単に出来る気がしないのでなんかおかしいなと思ってよく見ると、A、BのFAを表す金色の風船にくっついているただの風船だった ICPC経験が無い人間でチームを組むと、こういう悲劇が...

 

とりあえずPCが空いているのは勿体無いので、現時点で多少なりとも考察が進んでいるIを書き始める

「うーん、とりあえず潰せるところは潰したいな こういうときは、SCC！」と言ってSCCライブラリを写経し始める

(x_i, y_i)と(y_i, x_i)を全て有向辺として追加してSCCをする

全ての頂点が同じ強連結成分に入る

「あれ〜写経ミスったかな〜？」と言ってソースコードを印刷し、Hが実装出来そうというrisujirohにPCを譲る

席に戻って頭を冷やす

 

 

この10分間の自分、IQ2か？？？？？？？？？？？？

 

 

本当に死にたくなった こういうときはSCCじゃなくて二重辺連結成分分解だし、与えられる無向グラフは連結なんだから2通りの有向辺を張れば当然全ての頂点は同じ今日連結成分に属するし、写経は完璧だった

 

こうして無事チームのペナルティを破壊する 何の為にAB速解き戦略を取ったんですか...?

 

そして以上の考えに至ると同時に、背筋が凍る

 

二重辺連結成分分解ライブラリ、持ってない...

終わった...

 

 

 

と思ったが、何とidsigmaさんが持ってきていた 終わってなかった

Hで詰まったらしいので印刷デバッグをして、その間にidsigmaさんが二重辺連結成分分解の写経を始める

 

クソザコニートぼくくんは、ACが出ていたE、Gあたりを読むことに

E:ちょっとDilworthの定理みがある問題だよね こういうのはrisujirohが得意だし後で投げたいなー

G:余る文字列をノードにすればDijkstra出来そうだけど、各ノードに達するごとに全文字列見て遷移先ノードを調べてたら間に合わないな どうしたものか

 

risujirohがHのバグを見つけて通す

程なくしてidsigmaさんの写経も終わる

risujirohにE読んどいてと言いつつ、Iを再開する 流石に早い段階で手を着けるべき問題でないことは分かってはいたんですが、PCが空いてるのは勿体無いので...

 

しばらくして、risujirohからEの解法が飛んでくる 多分かなりアタリ解法で、実装が軽かった 10分程度で実装してAC

 

更にGの解法も飛んでくる 「頂点に来る度に文字列を見るのではなく、最初に文字列を見て辺を張って、頂点と辺を陽に管理する 一見辺がかなり多くなりそうだが、実際は多くならない」と言われたので、「すごい」と言う

これはまあまあ実装が重くて苦戦するもAC

 

順位表を見ると、流石にそろそろ本格的にIに取り組むべき頃合いだという話になる

 

二重辺連結成分分解をする、二重辺連結成分の中ではよしなにやる、いよいよ二重辺連結成分同士を繋ぐ橋の処理を行う段階になって、気付く

 

これ、パスクエリを行わないといけないから、HL分解しないといけなくないか

 

なんとこるとんくんはカスなのでHL分解の実装が出来ず、チーム戦ではいつもrisujirohに投げていたのです...

 

謝りながらrisujirohに「これHL分解でやって」と言う

1-indexedの二重辺連結成分分解ライブラリと基本1-indexed処理のコーダーからライブラリ実装完全0-indexedコーダーへ、感動の引き継ぎ

 

こんなクソ案件でも一切不満を漏らさずに実装を始める 偉すぎるだろ

 

なんか意外とすぐ実装してくれた サンプルを試す

大体合っていそうなのだが、何故か答えに「頂点0から頂点0への有向辺」が2つ出力される 絶対1-indexedコーダーから0-indexedコーダーに引き継いだせいだろ

 

カスなので答えを出力するときに「頂点0が関係する辺は無視する」処理を加えると

f:id:kort0n:20191121001700j:plain

これが競技プログラミング

 

submit

 

3人全員が実装に携わっていて、200行以上あるコード

 

本当にデバッグしたくない

 

頼む 通ってくれ

 

 

 

 

 

 

 

 

 

 

 

PROBLEM I WRONG ANSWER

 

 

 

 

 

終わった・・・

 

 

 

 

 

 

人数分コードを印刷 憂鬱デバッグの開始

 

こんなデバッグどうしろって言うんだ...

そもそも自分の書いたところにバグがあるとも限らないのにデバッグしないといけないなんて...ん...?

 

f:id:kort0n:20191121005155p:plain

？

 

f:id:kort0n:20191121005249p:plain

？

 

 

 

...

 

 

f:id:kort0n:20191121005314p:plain

？

 

 

 

 

...

 

 

 

 

PROBLEM I CORRECT

 

 

 

 

チームメイト、本当にスマン...

 

 

 

 

 

 

(もう一個カスだったのが、これ木上でimos法すればHL分解いらなかったんですよね ちゃんと考えれば最後まで1コーダーで行けたのに...いやそもそもHL分解出来ないのが最低なんですけど...)

 

何はともあれ、順位表凍結直前にIが通って無事6完となる 残り時間は30分間程度で、厳しいが何とかあと1問通したいところ

risujiroh「こるとんまだCほとんど時間掛けてないよね 考察してみたら？」

そう、今回は実装で大忙しだったので、残っているCDFJKのうちCは概要は知っているものの殆ど考察していないし、DFJKに至っては問題概要すら知らない状態だったのだ

ぼく「確かに でも一応他の4問も概要知っておきたいな 概要教えて」

risujiroh「DとJは幾何で、間に合わないのでやりません」

ぼく「ok じゃあFとKの概要を教えて」

 

risujiroh「FはN個のノードがあって、それぞれについて、-10^18から10^18までの状態があって、それぞれのノードについて遷移条件が定められていて、これに当てはまるならこっちの条件に従って状態が変わって、当てはまらないならこっちの条件に従って状態が変わるようになっていて、このとき...」

 

ぼく「悪かった Cやろう」

 

改めてCを考える よく考えると、等差数列でchmaxする感じでうまいことdpの遷移が出来るのでは？という感じになる つまりこれは

ぼく「これ線分追加CHTで出来るんじゃね？」

risujiroh「そんなもんないけど」

ぼく「おわりです」

 

と言っても仕方ないのでもう少し考えると、追加する線分の傾きは高々2種類なので、遅延セグ木を2種類持てば良いのでは？という気持ちになる

これをrisujirohに伝えて遅延セグ木を写経してもらい、ギリギリまで考察を詰める

しかしそんな短時間でこの問題の考察を詰められる訳も無かった

途中座圧も必要で時間がかなり厳しいので、遅延セグ木の写経が終わった時点で即実装に入る 確かこの時点で残り10分くらいだった

とりあえず必死でコーディングする 座圧が終わる 残り5分とか言われる

ぼく「え、これ終わるんか？間に合わんけど？」

ぼく「いや座圧いる？いらなかったよね？ねえ？座圧バグってない？」

ぼく「あーーーーいやギリギリ間に合いそう でもこれ遷移式ちゃんと合ってるのか？何も分からん 誰か助けて」

とか言いつつ、残り1分くらいで実装が終わる

 

f:id:kort0n:20191121010600j:plain

g++ C.cpp

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f:id:kort0n:20191121010851p:plain

 

終わった...

 

 

 

つぶあんと目が合う Cの風船をアピールしてきた ばか あほ かす まぬけ

 

f:id:kort0n:20191121011403p:plain

 

結果は6完741ペナで10位だった

「もっとやれたはず」という気持ちもあるにはあるが、客観的に見ればかなり上手く行った方だったと思う この結果で上手く行った方だと言わざるを得ないのはかなり悔しいんですが...

 

懇親会

何だかんだでやりきった満足感と重実装の疲労感が入り混じった状態で懇親会へ

他チームやJAGの方たちと談笑してると、企業賞の発表が始まる

"10位"というキリの良い順位だったので、企業賞が無限に贈られる

 

 

らてあさんとかに「賞を貰うときに真顔になるな」と言われたんですが、違うんですよ 後半「こんな順位で無限に企業賞を貰ってしまって申し訳ない」と恥ずかしくなってたんですよ ゆるして

 

その後企業賞を貰ったAobayama_dropoutの喜び方がかなり良かった 斯くありたい

 

懇親会では最初は周りの競技プログラマと談笑していたのだが、周りの人が謎の紙を持っていることに気付く

どうやらGoogleのブースで「各人ごとに異なる入出力例のみが印刷された紙が1枚ずつ渡されるので、それらから問題を推測して答える」という遊びらしい

 

当然皆競技プログラマなので、こういうのがあると、着手───

 

実際にはその場にいた数十人分のサンプルを見て考えていたのですが、流石にそれを全部覚えてはいないので、適当に問題に合わせた入出力例をいくつか作って置いておきます

 

Input

4 7

4 3 3

3 2 2

1 3 6

2 4 1

2 1 2

4 1 6

3 1 8

1 2

 

Output

8

 

Input

3 6

1 2 2

1 3 4

2 1 3

3 2 4

2 3 1

1 2

 

Output

6

 

Input

5 7

1 2 8

2 3 4

3 2 1

4 1 3

3 4 5

1 4 2

3 1 6

5 2

 

Output

8

 

 

これだけだと少なすぎるので答えようが無いと思いますが、大体こんな感じです

あえて答えはここに書きません 多分Twitterで調べれば答えが見つかると思います

Googleのサービスは金輪際使用しません

 

 

懇親会後、10名くらいでまたしても中華街へ

中華街、料理が美味しいので無限に食べられてしまう 危険

なんとsmikenさんが全員分奢ってくださった...(ありがとうございます)

お礼にJAGの宣伝をしておきます

 

jag-icpc.org

 

Day.3

グループCの企業見学に行く

Google最高！一番好きな会社です！

NEC最高！一番好きな会社です！

 

お昼はしながわ水族館 大はしゃぎする

 

 

お恥ずかしい限りです...

 

その後3社目のHuaweiへ行き、解散する

新宿で集合してICPC勢とボドゲカフェに行ってたっぷり遊んで解散

 

 人を殺さないこと

 

こうして初めてのICPCが終わりました

risujirohとチームを組むことが決まったのが1/20

idsigmaさんがチームに入ったのがその翌日

気付けば約10ヶ月間 あっという間でした

本当に楽しかった お疲れ様でした

 

ところで

idsigmaさんが今年で引退なので、弊チームの来年の新メンバーを募集しています

 

 

 

後日談(2020/11/08)

久々にAOJ-ICPCが更新されて、ICPC2019の問題も登録された

ウキウキで当時のコードをAOJに投げ直すとWAが出る

 

？

 

色々と調べると、2つのことが分かった

1つ目は、AOJで過去にACしているコードを投げ直してもWAが出たことから、AOJのジャッジが壊れていそうだということ

2つ目は、当時のコードがvectorの範囲外参照をしているということ

 

？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

 

弊チーム、完数マイナス1です...

_aizu/status/1195569694251503618?s

8?s=20