チーム練記 2/4 2019-2020 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)

需要があるらしいので書こうと思います

2019-2020 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)

The atama主催の3チームバチャ(The atama, Heno World, 弊チーム)

codeforces.com

risujirohにコドフォのチーム名をQWE_QWEにされる これ絶対ICPC本番までにはチーム名変えるからな

 

risujirohは私用で途中参加の為、Rubikunとkort0nの2人でスタート

初動はRubikunがAから読み始め、僕がGから読み始めることになる

 

Gを読み始める 読解に5分くらい掛かってキレる まあでもそんなに難しくなさそう

Gを読み終わると、何とCDEがぼちぼち通っている は?

RubikunにCを読んでもらい、Dを読むことにする

何とA>Bの間はAを小さくし続けて、最後に足すだけ 簡単ですね〜〜〜

ニッコニコでsubmit

 

f:id:kort0n:20200208011820p:plain

 

なんで?

 

ソースコードを読み返す 奇数判定を x & 2 と書いている あまりに頭がついていない 書き直す AC(0:11)

 

Eを読む うんうん、連続する部分文字列であって、同じ文字が2回以上現れないものの数え上げか〜 これ見たことあるな 尺取りでホイだね

RubikunがCを解けたと言っているが、カスなので「Eすぐ書けそうだし先書かせて〜」と言ってキーボード使用権を強奪する

ウッキウキで実装

 

サンプルが合いません

 

サンプルが合いません

 

サンプルが合いません

 

サンプルが合いません

 

サンプルが合いません

 

かなり死にたい気持ちになってくる 「ごめん、Eなんか合わないからC先にやって...」と言う

 

落ち着いて問題を読み返す よく読むと、「(連続していなくてもよい)部分文字列であって〜」であった カス...

f:id:kort0n:20200208015734p:plain

当時のメモ共有用スプシ 尺取りやるだけ(笑)

 

この間にRubikunがバッチリCを通す(0:25) あと確かこの辺でrisujirohが合流する

 

流石に誤読しなければEはクソ簡単 各文字列出現回数を数えて掛けるだけなので実装もクソ軽い

 

急いで実装してsubmit

 

f:id:kort0n:20200208012657p:plain

 

なんで?

 

え、流石に解法は間違ってないと思うんだけど 何で落ちるんだ オーバーフロー?というかこの問題どう考えても答えlong longに収まらなくないか?

 

 

問題文をよく読み返すと

f:id:kort0n:20200208012855p:plain

 

 

 

 

 

 

 

お分かりいただけただろうか

 

 

f:id:kort0n:20200208012937p:plain

こんな端のところに書かないで...



頭を抱えながら修正 AC(0:29)

順位表的に恐らくこの3問が所謂自明枠だったのですが、圧倒的活躍によりチームのペナを破壊する

 

順位表を見て通ってるのに手を着けることにする 確かRubikunがAでrisujirohがBで僕がLだったと思う

 

Lを読むけど分かりません ウケ

こういうのはrisujiroh担当!と言ってrisujirohに投げてIを読む

 

Iを読む 最大安定集合を求める問題になることが分かる

ぼく「最大安定集合ってこのサイズは無理だよね」

risujiroh「普通は無理だね 二部グラフとかなんじゃない?」

ぼく「えーこれ二部グラフなのかな (考えると、S="aab"とかで二部グラフにならない) いやならんわ」

 

よく分からんのでIをrisujirohに投げる AをRubikunに投げられたので読む

なんか全方位木dpすれば通りそうだけどいきなり実装入ると破滅しそう そんなに実装軽くもなさそうだし後回しかな〜などと考えていると、またIの話になる

 

risujiroh「これ入力長の制限って無いのかな 集合のサイズ決まってても長い文字列来ると入力でTLEしないか」

ぼく「それは思った まあその辺はよしなにやってくれるんじゃない」

risujiroh「これよく読むと同じ文字は2度現れないって書いてあるぞ だから高々26文字だ」

ぼく「あ、そうなんだ      ん?」

 

 

 

 

 

数分前ぼく「えーこれ二部グラフなのかな (考えると、S="aab"とかで二部グラフにならない) いやならんわ」

 

 

 

 

 

ぼく「え、ごめんじゃあ二部グラフになるかも」

 

 

考えると、この条件のもとだと結局二部グラフの最大安定集合問題になる risujiroh、超能力者か?

 

risujiroh「じゃあ解けるね フロー書くかー」

ぼく「え、二部グラフの最大安定集合ってUnion Findで出来なかったっけ?」

↑やめたら?橙コーダー

 

結局risujirohが実装する AC(1:09)

 

この間にRubikunが読んでよく分からんと言っていたMを投げられる RubikunにはかわりにLを投げて、Mの概要を読む

 

え、これでは?

 

最近解いた問題の弱体化版なので流石に秒で解ける 序盤の個人の動きが酷すぎたので、ちゃんと仕事が出来そうで安心 実装してsubmitする

 

f:id:kort0n:20200208014748p:plain

なんで?

 

RubikunがLを解けたと主張していたのでPCを譲りデバッグする

コードを読み返すと、H+1列あるのに二次元座標を一次元に潰すときに掛ける係数をHにしたせいでマスがぶつかってしまっていた カス... 修正してAC(1:28)

 

RubikunがLを実装している間にAの遷移式を詰める

RubikunがLをACする(1:38)

その後Aを実装する 「15分くらいかな〜」と宣言して実装したら16分で実装が終わった ここ冴えてた AC(1:54)

 

risujirohがBの実装を始める 確かRubikunはFを読み始めて、ぼくはGに戻る

 

暫くするとGが解ける BのWAが取れず辛そうだったので、PCを譲ってもらってGを通す(2:22)

 

