競プロ備忘録

競プロerの備忘録

AGC58B - Adjacent Chmax

コンテスト中に解法思いついたけど、計算量改善の実装が間に合わず無念の敗退…
結局、コンテスト後に自力ACに成功しました。しかし公式解説見てみると、解法が違う気がする。なので、一応解法残します。
嘘が含まれていたら教えてください。

解法

問題を、有向グラフの経路数を数える問題とみなします。

まず、各indexについてとりうる値を考えると、操作によって左右どちらかから伝播してくるわけですが、これは P_{i}を含む i以降の単調増加列および、 i以前の単調減少列の項です。これがグラフの頂点になります。
次はグラフに辺を張りますが、どこからどこに向かって辺を張ることができるかを考えなくてはなりません。ここで頂点の性質を分けると、

  • 値が変化していない
  • 操作によって、左から値が伝播している
  • 操作によって、右から値が伝播している

といったように分けられます。これを踏まえて、どこからどこに辺を張るか考えます。

  1. P_{i}が操作以前のものと変わっていない場合
    • P_{i+1} が操作以前と変わっていない場合、辺を張れます。これは自明でしょう。
    • P _ {i+1} が左から伝播した値に書き換わっている場合、 P _ {i} と等しければ辺を張れます。なぜなら、 P _ {i} は一度も書き換わっていないため、 P _ {i+1}が左伝播で書き換わっているならば、 P _ {i}と等しい以外ありえないからです。
    • P _ {i+1}が右から伝播した値に書き換わっている場合、辺を張れます。 P _ {i+1}は右伝播で書き換わっているので、 P_{i}とは独立しており、いつでも辺が張れます。
  2. P_{i}が左から伝播した値に書き換わっている場合
    • P_{i+1}が操作以前と変わっていない場合、辺を張れます。伝播がiで止まっているので、当然辺が張れます。
    • P _ {i+1}が左から伝播した値に書き換わっている場合、 P _ {i}以下であれば辺を張れます。なぜなら、左からの伝播であるなら、 P _ {i+1}を書き換える際、同時に P _ {i}も書き換わっており、 P _ {i+1}だけを P _ {i}より大きい値で書き換えることはできないためです。逆に、 P _ {i+1}を一度小さい値で書き換えた後、 P _ {i}を左伝播で書き換えることはできるので、 P _ {i} \geq P _ {i+1}は達成可能です。
    • P _ {i+1}が右から伝播した値に書き換わっている場合、辺を張れます。 P _ {i}と P_{i+1}は独立に操作されているので、いつでも辺が張れます。
  3. P_{i}が右から伝播した値に書き換わっている場合
    • P _ {i+1}が操作以前と変わっていない場合、 P _ {i}と等しければ辺を張れます。なぜなら、 P _ {i+1}が操作以前と変わっていないため、 P _ {i}が右から伝播される値としてありうるのは、 P_{i+1}以外ありえないからです。
    • P _ {i+1}が左から伝播した値に書き換わっている場合、辺を張れません。なぜなら、 P _ {i}は右から伝播された値に書き換わっているため、 P _ {i} \leq P _ {i+1}です。このとき、 P _ {i}の値を P _ {i+1}に伝播させることはできず、このような場合がありえないからです。
    • P _ {i+1}が右から伝播した値に書き換わっている場合、 P _ {i}以上であれば辺を張れます。これは P _ {i}, P _ {i+1}ともに左伝播の場合と同様の議論から導けます。

このように辺を張り、 i = 0の場合にありうる値のみを1で更新したDP配列をグラフに従って更新していけば、解は求まります。

計算量改善

ただし、これを愚直に実装すると以下のような実装となり、最悪計算量は O(N ^ 3)となり、TLEしてしまうはずです。

for (int i = 0; i < n-1; i++) {
    for (/* Piとしてありうる値を走査 */) {
        for (/* Pi+1としてありうる値を走査 */) {
            /* 条件わけを行い、DP配列を更新 */
        }
    }
}

そのため、計算量改善を行う必要がありますが、これは可能です。
具体的には、左右伝播の頂点リストをソートし、尺取法でDP配列の更新を行うことで、計算量を O(N ^ 2 logN)程度(ボトルネックがDP配列の更新ではなく、左右伝播の頂点リストの作成とソートになるため)に落とすことができます。
実装例は以下の通りです。冒頭はただのmodintのライブラリなので、本質コードは100行目くらいからになります。(めっちゃ実装汚いですが許してください…)

Submission #34053270 - AtCoder Grand Contest 058