NPCA contest #3 & TDPC参加記

NPCA

優勝しました(ドヤ)

• 最初に問題全部見るが全然わからんする
• Dが数え上げなので考えたらN^2くらいのDPが見えるが遅いのでちょっと数学すると解ける
• combinationを足してちょっとやる
• AC
• Bが結構解かれている
• にぶたんっぽい
• 境界条件とかをうまくどうにかして適当に提出
• AC
• Cもとかれている
• AEは解かれてないのでCをやる
• これheavy-light decompositionとsegtreeでごり押せばできるのでは?
• そんなの40分じゃ実装できるわけないだろ(絶望)
• ふと昔のコードでheavy-light decompositionがあったことに気付く
• 貼る
• ちょっと書く
• 提出
• 通る(ライブラリ厨と言われても文句は言えない)
• コンテストが延長される
• しかし解ける問題がないのでおしまい
• 結局2完したところからずっと1位だった

• やったぜ(完全勝利)

TDPC

• 典型だし12問くらいは解きたいなぁ
• Aからあけることにする
• Bで早速動かない
• いろんな問題を転々として適当にやる
• 何問か通す
• MでTSっぽいことして行列累乗するO(n^3*2^n+n^3log H)くらいのが定数倍クッソ軽いのにTLEする
• あとで聞いてみたらそれで通るらしい、なぜだ
• Rが強連結成分分解してDPするだけに見える
• WA
• 変な場合の処理を忘れてたっぽい
• DAGDPは変な場合があるから気をつけなければ
• 自明しか通せないうちにコンテスト終了
• 50位(大絶望)

• 典型力低すぎて死が見える

まとめ

典型じゃない問題は解けるのに典型が解けなさすぎる
典型が解けないのに典型じゃない問題が解けてしまう