チーム練記 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は多分無理...

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

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