Hを読む 別の点にぶつかるまで直線を回転させるとかいう意味不明幾何 なんだこり 無理だろ

 

f:id:kort0n:20200208015627p:plain

自分に正直

 

risujirohにBを相談される なんかよく分からんけどバグが見つかった(のか?) よく分からんけどなんか通る(2:38)

 

Hが意味不明なので「これは捨て判断だろうな〜」と思いながらrisujirohに概要を話すと、2分くらいで解法を出してくる なんだこいつ

 

結局本質は幾何パートではなくグラフパートだった為、実装を投げられる 泣きながら実装をする

この間にRubikunはFを、risujirohはJを考える

 

途中誤読によるミスもあったが何だかんだで修正できて通る(3:37)

 

この後risujirohがJの実装を始める ぼくはFを考え、RubikunがKを考えることになる

 

しばらくrisujirohが頑張るもWAが取れない 4:20時点でrisujiroh離脱 さようなら...

 

risujirohがJと格闘している間にFの考察はほぼ終わっていたので、Fの実装を始める 40分もあれば余裕だと思っていたが、途中考慮漏れがあったことに気付いて焦る ヤバイヤバいと言いながら必死に修正する 何とか通る(4:57)

 

f:id:kort0n:20200208020616p:plain

11完 ペナ1345 Gymの順位表で13位

 

Heno Worldが全完しててえげつない risujirohフル参加なら@1完は増えていたかもしれないが、Kは多分無理...

別日にバチャをした学科の先輩のチームにも負けていて悲しくなった

まあでも新チーム初陣にしては上手く動けてたかなと思います チームとしてのパフォーマンスを向上させていきたい

ARC014 魂の還る場所

https://atcoder.jp/contests/arc014/tasks/arc014_3?lang=ja

f:id:kort0n:20200108000344p:plain

解法

各ボールの色の偶奇性に着目すると、各色円筒に入れられるボールの数が奇数であれば、その色のボールは最後に最低1個は円筒の中に残る。

則ち、答えの自明な下界として、#{色c|円筒に入れられる色がcのボールは奇数個}が考えられる。

以下この答えを達成可能であることを示す。

以下のように状態A, B, C, Dを定める

状態A:円筒が空

状態B:円筒に1個のボールが入っている

状態C:円筒に2個のボールが入っている

状態D:円筒に3個のボールが入っており、この3個は異なる色であり、更に次に入るボールと同じ色が端に存在するか、もうボールは入らない

実は、操作中、円筒がこの4種類の状態のみを取るように出来る。

状態Aのとき

次のボールを入れれば状態B

状態Bのとき

次のボールが円筒の中のボールと打ち消し合えば状態Aへ遷移する。そうでないならば状態Cへ遷移する。

状態Cのとき

次のボールが既に円筒に入っている2つのボールのいずれかと同じ色なら、それと打ち消し合うように入れれば状態Bに遷移する

そうでないならば、更にもう1つ先のボールを見つつ適切な方から入れれば、状態Dに出来る。

状態Dのとき

状態Dの定義から、適切な方からボールを入れれば状態Cに出来る

 

以上より、操作中常に円筒を状態A,B,C,Dのいずれかに保つことが出来る。

以下、このように操作を行った際の最終状態を考える。

 

#{色c|円筒に入れられる色がcのボールは奇数個} = 0のとき

偶奇性に着目すると最終状態はAかCだが、Cになる為には同じ色のボールが円筒内に2つ存在する必要がある為、不適。よって、最終状態はA。

 

#{色c|円筒に入れられる色がcのボールは奇数個}=1のとき

偶奇性に着目すると最終状態はBかDだが、Dになる為には同じ色のボールが円筒内に2つ存在する必要がある為、不適。よって、最終状態はB。

 

#{色c|円筒に入れられる色がcのボールは奇数個}=2のとき

偶奇性とボールの個数に着目すると、最終状態はCであると分かる。

 

#{色c|円筒に入れられる色がcのボールは奇数個}=3のとき

偶奇性とボールの個数に着目すると、最終状態はDであると分かる。

 

そして、これらは全て前述の下界と一致する。

 

実装例:https://atcoder.jp/contests/arc014/submissions/9337970

ICPC 2019 Asia Yokohama Regional 参加記

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の風船をアピールすると、無限に親指を下げられた サイコ〜w

 

risujirohがDの実装を始める

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

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

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

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

無事 AC

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

 

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分早めると言っていませんか?」

 

・・・

 

(^v^)????????????

 

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

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さんが今年で引退なので、弊チームの来年の新メンバーを募集しています

_aizu/status/1195569694251503618?s

8?s=20

The 2019 ICPC Asia Seoul Regional Contest 参加記

 okimochi(idsigma, risujiroh, kort0n)で韓国に行ってきました

出発前夜

準備は...ちゃんとしよう...!

公式サイトどれだけ探しても持ち込み資料についてのルールが見つからなかったので、去年Seoul Regonal Contestに参加したbeetに色々聞いて準備しました ありがとうbeet

 

Day.1

 

ハングル1文字も読めなくてビビる ただの記号にしか見えない

空港は大体看板に日本語も書いてあるのでイージーだったが、電車等では基本的に駅名が韓国語でしか表示されないのでかなり大変だった

 

何やかんやでホテルに着く 往復航空券+3泊4日ホテルが3人合計で100k 安すぎておったまげた

 

安宿だからかホテルWi-Fiがあまりに貧弱 まぁ通信容量無制限の海外用ポケットWi-Fi契約してきたしこれを使おう...

...と思うが、何故かポケットWi-Fiがここで不調に かなり険しい気持ちになる

