チーム練記 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, 弊チーム)
risujirohにコドフォのチーム名をQWE_QWEにされる これ絶対ICPC本番までにはチーム名変えるからな
risujirohは私用で途中参加の為、Rubikunとkort0nの2人でスタート
初動はRubikunがAから読み始め、僕がGから読み始めることになる
Gを読み始める 読解に5分くらい掛かってキレる まあでもそんなに難しくなさそう
Gを読み終わると、何とCDEがぼちぼち通っている は?
RubikunにCを読んでもらい、Dを読むことにする
何とA>Bの間はAを小さくし続けて、最後に足すだけ 簡単ですね〜〜〜
ニッコニコでsubmit
なんで?
ソースコードを読み返す 奇数判定を x & 2 と書いている あまりに頭がついていない 書き直す AC(0:11)
Eを読む うんうん、連続する部分文字列であって、同じ文字が2回以上現れないものの数え上げか〜 これ見たことあるな 尺取りでホイだね
RubikunがCを解けたと言っているが、カスなので「Eすぐ書けそうだし先書かせて〜」と言ってキーボード使用権を強奪する
ウッキウキで実装
サンプルが合いません
サンプルが合いません
サンプルが合いません
サンプルが合いません
サンプルが合いません
かなり死にたい気持ちになってくる 「ごめん、Eなんか合わないからC先にやって...」と言う
落ち着いて問題を読み返す よく読むと、「(連続していなくてもよい)部分文字列であって〜」であった カス...
この間にRubikunがバッチリCを通す(0:25) あと確かこの辺でrisujirohが合流する
流石に誤読しなければEはクソ簡単 各文字列出現回数を数えて掛けるだけなので実装もクソ軽い
急いで実装してsubmit
なんで?
え、流石に解法は間違ってないと思うんだけど 何で落ちるんだ オーバーフロー?というかこの問題どう考えても答えlong longに収まらなくないか?
問題文をよく読み返すと
お分かりいただけただろうか
頭を抱えながら修正 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する
なんで?
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を読む 別の点にぶつかるまで直線を回転させるとかいう意味不明幾何 なんだこり 無理だろ
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)
Heno Worldが全完しててえげつない risujirohフル参加なら@1完は増えていたかもしれないが、Kは多分無理...
別日にバチャをした学科の先輩のチームにも負けていて悲しくなった
まあでも新チーム初陣にしては上手く動けてたかなと思います チームとしてのパフォーマンスを向上させていきたい