HUPC2020 参加記
北海道行くぜ！
どうしてこんなことに...
[重要]
— HCPC 北海道大学競技プログラミングサークル (@hcpc_hokudai) 2020年8月19日
「北海道大学競技プログラミング合宿 HUPC」についてですが，新型コロナウイルスの感染拡大状況を踏まえ，非常に残念ではございますが，オフラインでの開催を中止にすることに決定いたしました．
関係者の皆様には多大なる迷惑をおかけしますことをお詫び申し上げます．
どうして...
チームはどうしようか悩んでたんですが、TLで全然募集ツイ見かけないし皆組んじゃったのかなと思って全日いつものチームで
前日当日に人々がチームメイトを募集していてウケた
Day1(北大セット)
北海道楽しみ〜！！！
— ABC174 276位 (@kyort0n) 2020年9月14日
今日はコンテストに参加した後知床を観に行って、その後ジンギスカンを食べようと思います！！！！！！！！１１１１１
全問(想定)難易度順らしい 初手は
A:Rubikun
B:risujiroh
C:kort0n
で、後はよしなにということに(結局3日ともこれに)
Cを読む 変わった制約に頭を悩ませるが、結局前20個だけ上手くやれば良いと分かる。
AをRubikunが通す。Bは暫く詰めたいとのことだったのでCを先にやることにする。変な探索をしようとしていたので再帰関数で実装を始めるが、素直にfor文で調べれば良いことが分かる。まあわざわざ書き直すものでもないしこのまま再帰関数で...
実装し終わったので提出する RE は？
一旦PCをrisujirohに譲りデバッグを始めるが、バグが見つからない。Bを通したrisujirohにもデバッグに参戦してもらうと、
「これスタックオーバーフローとかしてんじゃない？」
と言われる。いや、まさか
for文で書き直す AC は？
この間にRubikunがDを解いていたらしく、実装を始める。
Eをやれと言われて考える。
各ノードを頂点倍化
各ノードのin -> 各ノードのout
source -> 偶数番目のアルファベットに対応するノードのin
偶数番目のアルファベットに対応するノードのout -> ワープ可能な奇数番目のアルファベットに対応するノードのin
奇数番目のアルファベットに対応するノードのout -> sink
のグラフの最小カットが答えに一致するな！よし！
...絵を描くと分かるが、これ頂点倍化がマジで無意味。二部マッチングの辺を分割してるだけ。
こうして、これが最小頂点被覆問題であることに気付かずに最大フロー最小カット定理を振り回して解く は？
Dが割と炎上していたが無事鎮火したようなので、満を持してEの実装を始める。
サンプルが合ったので投げる。WAが出る。は？
コードを読み直す。
何と、距離がKより長いところもワープ出来るようにしてしまっていた。
修正してsubmitする。WAが出る。何で？
慌ててコードを読み直す。
"A or B and C" という最悪コードを書いていた 初心者か？？？？？？？？？？？？？
kort0n「andとorごちゃ混ぜで書いてたわ...」
risujiroh「あー まあでもandが先に評価されるように書いてれば問題無いよ」
kort0n「andが先に評価されると困る」
risujiroh「じゃあ終わりだよ」
終わってたので修正してsubmitする。ようやくAC。
risujirohがGを解いたと主張していたので、Fを考える。暫く考えると解けた気になる。
risujirohがGを提出し始める。WAやらTLEやらが出て明らかに「「「始まって」」」いた。
暫くしてFが解けた気になったのでPCを奪い取って実装する。提出する。WA は？
考えるが全くバグが分からない。risujirohもGとバトルを続けるが通らない。そのままコンテスト終了...
後で確かめると
F:数え上げの係数を1つ掛け忘れていた
G:計算量は想定解と同じだが、定数倍で落ちていた
だった...
冷えすぎて通話が冗談も飛ばないレベルのお通夜になる。どうしてこんなことに...
問題の感想
C:スタックオーバーフロー許さないからな
D:マジで実装方針で明暗分かれそう 問題自体はまあ好きです
E:典型問題のカモフラージュが上手い 最後の条件判定が辺じゃなくて頂点ベースで書いてあるから全然気付かなかった
F:AのsumとBのsumしか関係無いのかなりビックリで好き(これに気付いたのはrisujirohだけど)
G:ねっとりしてる
H:こういうのから逃げ続けて1年くらい経ってしまった...
Day2(会津セット)
TLで野良チームを組んでいるlatteとtatyamがcatsatmatをもじって*atを名乗っている。たのしそ～
*atじゃないけど認められた たのし～
え？
正直紛らわしかった。マジでごめん。
憎しみを込めてチーム名kottatlatにしてやるか
— あ (@latte0119_) 2020年9月15日
それは違うだろ
コンテストの時間になる。
Cを開く。
kort0n「これもうrisujirohに投げたいんだけど」
risujiroh「じゃあswapするか」
持つべきものは得意分野の異なるチームメイトよ
Bを開く。問題文の長さと中身の面倒臭さで今年一番の笑顔になる。
RubikunがAを、risujirohがCを通したところで実装を始める。
Bの実装に無限時間掛かる。この間にRubikunがDとGを解けたと言う。すげー
Bを通してLを読む。「これどんなケースでもlogステップくらいで終わるんじゃない？愚直にやって終わるんじゃね？」とか言う。
DとGのFAを爆速で回収したRubikunに「↑の反例ある？」と聞きつつ他の問題に手を着ける。Jの解法が生える。risujirohがMを通した後Jを通す。
他にすぐに分かる問題も無くなってきたので、Kを実装する覚悟を決める。この間にRubikunにLのNステップくらい掛かるケースを発見されて萎える。
risujirohがIを通すのを待ってKの実装を始める。途中risujirohがEを解いたので通してもらう。
色々苦労しつつもKでサンプルが合う。提出する。
kort0n「これ落ちたらデバッグは無理です」
kort0n「終わった...」
半分くらい通ったところで落ちているので尚の事絶望感が凄い。
しかし、問題文を読み返すとただの誤読であることが分かる。修正してsubmitするとAC 見たか会津
残りがFHLになって、割と手詰まり感が出てくる。
Lは賢い計算方法なんてありそうも無いし、シミュレーションを高速に行う方法を考える方向にシフトし始める。「successorが高速に求まれば良いのにね～」等と言っていると、突然risujirohが「そういえばGifted InfantsのライブラリにFastSetってのがあるよ」と言い始める 確認すると、successorがΘ(log_{wordsize}N)で求められることが分かる。
これを使ってシミュレーションする。AC。
解説です pic.twitter.com/qLUrL9jpS9
— beet (@beet_aizu) 2020年9月15日
writer、スマン...
残りがFとHになる。暫くすると、risujirohがHを解けたと言って実装を始める。仕方ないのでFを考え始める。
正直あまり解ける気がしていなかったので、ダラダラしながら適当に考えていると、突然天啓が降ってきて解けた気になる。PCを奪い取って実装するとサンプルが合う。submitするとAC 神～～～～～～～～～～～～～～～～
その後ヤジを飛ばしつつHのライブコーディングを見守る。一度WAが出たものの、デバッグとストレステストを終えて再提出するとAC
全完！ pic.twitter.com/rBIPXg6PsM
— こるとん (@kyort0n) 2020年9月15日
1日目はチーム最低レベルの冷えだったが、2日目は序盤から終盤までほぼ失速せずずっと好調で最高レベルの出来だった。良かった...
問題の感想
B:笑顔
C:Cでこのレベルが出るのか...
D:これ速攻で通されてたけど普通に難しくないか？
E:これ途中考えてたんだけど普通に解けなきゃダメなやつだなぁ 問題は好きです
F:3日通しての瞬間最高風速多分ここだった でも解説pdf読んで問題の解釈にビックリ そんなこと考えてなかった 「スコアの定義が人工的で謎だね」とか言っててスマン
G:あ、実家だ！
H:解法が天才だった こういうの苦手だな つぶあんってすげぇよ...
I:こういうの難しいけど答え見ると「当たり前じゃん」ってなるよね...
J:3問ぶりの帰省
K:＾＾
L:これ想定解の計算量の落とし方はセットで一番好きまである でもコンテスト向きではないよね 難しい...
M:想定解好き K<=1e5にしない方が面白くて良いよね
Day3(ごった煮セット)
脳内でQWE_QWEを走らせたんですけど2時間47分で全完された
— てんぷら (@tempura_cpp) 2020年9月15日
らしいので、2時間47分で全完しようと思いますゥ
Cを読むと秒で解けたので、Aの後に実装する。2位に4分近い差を付けてFA。冴えてる～
Fを読むと、それっぽい未証明エスパーが生える。Cを瞬殺したことで調子に乗っているので、「うーん、出すか！」と言い始める Bが手間取っていたようなので、PCを奪い取って実装して出す。WA。本当にすみませんでした。
risujirohがBで苦戦していたらしく、途中でRubikunにパスしていた。その間にIMを通す。
RubikunがBで頑張っているが、なかなか通らない。この辺で順位表を見て、どうもBの難易度が異常らしいということを察し始める。この間にrisujirohがEをサクッと通していた。
Rubikunもギブアップして、Bが飛んでくる。こういう算数は苦手なので、初手実験をする。結果があまりに非自明でビックリする。誰だよこれBに置いたの。
実装して2WA吐きながら通す。この時点では順位は酷かったが、実装待ちが3問+実験すれば分かるだろが1問という感じだったので、ここから巻き返していきたいね等という話をする。
Bのデバッグ中にちょいちょい実装を進めていたKをrisujirohが通す。
Fで実験をした結果あまりに良い性質が見つかったので、それに基づいて考えると解けて、通す。
実家のGを通す。
risujirohがHの実装を始める。これは流石に大変そう。
解法が出ていない問題がD, J, Lになる。Jを考えると、細部はちゃんと証明出来ていないが計算量が落ちていそうな解法が生える。
HのACを待って実装する。雑にランダムケースを試すと速そうだが、ランダムケースは雑にやっても速そうなので困る。悩んでも仕方が無いので投げると通った。よし！
この間にRubikunがDの解法を生やす。実装はヤバくなりそうだからやってほしいと言われたので、実装を始める。この間にrisujirohとRubikunがLを詰め始める。
実は並列二分探索の実装をするのは初めてだったので色々とバグを踏む。苦労しつつもデバッグして提出する。WAが取れない。1ケース目で落ちているので何かがおかしい。確かめると出力時に0-indexedを1-indexedに直し忘れていた そう... 直すとACする。
この間にLが2人によって完全に詰められている。応援していると通る。
2日連続全完！ pic.twitter.com/m0A7uIOdpN
— こるとん (@kyort0n) 2020年9月16日
2日続けての全完だし、最後の3問が3人で1人ずつ解法を生やした感じになっていたのでとても良かったと思う。
問題の感想
B:つぶあんは凄いと言ったな 撤回します
C:秒で解けて自分すげーって言ってたけどAtCoderで類題解いてたことに後で気付いて悲しくなった
D:ザ・やむなく問題感がある やむなく問題すげー
E:これrisujirohの実装方針で感動してた すごい
F:これ実験せずに解けた人どれくらいいるんだろう...
G:
kort0n「これは実家」
risujiroh「君の実家広そう」
H:risujiroh、ありがとう...
I:最初「頂点iと頂点jの間の辺のコストはgcd(A[i], A[j])と誤読して困ってた これ解けますか？
J:シンプルに難しかった 状態数指数的に増えそうに思っちゃう
K:最近帰省回数が多い
L:ステップ数が多い上に各ステップもそれなりに非自明で、ICPCセットの難問枠感がある
M:最後の帰省
楽しいコンテストでした。運営の皆さん有難うございました。