貧弱Wi-Fiに繋げてなんとかクレームを付ける とりあえず空腹なので外で店を探す インターネットも無しに異国の地を歩くの不安すぎた

 

Day.2

寝て起きたら昨日投げたクレームに対応してくれて、ポケットWi-Fiが繋がるようになっていた ありがてぇ...

そして外出する準備をしていると

なんで?

まあ結果的にライブラリの要求仕様は去年と同じだったので問題無かった ありがとうbeet

 

practiceが昼からだったので、それまで近くのショッピングモールを適当に散策する

これすき

これすごい

これおいしい 日本にも出店して

 

良い時間になったのでpracticeに向かう

 

横浜が基本英語進行だと聞いていたのでソウルも英語進行だと思っていたが、入場案内が韓国語でかなり焦る やばい

何だかんだでその辺のスタッフが英語通じたので何とかなった

 

注意事項説明は英語と韓国語両方だった 助かった

「コンテストルームに入ったら、指示があるまでは"DO NOT TOUCH ANYTHING." 失格になります。 "DO NOT TOUCH ANYTHING."」と一生言われてた 多分"DO NOT TOUCH ANYTHING"カウンター30くらい

 

コンテストルームに移り、practiceが始まる

問題は2018 Seoul Regonal Contestから3問

Practice Aは去年のD

Practice Bは去年のE

Practice Cは去年のL

 

 

去年のE...?

 

(解いたことが無い人はこの先を読む前に是非解いてみてほしい

Dashboard - 2018-2019 ACM-ICPC, Asia Seoul Regional Contest - Codeforces

多分考察は新ABC-E程度で、実装は新ABC-E強〜新ABC-F弱程度だと思います)

以下Seoul Regional Contest 2018の重大なネタバレ有り

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

何なのかと言うと、こういうことです

https://twitter.com/kyort0n/status/1188019884766023681?s=20

https://twitter.com/kyort0n/status/1188019884766023681?s=20

f:id:kort0n:20191111121847p:plain

コドフォジムの順位表

 

Eのペナルティを見るとヤバさが分かると思います

 

 

去年のセットはチーム練しており、そのときはAはidsigmaが通しており、BとCは僕が通していた

まあpracticeでは流石に1人1問実装した方が良いということになり、BとCの一方をrisujirohに譲ることにする

risujiroh「どっちやればいい?」

ぼく「Bやって(即答)」

 

 idsigmaがAを通したので、Cをやる エディタをいつも通りの感じにするのが思ったより大変ということが分かってビビる 結局色々妥協するもかなりやりづらくて、初めて実装したときより時間が掛かる

 

riujirohがBを実装して提出すると、WRONG ANSWER

ぼく「よし!!!!!!!!!!!!!!!!!!!!!」

 

時間がないのでコーナーケースを教える ブチ切れてた

 

何だかんだで皆慣れないエディタに苦戦する等の要因で時間ギリギリに 余った僅かな時間で何となくCLionを弄ると、その使いやすさに感動...

ホテルに戻るとこのリプライが届いている

韓国、あったけぇ...

調べたら789の方だったらしい 本当に有難うございました

 

 

CLionの最低限の使い方を覚える 「明日構文解析出たらよろしく」と押し付け合いながら就寝(弊チームは構文解析担当がちゃんと決まっていなくて、いつもは大体手の空いた人がやってます)

 

Day.3

朝が早い

集まると改めて諸々の説明をされる この日の"DO NOT TOUCH ANYTHING"カウンター20くらい

コンテストルームに移る 周りのチームが普通にマウス触ってPCのスリープモード解除しててウケる 前3チームくらい連続して普通にPCのスリープモード解除されてる 治安が悪すぎるだろ

まあスリープモード解除されるくらいは事故でもありそうだし仕方ないかなと思うが、いくつかのチームが開始1分前時点でスリープモード解除した上にログイン画面まで進めていた それはシンプルに不正じゃないか?

 

コンテスト

idsigmaがABCDEFを読み、risujirohがGHIJKLを読み、ぼくが最初にエディタの設定をすることになっていたので、する

エディタの設定を終えると、「EFGHを読め」と言われたので、読む

E:なんか出来そうな見た目 なんかうまい貪欲とかありそうじゃない?←なさそう まあ後回し

F:あーなんか今年の幾何問題不可能そうだな... とりあえずrisujirohに後で読んでと言って放置

G:なんだこれ むずそう

H:出来なくはなさそうだけど、多分解けても実装重いだろうな 後回しでいい

 

idsigmaにIが簡単そうだと言われる 読むと確かに簡単で、実装を始める

なんかこの頃にはもうAが通ってたらしい いつ通ったんだ?

無事実装を終えるも、サンプルが合わない 何故か「隣接する2点の距離をans以下にする」ではなくて、「隣接する2点をans以上離す」で実装してしまっていた は?

 

一旦PCをrisujirohに譲ったらJが通ってた その後Iを通す

その直後、idsigmaにLの解法を伝えられる これはバグらせずにサッと実装して通す

 

「B得意そうだからやって」と言われ、問題概要を伝えられる

考えると、うまいこと部分木の情報を1つの値で表して木dp出来ることが分かる

しかし、risujirohが「これ最大ケースだとlong longでオーバーフローしないか?」と言い始める 確かに...

「とりあえずlong longで提出して、落ちたらint128で書き直して再提出しよう」と言って、実装を始める int128の出力を書くのが面倒だったので説得出来て良かった

 

しかし、ここで伝達ミスで、「全ての葉のペア」ではなく「全ての頂点のペア」だと思って解いてしまっていたことに気付く 大まかな解法が壊れる訳ではないが、遷移式が書き直しになる 伝達ミスは最近のチーム練でも何度もやらかしてたので気をつけてないといけないと思っていたのに油断してしまった...

