HUPC2020参加記

HUPC2020に全日程参加しました。 ICPCチームメイトのsiro53も参加記を書いているので是非ご覧ください。

bakamono1357.hatenablog.com

day1

ICPC出場予定でのチームUHISHIRO(siro53, kiyoshi0205, suta)の3人で参加しました。
最初はレート順に
A : shiro
B : suta
C : きよし
が担当することになりました

Aをshiroがすぐ通す
Bを読んで「区間一次関数加算できません！詰み！w」とか言っていたがよく見ると最終的な値しか問われていないので例のimos2回やるやつだと理解
→少し戸惑いながらもバグることなくAC(良かった)
Cをきよしがギャグじゃんと言いながら書いて出す→MLEが出たがすぐ修正して提出してAC

Cをきよしが書いている間shiroとDの考察をする
suta「N個の点が平行な二直線上に全てないときつそうじゃない？知らんけど」
shiro「あるかも」
suta「きよしに聞けばヨシ！」
Cを通し終わったきよし「あ、はいそうですね」
ということでそうなっているかどうかの判定をO(N)でやりたいねという方向で考察を進める。
がなかなか良い案が出ず、shiroとsutaはEの考察をはじめ、Dはきよしに任せることに

Eの考察は比較的順調に進み、
suta「とりまワーシャルフロイドやってワープできるとこ列挙して新しくグラフ作ればいいか」
shiro「これ作り直したグラフって二部グラフじゃない」
suta「天才か？」

確かここらへんできよしがDの考察を終わらせて実装を始めた　O(N)回見て比較がO(N)回かと思いきや最初の数個みればNG判定ができるらしい　すごい
再びEの考察に戻る
shiro「連結成分の頂点数/2の合計で良さそう」
suta「ウニのときどうするんですか」
shiro「」
suta「連結成分ごとに色塗って少ない方を足しこめば良さそう」
shiro & suta「はい勝ち～もろたで！w」
完全にACを確信してきよしがDを通した後にshiroが実装を始める
ほどなくして実装が終わり、提出
！？！？
実装ミスを隅々まで確認するが、間違っていなさそう
きよし「一応assertつけて二部グラフかどうか確認する？」

WA　それはそう
かなり厳しい気持ちになる。F以降も読んでみるが厳しそう

～30分後～
きよし「これだめじゃんww(WAのケースを見つける)」
shiro & suta「ほんとだ………」
「連結成分の中で色塗って少ない方」は貪欲だという認識が抜けていた　大反省

フローを疑いながら最小カットや最小費用流をきよしが考察し、自分はDPでできないか考えはじめる

色々考察するもなかなか解法にたどりつかない
suta「なんかこれ最大マッチングとか最小点カバーとか最小辺カバーとかそこらへんだったりしない？二部グラフだし」
きよし「最小点カバーじゃん」
二部グラフでは最小点カバー = 最大マッチングを知っていたのが救いだった…
shiroが書き始める。途中でバグったらしくきよしに交代し、ギリギリでAC。

結果

5完28位。1時間あればFを詰め切れた雰囲気もあったので残念。

3時間コンテストでは1問破滅すると大変なことになることがよく分かりました。国内予選では炎上しませんように……
？？？「直感に頼った未証明のgreedyは危険です」

解いた問題の感想

A : 先に掛け算をしましょう
B : imos2回の等差数列加算は某ARCで書いた経験が生きました
C : 不思議な制約　面白いギャグ
D : 鳩ノ巣の考え方全く出てこなかった。きよしがすごい
E : 直k…(以下略)
Fが、解けません…(数え上げやっぱり苦手)

day2

day1と同様UHISHIROで参加しました。
最初の3問もday1と同様に
A : shiro
B : suta
C : きよし
が担当しました

Aをshiroが通した後もBが読解すら完了しておらず焦る　Cもまだ詰められていなさそう
なんとかBの読解が完了し、やりたくねえ～と言いながら書き、1ペナ(PE)してAC
Cが行列累乗で解けるらしく、shiroが爆速で書いてAC

