ARC 097

CD: 反射

E

Nが2000
→数えるのにO(N²)かかる保存量がある？

保存量
→転倒数を拡張？
　→i個目とi+1個目を通る個数？
　→a[i] > a[j]ならj-iを足す？
　　→全部ダメ

最終的な数列が定まると答えは簡単(転倒数)
→最終的な数列はどういう形になるか？
　→ (W1, W2, ..., Wn)と(B1, B2, ..., Bn)をマージした形になる

Nが2000
→ある程度までのゴリ押しは可能
　→最終的な数列を全部探索，をまとめられないか？ 　　→DP？
　　　→キーは3個に見えて2個，遷移が高速なら可能

DP
→遷移を適切にやればO(1)
→AC

F

Nが100,000
→かなり良い性質がある
　→「無駄な行動」をしない操作列という条件をしないと実は考えるべき操作列が少なくて高速に計算できるタイプの問題？

性質？
→全ての白い頂点を訪れる必要がある
　→全ての白い頂点を訪れるために必要な秒数は？
　　→何年か前の国内予選で既出，白い頂点を葉とする部分木にカットして，2*(n-1) - 直径

白い頂点を葉とする部分木にカットする？
→きっちり証明は出来ないけど正しそう

もしかして2*(n-1) - パスの形の行動経路しか考えなくていいのでは？
→反例も出ないしこのぐらい良い性質が無いと解けなそうなので，多分正しい(強気)

2*(n-1) - パスの形の行動経路だとどういうコストになる？
→式変形
→…
→式変形
　→パスのうち白い頂点のmaxを求める問題
　　→典型，木DP

→AC