更に最悪なことに、元のコードを少し弄ったらスパゲッティになって酷いことになる コードを印刷して、Hが解けたと主張するrisujirohにPCを譲る

 

暫くしてバグを発見して直すとサンプルが合う 提出するとAC これに1時間くらい掛かったの本当に酷かった...

 

 

ところで

これがICPC

 

順位表を見るとKがそこそこ通っているので読む

未証明だけど、ある平面を固定したときにそれらを跨るような点の取り方をするのは損だなぁ(雑)という気持ちになる 平面の取り方を全探索すると、これでO(N^4)となる

この先は幾何っぽい考察が必要だねという気持ちになる risujirohがHを通したので、これの続きを投げて、自分はGに移る というか、このセット実質幾何が2問か...

何かこの辺で順位表が凍結する 2年くらい前の韓国大会でも1位チームが残り1問になった時点で凍結されたと聞いたので今年もあるかなと思っていたが、実際1位のCafe Mountainが残り2問になった時点で凍結された 自由すぎるだろーと思っていたけど、そういえばルールで順位表凍結時刻は指定されてないんですよね...

 

Gを考える 色々考えると、左から順番にdpをすれば良いということが分かる これ遷移式が、「2つの異なる区間の中の最小値のうちのmin + 1」みたいになるんですよね こんな遷移式初めて見た...

とりあえず区間minを愚直に求める方法で甘えて残りを実装すると、無事サンプルが合う あとはセグ木を写経して区間minを高速に求められるようにするだけ 勝ったな!

ウッキウキでセグ木を写経してサンプルを試す バグる 人は何故...

写経をミスっていました 提出するとAC

risujirohが「Kの平面全探索は軸を1つfixして、もう1つ通る点を偏角ソートで順番に見ると高速に更新出来るから間に合う」と言い始める なんだそれ やべー

risujirohがKの実装を始める 残りの問題のうち手が出せそうなのはCとEあたり Fはrisujirohが多分無理と言ったので諦める Dはなんも出来る気がしない(これも結局伝達ミスで問題を勘違いしていたんですが...)

眺めていると、Eが解けた気分になる Kと並列で実装を始める(お互い詰まったら印刷して交代)

Kのサンプルが合ったらしいので提出するが、WA というかKのサンプル貧弱すぎるだろ

その後Kを何度か提出していたが、全然通らなくて辛そう

Eの実装が終わる サンプルを試すsample2~sample4はok sample1の3番目の答えだけ合わない

まあこれは後は少し境界条件が間違っているだけだろうという気分になる

暫くしてKが通る なんか尺取りでバグっていたらしい?

 

KをやっていたrisujirohにEの現状を伝える すると、

「サンプル1で3番目の答えって2で合ってるんじゃないの?これとこれとこれを取り除いたら連結成分数2つになると思うけど」

と言われる 確かに?????これ出力例間違ってないか?????

出力例のミスを信じてsubmitすると、一瞬でWAが返ってくる そういえば3番目の答えは頂点を2つ取り除いたときの答えでしたね......

 

残り10分くらいになっていよいよ大幅な書き直しをする時間は無くなってきたので、ドキドキソート評価関数ガチャを始める(こういうのあまり好きじゃないんですが、流石に時間が無かったので...)

結局通らずに終了 以上8完1043ペナでした 凍結時点では1位10完投Cafe Mountain 2位9完789で3位以下は7完以下だった為見た目の順位は良いが、まあ凍結から2時間経ってるのでよそのチームも沢山通しているでしょう...

 

反省点

Bがすぐ通せないの最低 伝達ミスを考慮しても遅すぎる

長いこと順位表が凍結されていたので周りの情報は分かっていなかったのだが、終わってみればEはオンサイト1ACの地雷問だった これ手を付けるべきではなかったのかもしれない...(オンラインミラーはそこそこ通ってた) まあ僕の解法はO(N^2logN)だったんですが、どうやらこの問題はO(N^2logN)はTLがかなり厳しかったらしい?じゃあ実装出来てても厳しかったんだろうか そもそも自分のが本当に合っていたかは分からないんですが

HとKで「試す順番を工夫すれば更新が高速に行えるので計算量を落とせる」に気付かなくて解ききれなかった これ苦手分野なのかもしれない...

 

コンテスト後

日本勢いつものperiscopeをする しかし進行が韓国語...

結果は11位でした

10位以内に入ることも出来なかった 良い順位ではないんですが、でもこれは冷えではなくて多分実力相応くらいなんですよね...

話を聞いてなくて壇上に呼ばれることに気付いていなくて、慌てて壇上に向かう 慌てていたのでiPadを閉じてしまい配信が途切れる 配信聞いてた人すまんな いや11位で表彰されるとは思わなくない?

 

1位のCafe Mountainが全完だった えぇ...

 

 

この夜は何も無かった いいね?

 

Day.4

 

次は来週の横浜ですね 横浜でお会いする皆さん、宜しくお願いします

HACK TO THE FUTURE 2020予選

HTTF2020予選に参加しました。結果は22位(4963718点)でした。

① 正の得点(48047点)

Text(cat)

0

atcoder.jp

f:id:kort0n:20191103002522p:plain

6秒、なに?

② 拡張Dijkstra解法(4961249点)

(座標, 向き)でグラフを拡張して、直進はコスト0, 方向転換はコスト1のedgeを張って、拡張Dijkstraをする。則ち、「このマスでこっちを向いているロボットがいるとき、いくつの方向案内を新たに置けばゴールに着けるか」を求める。

