ACPC2020 1日目
全日程 Ramen as a Service で参加予定です。
内容
通した順です。
A(0:02)
どうせ割り算すると誤差死するんだろうなと思ったので、きちんと手元で立式しました。
普段より時間はかかりましたが、問題ないスピードでACです。
B(0:31)
何も知らないので何もいうことがありません。とまとさんが危なげなく通していました。
D(1:09)
問題は最初に読みましたが、結局僕がCへ行くため、るぎうさん考察→とまとさんが実装の流れに。
詳しい中身をあまり知りませんが、DPとか二分探索とかセグ木とか言っていたような…
C(1:15, 3ペナ)
いい感じの考察をるぎうさんから受け取り自分が実装。
最小全域木をすればよくて、x本の道を敷いた後テレポーターを割り振る部分が嘘になっていたのでペナを生やしまくりました。冷静になると、制限付きテレポーターを使う場合と使わない場合で2回似たことをすればよかったのに気づき、ようやくAC。
G(1:58)
問題を知りません。三分探索ってワードが聞こえました。この問題の位置にしては簡単というのも聞こえた気がしますが何もわかりません(無責任)
E(2:36, 2ペナ)
序盤のDP部分の後数え上げるところは僕がやるのがよさそう、と先に見ていたるぎうさんが指示してくださったので僕がやりましたが、思ったより包除パートの正しい考察に気づくまで時間がかかってしまいギリギリに…
のDPでModIntを使ったらTLEして泣く泣くintに直してようやくAC...
と思っていたのですが、コンテスト後に確認してみると二項係数の割り算で毎回計算量がだけ増えていたせいだったぽいです(↓参照)、たまたまそこも書き換えていたので気づかなかっただけっぽい？
E、TLEして、ずっと前半のDPパートでTLEしてると思って定数倍高速化をしてたんだけど、よく考えるとそこは余裕で、本当の原因は後半で二項係数の計算で逆元を求めるときに毎回log MODつけてることだった
— SSRS/AOJ-ICPC550点埋め (@SSRS_cp) 2020年9月19日
F
Eが終わって駆け付けると考察はとっくに終わっていて、提出後のバグ修正中でした。考察は自分が考えたものと先輩方のものが同じだったのでおそらく大丈夫だろうとは思っていたのですが、クエリごとに辺を書き換える部分で無限にバグっていたっぽいです。
結果
6完23位でした。ペナが生えているのが自分の担当箇所のみなので反省しています…
おしまい
冷えてるか～～～(実際冷えていて結構焦っていました)
Bバグらせて3完の時、順位表見たらgetKOKOROもRamen_as_a_Serviceも3完で、冷えてるか〜〜〜って言ってた(結局抜かされましたが……)
— かっつ (@_KKT89) 2020年9月19日
