かっつのメモ帳

主に競プロ　時々日記

ACPC2020 参加記

コンテスト参加記

Day0

社会情勢、許せねえよ……(政治的発言)


Day1

農工大セット　解説


ICPCチームで出ました。

[0:02] Aを書く、通る。全体7番目で速度は良い感じ。

HyadoがB、hotmanがCを見ていたのでD見るか〜となる。

D座圧してDPやるだけっぽい。

hotmanが辛そうにCを書いていたのでそれを待つことに。


[0:19] C WA

Cを見デバックに回してDを書き始める。Cの実装前に問題文読んだ段階で座圧は書いてたのでBIT用意するぐらいで実装がほぼ終わった。

[0:30] D AC

B若干炎上していたが、Eを読むことに。

E→使うbitの数を決め打って後は包除原理やれば解けそう。

C問題で見つけていたミスっぽい箇所はWAの要因になり得ることが分かったらしくhotmanが書き換えて提出　AC(0:38)


Bが通せてなくて、辛い…><

順位表の他の早稲田チームは、、、同じく冷えてる…><


結局Bの当たり方針が引ける。ちなみに同じようなこと考えてたけど、主張しなかったのは手元で4進数で試して成り立たないな〜とかやってたから(Pが素数って知ってるかな！？？)

Hyado「まだ実装が少しめんどくさい　ううっ」

これぐらい書きなさーい！

[1:16] B AC


E問題結局hotman先生の介護を受けながら包除の式が立ったのでこれで良さそうとなる。

F問題はフローで解けるらしい、E問題の実装で少し詰まってる間にFの実装も始めてもらう。

HyadoとG問題について考えてた。ところどころ筋の通った考察は経由したけど、積極的に詰め切らなかったのは良くなかった(問題の位置的に足りないライブラリ/知識がありそうと思い込んでしまった)。


E問題若干実装に自信が無くてF任せてたけどもっと早い段階でPC奪っても良かったな、この辺難しい。

[2:26] PC奪って書いてEを書く、サンプルが合うので出す→WA

あれ〜って言いながら見デバックする、よくよく見ると負の数も扱ってるのに適切な+mod処理をしてなかった(は？)

[2:33] E AC


後時間的に一問に絞る形だったので、F問題の応援をしていた。

どうやらフローライブラリがバグってるらしい。

が、結局バグが取れずにタイムアップ。

感想戦にて。

dfs回す前にbfs回さないとdinic失敗するやん


感想

5完全体33位　学内ICPCチーム内2位。

とはいえ終了直後にFは通ったので惜しかった。

ただ全体的にタイムロスが多かったので減らしていきたいな〜〜(個人的にはADは良くて、EのACまで時間が結構空いてしまった)。

Gは通すべき問題だったね。


Day2

参加記書きます、書くので(今日は10/9)

会津大セット　解説

冷えた記憶だけが残っていて、その中で2週間前のコンテストのムーブ思い起こすの険しい。


ICPCのチームメンバーで出ました。

Aやるだけだったので書くAC [0:00]

B若干時間かかってたけどHyadoが書いてたAC [0:08]

A終わった後hotman先生とCを読んでいた、問題文が長くて辛い。

B終わったHyadoも合流して3人でCを相談していた気がする。実際、誤読や嘘を主張してるチームメイトにツッコミを入れた記憶があるのでこれは良かったかも。

なんやかんや話してるうちに良さそうな方針が固まるのでHyadoがCを書く、AC[0:28]

C問題の議論中、他の問題開いてE問題DPぽいな〜って思ってて実際簡単なDPで解けるな〜ってなったのでC終わった後書いたAC [0:35]

F問題hotman先生が最初計算量を勘違いしててTLE出してたりしたけど、頑張って1ペナで通してた　凄い[1:03]


ここからかなり辛い時間が…

G問題色々迷走してて、区間に貼るテクが全く出てこなかった。最後hotmanが実装頑張ってたけどダメだったな。

J問題実は愚直が間に合いませんか？とHyadoが主張して色々工夫を考慮していた。

K問題、考えてたけど途中であーこれ知識足りない奴だーってなって調べ物フェーズもあった気がする。


結局椅子を温め続け、5完 32位で終了。

早稲田の2チーム冷えてたんだけど結局ラスト10分で完数でまくられた(〜完〜　完だけに)

感想

かなり自分に足りてない部分だと思うので会津大セット復習真面目にやります。。。


Day3

北海道大学セット　解説


Day3はじゅぴろさん、Mdさんと出ることに。5000兆円欲しい！！


コンテスト開始

早速Aが苦しい問題だったみたいで先にじゅぴろさんがBを書いてAC[0:08]

Aでペナが出たので見デバックしてもらう事に。その間にCの解法が詰まってたので書いた。AC[0:13]

MdさんがAのバグも発見、AC[0:13]


じゅぴろさんがD問題読んでこれはSCCやるだけ典型では？と言いながらパパッと通す　全体の中でもかなり早くて凄かった[0:21]

その間MdさんとEを考えたんですが何も分からず冷えていた。順位表この時Dが解かれてなくてEがかなり通されてて焦った。

その後3人でEを考えてそれっぽい方針が生える　けどよく分からないので書きたくね〜って顔をしていたらじゅぴろが1発で通してた　ありがとう…[0:38]


Eを押し付けてる間にMdさんとFを考察してた。

いざ実装し始めるまでも色々方針で悩んだが、書き始めてからもこの方針のままだと対応出来ないケースがあるなぁ…って感じで詰まり詰まりながらもMdさんと相談しつつなんとか書き上げる。



サンプルも合ったので提出する。



よろしくお願いしまぁぁぁすっ！！！(submit)



f:id:KKT89:20201009020756p:plain
終わった…



デバック開始……




原因、発覚……

f:id:KKT89:20201009021057p:plain

f:id:KKT89:20201009021221p:plain

サンプルはよく確認しよう！！！



その後は3人でGの考察をしていた。

この時点で残り1時間半も時間あったはずなんですが、3人でGの解法がなかなか生やせず反省…

ところどころ惜しい話は出てた気がする(Mdさんが提案してたDPも惜しかった)が後一歩出るのが遅かった。

最後の最後になって解法が生えるもタイムアップ……終了後にMdさんがACしていた。


感想

6完 31位で終了でした。

途中までそこそこ良い感じではあったので7完出来なかったのは悔しい。

とはいえ久々に外部の人とチーム組めて楽しかったです、またオンサイトのあれこれに参加したいな〜


遅ればせながら運営の皆様、合宿運営ありがとうございました！楽しませて頂きました。