コストが正であるロボットのうち、最小のコストを持つロボットについて、ゴールに着けるように方向案内を置く(そのようなロボットが複数存在する場合は、インデックスで最小のロボットを採用する)

再び拡張Dijkstraを行う。これを、(ゴールまで到達する道が存在するような)全てのロボットがゴール可能になるまで繰り返す。

実行時間は約100ms

 

atcoder.jp

f:id:kort0n:20191103003745p:plain

言語は...確かめよう!

 

③ 拡張Dijkstra + ロボットのインデックスシャッフル(4963153点)

②はロボットのインデックスに応じて結果が変わる。

Time Limit 一杯まで、毎回ロボットのインデックスをシャッフルして②を繰り返す。

 

atcoder.jp

④ 拡張Dijkstra + ロボットのインデックスシャッフル + 不要な方向案内削除(4963718点)

最後に不要な方向案内を削除する。

 

atcoder.jp

 

その他試したけど無意味だったこと

コストが同率な複数ロボットが存在するとき、ゴールまでの距離が最小(最大)のロボットを採用する。

スコア下がった

ロボットのインデックス順で焼きなまし

一回のシミュレーションで100ms掛かるのに焼きなまし、意味ある?無いね

 

試すべきだったこと

Dijkstraの代わりに0-1BFSで高速化

コスト1種類しか使ってないので当然0-1BFSでok

これ気付かなかったの酷すぎる...「本職がマラソンじゃなくてアルゴだから」とか言い訳も出来ないレベルの失態ですね...

非通過のマスを通過するときボーナス

上位陣のコードをいくつか実行して確かめたのですが、自分のコードと上位陣のコードを比較したところ、Bの差はほぼ無く、Cの差で負けている状態でした。

Cを高める上手い方法が分からなかったので殆ど無視してしまったのですが、こうすれば良かったのか...

 

おわり

ほ゛ん゛せ゛ん゛い゛き゛た゛か゛っ゛た゛

JAG夏合宿2019参加記

JAG夏合宿2019に参加しました

行きの電車内で宿泊所が咲の聖地だということを知り、少しテンションが上がる 特に何もしなかったんですが

https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20

 

https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20

 

最初の参加者自己紹介のときに「risujirohはまだ来てません」と言う羽目になった  こういうの言うの恥ずかしくないですか?遅刻しないで

 

Day.1 okimochi(kort0n, risujiroh, idsigma)

PCとキーボードを並べると思ったよりスペースが狭いので、運営の方に許可を取った上で机を繋げる 社会性の欠片も無い感じになる

とりあえず

A:idsigma

B:kort0n

C:risujiroh

で読んで、分かった人から実装しようとなる

読むと分かったので実装して通す そこそこ速かったのでFAかな?とわくわくしていたが、four-tに1分差で負けていた ゆるせねえ...

A,Cは暫く掛かりそうだったので、後ろの問題を一通り読むことにする

後ろを読むとH,J,Kの解法が生える 今日冴えてるな〜天才だな〜

risujirohにCの相談をされる 話を聞いていると自己解決していた 良かった(?)

その後idsigmaさんがAを通す Kの実装を投げると、問題文の誤読を指摘されて解法が爆発した は?

JはUnionFindとフローの写経が必要なので後回しにしたかったが、流石にHより楽なのは明らかなのでこれをやることにする 伝達も面倒なので自分でやることにする

risujiroh「写経しようか」

kort0n「いや、自分で写経するわ」

と言ってドヤ顔でコーディング席に座ったところで、(普段使い慣れていない)US配列キーボードであることを思い出す

kort0n「ごめん、写経頼むわ...」

写経パート以外は軽いので、写経してもらうと流石に通る

Dをrisujirohと詰めていると、連立合同方程式を解けば良いということが分かる 書けますと言われたので任せると通る

 

満を持してHの実装に入る 大まかな解法は以下の通り

  • 列は、B列ずつM/Bブロックに分ける
  • 各ブロックについて、対応するbの値をvectorに突っ込んで、ソートしておく
  • N*(M/B)個のブロックについて、書かれる数字の数を計算する これは、さっき作ったvectorを使って二分探索すると、1ブロックあたりO(Blog(max a_i) * logB)で出来る
  • クエリをdの値昇順で処理する ブロックは適当に飛ばして、各ブロック内では真面目にやる

(これ改めて見ると計算量ダメですね...これでやってはいけない...)

H実装中に他の2人がEを詰めたらしく、解法を共有されたので、「ただしそう」と言う 「log取るか素数mod取るか」とかでちょっと相談したら、誤差ヤバいしlogはダメだねとなる 実際logでやろうとしてハマったチームもいたらしい logで解決したくなる気持ちはかなり分かる...

Hは実装終わるまでどうせ暫く掛かるし、一旦PCを譲る 最初modを1つのみでやってWAを吐くも、modを2つにしてrisujirohが通す なんか有名素数は対策されていたらしく、有名じゃない素数mod1つで通したチームもいたらしい?

 

再びHに戻る 実装をして投げるとTLE 桁数を求める関数を極僅かに高速化したり、バケットサイズを適当に調整したりして何度か投げるもTLE

risujirohがKは二次元畳み込みで解けますと言う Hは泥沼感が出てきたので代わるとKが通る

再びHに戻る バケットサイズの調整の為に、前半パートに掛かる時間等が知りたくなる こういうときはsubmitデバッグが便利なんですね

submitデバッグをすると、なんかバケットサイズとかの問題じゃなくて計算量落とさなきゃ無理なのでは?という気がしてくる ここでHを諦める 何とTLEとsubmitデバッグを含めて14submit... PC長時間占拠したしこれは完全に戦犯ムーブでしたね...

 

