A – Draw Polygon Lines
めちゃ大変．90 提出してしまった，過去最高かも．
以下の記述は基本的には $(n,c)=(80000,800)$ を想定しています．
まず $c$ 以下の解と $N-c$ 以上の解を作る必要があります．曲芸飛行を確認した結果，どちらも適当な山登りで簡単にできるだろうと思っていたら，そうでもなかったです．特に入力がランダムとは限らない場合の最小化が全然ダメでした．
- 常に距離最大の行き先を選ぶこと $N-2$ 回が実現できて，これが理論最大値になります．
- 「乱択して鋭角なら採用する」といった貪欲法で，入力がランダムならば $400$ 回程度まで削減可能です．これを初期解とする山登りなどを書いても task2 が全然正の点数にならないです．
- 落とすケースは何だろうと思っていると，よく考えると特殊制約にもある「$x,y$ 単調増加」というような入力の場合に落ちます．例えばランダムな列をソートしたものを $x,y$ とするとこれらはほぼ同一直線上に並びます．「ランダムに可能なところに進むことと繰り返す」と，一方向に進んだあとすぐに端に達してしまい，頻繁に折り返さざるを得なくなります．
- 「点をいままで作った列のランダムな場所に挿入しようとする」というのも上手くいきませんでした．（ただし実行時間がもっと長ければ可能性はあるかも）
- 落とすケースの場合にならって，「いくつかの次の点の候補をサンプリング．鈍角になるかどうかに加えて，現在の点からの距離でタイブレイク（近い点優先）」としました．「いくつか」は最終的に $350$ 個で成功しました．TL も $c$ もかなりぎりぎりだと思います．TL に関していえば，この「初期解」の発見に 1 秒程度かかっていると思います．初期解から 2-opt 近傍で増減させるようなことも試しましたが，最終的には TL の関係上，貪欲一発で $c$ 以下の解を作りました．
- 距離が小さいものを選ぶと上手くいく理由は説明できません．単に，同一直線状に近い場合の対策ができているという以上のことは分からないです．
- 曲がる回数の最大化は，「距離最大の行き先を選ぶ」のでは TL も厳しいので，上の場合の対比として「いくつかの次の点の候補をサンプリング．鋭角になるかどうかに加えて，現在の点からの距離でタイブレイク（遠い点優先）」としました．こちらは候補の点を $10$ 個としただけですが，非常に $N-2$ に近い値を達成できました．
これでとりあえず，$c$ 以下の解と $N-c$ 以上の解を作ることに成功です．あとは間を埋めます．アイデアは $2$-opt 近傍（頂点列に対する操作としては，区間を選んで reverse する）です．ただしまず実行時間の都合上，reverse する列の長さを小さく抑えます．最終的には TL バトルの結果，後述の例外を除き隣接 swap だけになりました（実行時間が本当にきつい）．
間の値を隙間なくすべて作らなければいけないという問題があります．そこで，「小さい初期解・大きい初期解からスコアをちょうど $+1 / -1$ する」を反復できると嬉しいのですが，これは上手くいかかったです．最初に作った貪欲初期解に何らかの特徴がありすぎるせいだと思いますが，初期解から増やす操作が $+2$ しかできないということになりまくります．かといって parity がいい感じの初期解を最初の貪欲を反復して $2$ つ得るのも難しいです．
最終的に次が解法です．
- shapeness が小さい初期解，大きい初期解を貪欲で作る．
- すこし長い区間に対する 2-opt （prefix の場合も試す必要があった）により，それぞれの初期解から parity が逆の初期解を作る．つまり，小さい側の初期解が $2$ つと大きい側の初期解が $2$ つ作れた．
- それぞれの初期解から，隣接スワップで $+2, -2$ していく．おそらく初期解がいい感じの作り方になっているおかげで，$i=2,3,\ldots,N-4$ に対して $1$ 回ずつ試すだけで $[c,N-c]$ を被覆できた．
熱烈定数倍高速化バトルパートがかなり大変でした．出力も多いので，task 4 まで想定した解法が task 2 を通ったとしても，そこからまだバトルがあると思います．
B – Evidence Board
まず組 $(c_A,c_B,w)$ を作ります．これは葉の相手を決める（選べる $c_A$ のうちで最小のものを消費する）ことを貪欲に繰り返せばよいです．
これが復元できたら，あとは各頂点のまわりで指定の順序になるように辺を並べればよいです．これはたとえば辺の順序関係を有向グラフで表して toposort をとればよいです（必ず存在します）．
C – More Gifts
各始点から $t$ 種類以下という条件を保っていくつまでとれるかを計算しておきます．あとは functional graph の重み付き辺があって，重みがいくつになるまで進むというタイプの二分探索をすればよいです．
D – Big Persimmon
$dp[player][L][R]$ を考えます．ただし，「$L$ はちょうど区間の境界」という場合だけに限定します．player は自由（次にどちらをとるか選ぶ），$R$ に居る人はその区間にあるものを回収中です．
これでひとまず $O(nW)$ 状態です．遷移を考えます．
相手 player が現在の区間を回収し終わるまでに自分が選ぶ区間の集合で場合分けをします．
- player は左端区間をひとつ以上完全に回収する場合
- 操作順を入れ替えれば，player は最初に左端区間をひとつ回収するとしてよいです．この場合の遷移は簡単です．
- player は左端区間を全く回収しない場合
- この場合の遷移も簡単です．
- player は右側区間を $1$ つ以上を回収したあと，最後に左端を中途半端に回収している場合
- 最後に選ぶ $2$ つの区間（右端 $X$・左端 $Y$）の順をスワップすることを考えます．右側の区間の方が長いことから，「$X$ を完全回収して $Y$ の半端なところで終わる」が「$Y$ を完全回収して $X$ の半端なところで終わる」に変わります．残る量は同じなのでこれらは等価で，「左端区間をひとつ以上完全に回収する場合」により計算済なので，このパターンは考慮する必要がないことが分かります．
- player は右端区間を全く回収しない．最後に左端を中途半端に回収している．
- 未回収の量が $x$ であるとき，「このプレイヤは右端の右側にある区間（相手 player が回収し終わった区間）の残り $x$ 部分を回収中」という状態に置き換えてしまいます．右側の区間ほど長いため，これで大丈夫です．
あとはこれらを丁寧に実装します．$2$ 人のプレイヤで優先順位の違いもあるため，プレイヤの差も区別して実装する必要があると思います．