Dをきよしが読んでいて、これなんだろう？貪欲か？いや違うだろ…解けませんという気持ちになる

Gを読むとダブリングっぽいから最初のステップだけなんとかできればいいねという話になる。
XとYを独立に見ることができ、きよしがさらに等差数列として計算できることに気付く
きよしがGの実装を始め、Dが解かれていたのでshiroとsutaでDを詰めにかかる

Dが全く分からないままきよしがGを書き終わり、提出
デバッグ作業に加わってバグを探すが、最初の1ステップもダブリングパートにもバグが見つからず、day1の悲劇を思い出して悲しくなる。

Gが諦め気味になり、再びDの考察へ。すると
きよし「これ多分貪欲でいけるよ」
suta「マジ？？？？」
きよし「去年のPG battleにそっくりなのがある」

さすがに草　よしなに書いて証明 : AC

Mを詰めはじめる
各コマ独立で、K回まで数字が言えてある数を言ったら負けなゲームが複数みたいなことを伝えると、きよしがgrundy数で考察を始める
自分が変なことを言いまくってた気がしたが、きよしが詰められそうなのでJの考察を始める

しばらくするときよしがMを詰め切り、実装を始める
Jは実家DPに近いものだろうという気持ちになりながら考察しているとDPの値は単調増加に、maxの値は単調増加になることに気付いて希望を見出す
shiroにa[i]の値は負になることもあることを指摘されて破綻したと思っていたが、そもそもmaxが負の区間は全部負の時以外取る必要がないことに気付いて勝ちを確信

ほどなくしてMが通ったのでJを書き始める
するとGのデバッグに回っていたshiroときよしが突然笑いだす



1LL<<60は無限回やらかした経験があるだけに気付けなかったのがかなり悔しい…
きよしではなくshiroが発見したらしい。情報共有は大事ですね
G　AC

Jが書き終わるが、添え字関連が難しかったので一発で書けるわけがないという謎の自信(?)があった
が、テストケースをもらってもWAケースが出ない

suta「じゃあ俺が天才だったっということで、、、出していいっすか？？？？w」

初めて仕事ができたような気がした

Jを書いていた時にshiroときよしがIを詰めていて、数学何も分からんと言いながらEを考える　Eも何も分からん
I詰め切れないままコンテストが終了。数弱で協力できずごめんなさい…

結果

7完28位。28に愛されたチーム
ICPC国内予選でもライバルになるであろうgive us、Ramen as a serviceに完数で負けてしまった。

解いた問題の感想

A : 多倍長整数は要りません
B : AOJ-ICPC 100-150点問題
C : 三項間漸化式　これCなんだ
D : 証明 : AC(は？)
G : ぱっと見ダブリングで、最初のステップをどう詰めるか　1e9でも解けるのすごい
J : JはDPのJ　解けてよかった…
M : 頂点ごとにgrundy数が予め定まることに気付けるかどうか。遷移が高々O(NK)なのが面白い

day3

HUPC day3優勝しました pic.twitter.com/UnhvTwahhM

— suta (@suta28407928) 2020年9月16日

実家であるところの「麵屋こころ」です。遊びにきてね

shiro、yamadさんと大学に集まってチームmouko_tanmenで参加しました。
yamadさん㊙情報 : mouko_tanmenが好きではないらしい

最初の3問はまたレート順に
A : shiro
B : suta
C : yamad
が担当

Bを読むが分からない。shiroが間違えてBを読んでいたらしく慌ててAを読んで通す。Bが分からない。
申し訳ない気持ちになりながらyamadさんにCを書いてもらい、無事通る。
順位表をのぞくとBが誰にも解かれていない　マジか…

yamadさんとshiroは他の問題を読み、sutaがBを考える

しばらくしてBの答えはXの差 + Yの差またはそれに1足したものだろうと確信し、Xの差とYの差が両方1以上なら途中で調整できて1足さずに済むだろうとエスパー。
本当か？と思いつつも提出する→WA 29/47
なんとなくあってそうという気持ちになったところで0 0 0 0の答えが1になっていたことに気付いてがっかり
Xの差またはYの差が0の時の場合分けを細かく書いて再提出→WA 34/49
分からなくなり、shiroから愚直解の疑似コードをもらう