順位表を眺めると、Gを通すべきだという話になる 考えても何も分からない

risujirohがdpテーブルは想定解通りにちゃんと定義出来たようだが、実装ミスか遷移式ミスか何かで一生サンプルが合わず、コンテストが終了する

 

f:id:kort0n:20190916224735p:plain

14

結果は7完最速の8位(オンサイト4位)で冷えっ冷えだった 誤読嘘解法人に投げるし写経要求で人の時間奪うしHで一生PC占拠するし、完全に戦犯をした...

コンテスト後てんぷらさんに「おきもち冷えすぎだろ」と煽られる キレそう

 

解説を聞く Hで浮動小数点数的な考え方をすると計算量がlog(max a_i)落ちるのか〜天才だな〜

感動しながら再実装して投げる

f:id:kort0n:20190916225514p:plain

やーめた

コドフォに出たかったが、回線難民で出られなかったので、談話室のボドゲ会に参加する 楽しかった

海底探検の最終ラウンドで欲張って無事帰らぬ人となりました

Day.2 Seica_no_okimochi(kort0n, risujiroh, seica)

idsigmaさんは私用で不在につき、seicaちゃんをチームに招き入れる

問題が難易度に依らず全問シャッフルらしいので、とりあえず各人がmod 3で問題に目を通すことにする

自分はA, D, G, Jを読むことになる Aが簡単なので取り組むことにする

連結成分を調べたいのでUnionFindを写経する 見事5箇所ほど写経ミスする US配列を許すな

写経が終わると流石に通る seicaちゃんが「Eがギャグ」と良い、サッと通す

Dが解けたので実装する 肺が0個と判定されたときの出力を誤って1WAするが通る

Fを考察していたseicaちゃんが、「†一般マッチング†に帰着された」と言い始める 嘘だろ?と思いつつ話を聞くと、†一般マッチング†に帰着されたことが分かる まあこの問題固有の上手いやり方があるかもしれないし、手を付けるかはオンサイトAC状況を見つつ決めようという話になる(オンラインACはライブラリコピペで終わるので参考にならない)

CGHJあたりを適当に読んで考察する Cは何となく最小費用流っぽい話になりそうだなーと感じる GHJは何も分からない...(Jの勝利条件が分からないのは流石に酷すぎる)

risujirohがIを解いて実装する WAを連続で出していて辛そう 暫くすると解法を共有される

聞いた感じ合ってそうだけどなー 「あまり通ってないし、とりあえず後回しにしよう」と言ってトイレに行く 戻ってくるとジャッジミスがあったらしいと言われる かなしいね

暫くすると、seicaちゃんがjの最適戦略を導き出す これを使って勝利条件をまとめる 最初自分のミスで20分くらい無駄にした は?

勝利条件を元にして、seicaちゃんが答えを表す式を立てる 変形するとN-1乗和の公式に定数倍掛けたものを足したり引いたりした形に変形出来ることが分かるので、多項式補間で出来ると分かる これをrisujirohが実装する

暫くサンプルが合わなかったが、標本点を選ぶ際に偶奇性に注意しないといけないことに気付いてサンプルが合う AC これは熱かった

Bについて話し合うが、全員口を揃えて「これ最大流問題を部分問題として含むし、フローは明らかに無理だし、何かおかしくないか?」と言うということでclarを投げる

f:id:kort0n:20190916235350p:plain

仰る通りでございます。

「全てのedgeのcapが等しいならdinicは速い」ということを知らなかったせいで、このようなクソclarを投げてしまいました。clar対応の皆様、本当に申し訳ございませんでした...

Cを改めてちゃんと詰める 最小費用循環流っぽいことをやればokだということが分かる Primal-Dualの写経をrisujirohに頼んで、Cを実装する 添字ミスで1WA吐くも無事AC この時点でオンサイト1位になって思わず叫ぶ

Gを詰めていたseicaちゃんが実装に入る risujirohにO(N^2)でいいからHのdp解を書いてみてくれと言われる ちなみに一旦計算量の悪い解を僕が書いて、その数式をrisujirohが変形して高速化するというのは弊チームの常套手段で、RUPC2019 day3の赤黒そーるじぇむでもこういうことをしていました

O(N^2)解のdp遷移式を立ててrisujirohに渡す この時点で残り時間は30分ほど 計算量が落ちたときにすぐに実装出来るように階乗逆元等の準備も兼ねて、埋め込みも視野に入れつつ、Gで辛そうだったseicaちゃんにPCを譲ってもらって、HのO(N^2)解を書き始める

この辺りで(これまで完答数が並んでいた)右前のHeno_Worldに風船が届けられる様子が視界の端に映って絶望する

O(N^2)解を書いている途中で、risujirohが期待値の式をO(N)で求められる形への変形に成功する しかし二乗和の期待値は間に合わず、6完で終了となった

 

f:id:kort0n:20190916233007p:plain

6完最速 全体4位 オンサイト2位

7完のHeno_Worldとの差はFだった どうやらFが一般マッチングになるという考察は間違っていなかったようなのだが、Heno_Worldは一般マッチングライブラリが無いにも関わらず、その場でフルスクラッチで書いたらしい heno_codeとかいう男気持ち悪すぎる 本当に無理だ

 

コンテスト後は懇親会があった やはり(日経コンやDDCC等の規模のものと比べて)参加者が少ない懇親会は、色々な人と話そうという気分になれて良いですね

choKOdaiの方々とお話し、「高速ゼータ変換は名前が格好良い」という話で盛り上がる 高速ゼータ変換って格好良くないですか?

突然じゅっぴーにじゃんけんを挑まれたので戦って勝つと、大量の名札を押し付けられた上に、カツアゲ呼ばわりされる なんで?

 

 

