ICPC 系問題 9/6

Longest Increasing Sequence (AOJ 2430)

N(N+1)/2 個の区間を数の和で降順ソートして、ある点から終点までで LIS 分割するときの最大の分割個数で DP。O(N^2 log N)

Hakone (AOJ 2439)

"-" は無視し、上位から順に見る。

dp[位置][D のために空けておいた場所の数][U で使った場所の数]。「U で使った場所の数」は省略してもよい。

Brilliant Stars (AOJ 2291)

明らかに、連結成分ごとに独立して考えてよい。がんばると、各連結成分ごとに、「その成分の点すべてに接続しているような点 P」が必ず 1 つ以上存在することが示せる。この性質は、点を勝手に何個か取り除いても成立する。
ある連結成分がクリークならば、クリークを構成する点を勝手に 1 つ選んでよい。さもなくば、その成分についての解は 2 以上であるから、P は問答無用で取り除いてよい。残ったグラフに対して同じことを繰り返し（ただし、グラフが複数の連結成分に分かれるかもしれない）クリークになるまで繰り返す。

Psychic Accelerator (AOJ 2226)

この問題を解くために、次の問題を解く：

線分上で物体をできるだけ高速に移動させよ。物体には線分に沿って [-a, a] の範囲の加速度を加えることができる。また、線分上のいくつかの点には速度制限があり、その点を通過する際の速度はその制限速度を超えてはならない。

加速度は -a, a のみを用いればよいことはほぼ明らかである。
等加速度運動は、t-v グラフだと直線として簡潔に扱えるが t-v グラフでは位置の速度制限を扱うことができない。x-v グラフでは等加速度運動が曲線になり分かりづらい。そこで、横軸に x、縦軸に運動エネルギー（実際は v^2/2) をとったグラフを考える。
このグラフの上では、加速度 a の等加速度運動は傾き a の曲線で表され便利である。物体の速度のグラフは、できるだけ運動エネルギーの高い位置を通るべきである。
速度制限のない点における速度は、「前の速度制限のせいでこれ以上速くできない」もしくは「これ以上速くすると次の速度制限にひっかかる」のどちらかの要因により制限される。これを別々に考える。前者は、区間での最大の v^2/2 を ax+t で表すとし、t を区間ごとに順次更新すればよい。後者も同様。
この 2 つの制約により、各点での可能な最大の v^2/2 が求まる。あとは 1/v dx を積分してやれば答えが出る。

補題が解けると、元の問題は次のようにして解ける：

• まず、がんばって円弧を補完する
• 円弧上では、加速度の制限から速度の制限が生まれる。また、円弧上では加減速ができない。そのため、円弧は速度制限つきの 1 点につぶす
• 補題を解き、円弧上ではつぶした制限速度点の速度で動く