少ししてshiroがIの解法をyamadさんに説明し、解かれている数的にも正しそうということになり、yamadさんが書いてAC
Mの解法もyamadさんが分かったようで書く。

yamad「TL4秒でも少し不安ですが、出します」submitを押す
yamad「ありがとうありがとうありがとうありがとうありがとうありがとうありがとうありがとうありがとうありがとう…」
ジャッジにありがとうを言うとTLが緩くなるらしいです。1日n回オンラインジャッジいつもありがとう。


どうして……

何回か提出するもACにならない。するとshiroがmapを使わなくても良いことに気付き、yamadさんが修正してAC。15 * 3¹⁵にlogつけると感謝しても通らないんですね(棒)

Gを読むとDPっぽいので、コストを前計算すれば良さそうという話になり、yamadさんがGを詰め、sutaはBの愚直を書く。
書き終わって試すと、Xの差が0、Yの差が1の時だけ余計な場合分けをしてしまっていたことに気付く。ごめん……　修正してAC
かなり盛り上がった

shiroとsutaでF、yamadさんはEを詰めていたが途中でGの考察に入る。
Fは実は誤読していて(iとi+1の色が同じでも操作ができると勘違いしていた)、N >= 3以上は基本的にできる！wという話になり、提出→速攻でWA

何も分からず1時間くらい辛い時間が経過。辛かった

yamadさんがG書けそうということになり、書いてもらう。その間も二人でFの考察をしているが、やはり解法は浮かばない。解かれすぎでしょ……

気分転換にトイレ行きつつ外をうろついて戻ると、各文字の出現回数が関係ありそうという気持ちになり、shiroに伝える。すると
shiro「これSが全部同じ文字の時以外任意の2点swapできないか？？」
できそう
部屋の雰囲気が明るくなった
Gをyamadさんが通す　テンションが上がる
さらにyamadさんが操作によって各文字の出現数の偶奇が全て反転することに気付く
すると必要条件が浮かびあがってきた
「SとTの各文字において出現回数の偶奇が全て一致または全て違う。並び方は問わない」


一同「必要条件出たし、これは必要十分だろ！証明 : AC！www」


SあるいはTが全て同じ文字な時はコーナーケース(ということにした)として弾き、書くとAC、めちゃくちゃはしゃいでた

その後JとEを読むと、Eの問題文が修正されていたことが発覚
yamadさんが再度Eを詰め、shiroとsutaでJを考察
yamadさんがEを書いて提出したが、通らずコンテスト終了(1行変えたら通ったらしい。無念)

結果

7完24位。give usとRamen as a serviceにギリギリ勝利。UHISHIROでもACPCで勝ちたいですね。
主にBとF担当でかなり苦しい5時間になってしまった。

解いた問題の感想

A : いつもif文で書いていた大文字小文字判定。C++ islowercaseで調べたらどうやらislower関数があるらしい…
B : 難易度順ってなんだっけ
C : コンテスト後に見たら分かりませんでした。既出らしい…(精進不足)
E : 解説みてすげーって言ってた。「時計回りで最初」の実装にかなり苦労した。「凸多角形の面積は符号付き面積の和」はいつかのICPCで見て驚いた記憶がある
F : コンテスタントには天才しかいないらしい
G : コスト計算が尺取りみたいにできるのが面白い。三分探索でもできるらしい。
I : 見るべき辺が高々NlogN本
J : dp[i][l][r]、3乗に収まるとは思わず…
M : 底が3の高速ゼータ変換　初めて見ました

全体感想

どの問題も考えがいのある良い問題ばかりで本当にすごいと思いました。(WUPCでの作問数ぜロ並感)
どうもチーム練でなかなか仕事できなくて悲しくなる時が多いので、精進します。
運営の方々本当にお疲れ様でした。楽しかったです。

そしてACPCへ…