懇親会後はwriterを務めたABCがあった 談話室で大勢の人が参加していたので、同じくwriterだったbeetさんと眺めていた

????_code「良い問題でしたね E問題だけに」

らてさんと初めてお会いする らてさんは完全に酔っ払っており、名乗ると突然

「うんこるとんじゃん!!!!!!!!」

と言われた(参考:TTPC2019参加記 - kort0nの日記)

その後5回くらい「やむなくさんですか?」と聞かれた 「えーだって黒髪で眼鏡掛けてるし」と言われた やむなくは眼鏡を掛けていなくないか?

potetiさん曰く、らてさんはやむなくに会ったことが無いらしい 何から何まで意味が分からない

Day.3 kaisan(kort0n, risujiroh, heno_code)

idsigmaさんとてんぷらさんが同時に作問チームに入っている日があることは分かっており、okimochiとHeno_WorldのContestantがちょうど3人であった為、組むことにした

わかるなあ(得意ジャンルという得意ジャンルが無い人なので)

当日コンテスト会場に集まると、henoがビズリーチTシャツを着ている これは...?

f:id:kort0n:20190917000828p:plain

f:id:kort0n:20190917000842p:plain

そう、これはHeno_WorldがICPC2019国内予選ラスト40秒でEを通し、我々から奪い取った(?)企業賞のTシャツである ゆるせねぇ...

「ふざけやがって チーム解散だ」と言うと、「じゃあチーム名解散にしましょう」と言われる こうして謎チーム名"kaisan"が誕生する 何?

 

とりあえず

A:heno

B:kort0n

C:risujiroh

で読むということになる また、D以降はhenoがメインのコーダーを務めるということになる 弊チームは基本的にコーダー担当のような人はいない為、少し新鮮で楽しみ

henoはAがすぐに分かったようで、書き始める

自分も数分掛かったがBが分かる

risujirohにCの相談をされる 無証明だが流石に正しそうな貪欲解法...

「実装量は多分同じくらいで、Cは解法が少し怪しいけどBは流石に合ってるからBからやろう」と言う

Aが通った後Bを実装する ドヤ顔でsubmitする

f:id:kort0n:20190917001624p:plain

Cは解法が少し怪しいけどBは流石に合ってるからBからやろう

本当に死にたくなった

更に悪いことに、自分のコードのバグが見つからない 最悪だが後ろを読んでいるhenoに相談して、デバッグをしてもらう

無事バグを発見してもらう Cをrisujirohが通した後、Bを通す 3完は2位以下に結構な差を付けたハイスピードで1位だったらしい

しかし、自分がhenoに相談して止めてしまったこともあり、ここで実装キューが空になる つらい

F(risujirohが得意そうなタイプの数え上げ)、G(期待値ゲー)、I(数学ゲー)は自分よりrisujirohに任せるべきなので放置自分はDEあたりを読むことにする 「Dが燃やす埋めるで解けました」と言うと、henoに「この形は二部グラフじゃないと無理」と言われ、risujirohに「制約的に間に合わない」と言われる ごめん...

risujirohがJのN=2べきでの構築に成功する 2べき以外で失敗することは証明出来てはいないが、まあそれっぽい結果だしとりあえず投げてみる しかしWA

相談も挟みつつ色々考えていると、自分とrisujirohでHの解法が生える しかし実装が重そうだなぁ...

henoに解法を伝える

kort0n「でもこれどうやればいいんだろうね UnionFindでマージテクするけど、そのときそれぞれのUFに辺の情報を持たせて...」

heno「あ、実装方針は任せてください」

た、頼もしい...

そうは言いつつ結構時間が掛かるだろうし、とりあえず他の問題を読もう Dはよく考えると2-SATの形になるね でも辺がかなり多くなりそうで...

heno「サンプル合いました」

...は?

heno「通りました」

この男本当に無理だ 気持ち悪すぎる

 

Jを考えると、それっぽい解法が生える N=4, 6, 8で手元で試すと正しく構築出来る

これをhenoに頼んで実装してもらう すると、N=10で破滅することが分かる 死んでくれ

その後risujirohがGを解く henoが実装すると見事AC

再び実装キューが空になる henoも考察を始めると、henoがEを解き、実装を始める

自分は再びDに戻ると、辺を貼るパートが3^N全列挙で出来て、実は辺がそんなに多くならないことが分かる

risujirohがIを考察すると、綺麗な畳み込みの式になって解決する(僕としてはこれが解けるのもかなり気持ち悪いんですが...)

何とここに来て3問ほぼ同時に実装キューに突っ込まれる これは興奮した

henoがEをバグらせた為、印刷して一緒にデバッグをする その間にrisujirohがIの実装を始める

一緒にデバッグをすると(結局はhenoがほぼ自己解決したのだが)バグが見つかり、Eを通す その直後にrisujirohがIを通す これで単独7完で1位に

その後はhenoがDの実装を始める 残り時間的にあとは実装が重い問題を解いても意味が無い為、解ければ実装が軽そうなJをrisujirohと考える しかし解けない Dの実装も間に合わず、時間切れになる

f:id:kort0n:20190917005225p:plain

7完で優勝!

 AC数はeiyatonariと同じでしたが、ペナ差が効いて優勝しました やったー

 

その後はJAGの方+potetiさん+risujirohと万豚記に行きました 「茄子豚ピリ辛炒め」を注文したら、連続部分文字列であるところの「酢豚」が出てきました

楽しい3日間でした JAGの方々、作問チームの方々、本当に有難うございました。

TTPC2019参加記

前日

りあんさんとおぎんぎんさんとシナモロールと4人で麻雀を打ちました

 

犯罪をしました

 

当日

