Memo

Twitterに書くには長すぎることを書きます。Opinions are my own.

FHC 2019 R2敗退

旅行先で同行者がみんな寝た状態のところから参加。周りのいびきがうるさい中、遅めの3完(合計4:37:18)で201位でした。通過ラインの200位まで35秒だった。。。

A

わけわからなくないか? と思ってBを読んで実装し始めた (敗因その1)。Bを書いてみて計算量で疑心暗鬼になったところで落ち着いてAを考えると偶奇くらいしかやることがなくて、サンプルで実験すると規則性が見える -> A提出 (0:51 ← おそすぎる)

B

すぐに自明なO(TN(M+N)) (union_findがO(TNM)、経路復元付きナップサックがO(TN2)) が見えたけど、間に合うか不安でもっと高速化できないだろうか? と疑心暗鬼になった。A提出後に経路復元部分を実装して提出 (1:10)。結局のところサンプル実行は10秒くらいで終わったのでよかった。

C

各キューごとに長さkのABABA... と BABAB... を作るためにどれだけAorBを消せばよいか考えてキューごとに足してABABA... とBABAB... のうちコストの小さい方を使う、という考察まではあっさり出てきた。実装を進めていって途中で詰まったけど、いい感じにDPできることに気づいて解決。DP遷移以外のところをいろいろバグらせてサンプルが合うまでに時間がかかった。サンプルが合ったので提出 (2:35) 最初にキューをランレングス圧縮したけど、別にやらなくてもよかったし、圧縮パートでバグらせてしまった(敗因その2)。

D

残り時間が少ないし、疲れたので終了までごろごろしていた。

終了後

結果を見たら201位になってて笑った

合計ペナ方式はつらい

Round 2落ちは悔しかったけど、また午前2時からRound 3をやらなくてよいのと、500位以内でTシャツはもらえるのでまぁOK