会場に着き、運営からのチーム説明や会場使用上の注意等を聞いていると、チームメイトのシナモロールからDMが飛んできました

f:id:kort0n:20190901003536p:plain

は?

ご丁寧にチームアカウントが作成されていました。

「アイコンに丁度良い画像無い?」と言われました。ねえよ。

f:id:kort0n:20190901003757p:plain

アイコンだけはオンサイト感溢れる微笑ましいものになりました

コンテスト開始

実は前日の麻雀の際に軽く相談をして、「シナモロールが前半の問題を通し、その間にkort0nが後ろで簡単なものを探しておく」作戦を取るという話になっていました

 

しかし小学生2人組はこのチーム名を解説スライドに載せたくなってしまった為、

こ「FA取りたくね?」

シ「分かる BかCあたりでFA狙おう FA狙いで最初の1問だけ実装して」

こ「ok」

となりました。

 

開幕Bを開きます

これは開始地点を2重に回して、それぞれの部分文字列がokyo,echであるか調べればok!FAは貰った!

サンプル実行!

 

Segmentation fault (core dumped)

 

                                    終
                                  制作・著作
                                  ━━━━━
                                   ⓃⒽⓀ

 

結局元の作戦に戻って、G以降を読むことにしました

G:これは出来そう ただ細かいところ詰めないといけないからすぐにやるべきではない

H:絶対データ構造ゲーだ...

I:ノーチャンではないかもしれないが、他の問題やってからでいい

J:うーん出来そう(しかしこのとき何となく考えていた解法は完全に嘘)

K:はいヤバ枠(←は?)

L:もう開かん

M:苦手分野 多分ヤバ問題ではないと思うのでシナモロールに投げたい

N:要はユーリ君が整数を選べるということが大事っぽい 出来るのでは?(←は?)

 

ここまで読んだところで、Dまで通したシナモロールにEの構築を投げられる 30分くらい?掛けて通す

後ろの方の問題が全体的に難しめだし、前半6問は簡単枠とは言えEFあたりは骨のある問題だろうし、とりあえず2人でFを通そうという話になる

 

Fを読む これじゃんとなる

実はコドフォで3日前にグループバチャをした問題に、かなり似ている問題がありました これは無向グラフで、V, E<=3000の問題

この問題の想定解は「合流地点と離れる地点を探索O(V^2)」だったのに、今日のFはほぼ同じ問題設定でV<=1e5になっている これはどういうことだ...

2人で分からん分からんと言い合う 有向グラフであることを使う?でも有向グラフであることが良い性質を持っているとは思えないぞ?

Fで詰まって数十分後、おもむろに制約を再確認したシナモロールが気付く

f:id:kort0n:20190901005940p:plain

ん?

f:id:kort0n:20190901010011p:plain

ん?????


DAGやんけ!!!!!!!!!!!!!!!!!!!!!!!

頭を抱える DAGなら流石に出来そう
考える

出来ません

 

数十分掛けてようやくまともなdp解法が生える

実装して投げる WA

泥沼感が出てきたので、6完で終わることは無いだろうし後ろに手を付けようという話になる

順位表を見るとOが沢山通っているのでOをやろうと言われる Oって何だっけ?そういえばOだけ読んでないな

Oを読む これじゃんとなる

幅がギリギリだったので無理やり分岐路を詰め込んで、マジックナンバーをコードに埋め込みつつ無理やり通す

 

 

次は、自分がGを考え、シナモロールがFを考えるという話になる

GがO(N^2)から落ちねーと唸っていると、シナモロールに「違う文字に変更するペアの数で全探索をすると、各答えが綺麗に累積和の形になる」と言われて、確かにと答える 実装すると通る

 

流石にそろそろFから目を背ける訳には行かなくなってくる

考えていると、自分がさっき投げたdpが、"基本的に"最適であることが完全に証明出来てしまう あれ?

流石にコードの内容的にもバグらせているとは思えないし、おかしいなーと言っている

 

こ「これ何で落ちてるって話になったんだっけ?」

シ「こういうの(w<x<y<z)」

 

コードを読み返す 2つのルートが1度も合流しない場合を考えていませんでした................................................................................

直すと流石にACする

 

ここからが困る

「H、セグ木でマージテクすれば間に合いそう」

「それMLEしない?」

「動的セグ木でやればMLEしないし動く」

「確かに 出来るじゃん」

「動的セグ木使える?」

「使えない」

「使えない」

「そっかぁ」

でHが終わる

相変わらずK不可能にしか見えない病を患っているのでKはやろうとしない

Lは開かない

Nは詰めれば出来ると思っていたが、順位表を見て流石にやめる

 

ということで、残りがIJMになる

相談した結果、残り時間的にもあと1問通せば御の字だろうし、お互いに通せそうな問題を頑張って考えようという話になる。

自分はJを頑張ることにする シナモロールはMを頑張る

頑張るが解けません 解けません

終了20分ほど前になると、解法が分かっても実装が重いであろうMは諦め、Jが分かれば実装は軽い問題であることに期待して、2人でJを考える

考えるが解けません 解けません

 

終わり際になってシナモロールに「こういう遷移計算でいいんじゃないか」と言われる

こ「うーん、多分正しくないし、仮に正しかったとしてもN<=10^9だから間に合わないんだよね」

シ「え、N<=10^6でしょ」

こ「え?」

f:id:kort0n:20190901012145p:plain

え?

f:id:kort0n:20190901012210p:plain

え?????

                                    終
                                  制作・著作
                                  ━━━━━
                                   ⓃⒽⓀ

 

 

 

 

 

本当に神バランスの良セットだったと思います。東京工業大学の皆様、FUTURE様、有難うございました。