問題
個の島からなる諸島があり、これらの島々は
本の橋によって結ばれている。
島には から
までの番号が付けられており、また橋にも
から
までの番号が付けられている。
ここで、
である橋
は島
と島
を結んでおり、橋
は島
と島
を結んでいる。
また、橋を渡る以外の手段で島を行き来する手段は存在しない。
この諸島に対して、島 を順に訪れるツアーが開催されており、このツアーの長さを「行き来する橋の本数」として定義されている。
厳密には、ツアーとは以下の条件をすべて満たす 個の島の列
のことを指す。
- すべての
（ただし、
）に対して、島
と島
が直接橋で結ばれている。
- ある
が存在して、すべての
に対して
が成立する。
この諸島にて、維持費削減のために橋を1本封鎖することになった。 封鎖する橋をうまく選んだときの、ツアーの長さの最小値を求めよ。
入力
まず最初の1行目に、整数 が与えられる。
次の1行に、 個の整数
が順に与えられる。
条件
- 実行時間制限: 2s
- メモリ制限: 1024MB
（ただし、
）
出力
答えとなる最小値を1行で出力すること。
解法
まず、橋を1本も封鎖しなかったときのツアーの長さの最小値について考えます。
そのために、島 から島
へ移るときについて着目します。
（簡単のため、
とします。）
このとき、島 から島
への移り方としては、
- 島
の順に移る
- 島
の順に移る
の2通りが考えられます。
このそれぞれの場合の長さについては、1つ目の方法では となります。
2つ目の方法では、諸島全体で
本の橋があり、1つ目の方法では渡らなかったすべての橋を渡るため、
となります。
従って、このうちの小さい方が、島 から島
へ移る際の長さの最小値ということになります。
これをすべての
（ただし、
）に対して計算することによって得られる値の和が、ツアーの長さの最小値となります。
さて、ここから橋を1本封鎖したときのツアーの長さの最小値について考えます。
そのため、ある橋 を封鎖することについて考えます。
このときに、島 から島
へと移る方法を考えます。
先程の方法のうち1つ目の方法で進む方が最短であり、橋 がその中に含まれている場合では、橋
が封鎖されることにより、2つ目の方法で進むしかなくなります。
このことにより、全体のツアーの長さは元々の場合と比較して、
\begin{align}
(n - ({x}_{k + 1} - {x}_{k})) - ( {x}_{k + 1} - {x}_{k} ) = n - 2({x}_{k + 1} - {x}_{k})
\end{align}
だけ大きくなります。
また、先程の方法のうち2つ目の方法で進む方が最短であり、橋 がその中に含まれている場合では、橋
が封鎖されることにより、1つ目の方法で進むしかなくなります。
このことにより、全体のツアーの長さは元々の場合と比較して、
\begin{align}
({x}_{k + 1} - {x}_{k}) - (n - ({x}_{k + 1} - {x}_{k})) = 2 ({x}_{k + 1} - {x}_{k}) - n
\end{align}
だけ大きくなります。
これらの場合に当てはまらない場合、すなわち、最短で移動する方法の中に橋 が含まれない場合には、橋
が封鎖されたとしても、全体のツアーの長さの最小値には影響を与えません。
これをすべての （ただし、
） に対して計算することで、橋
が封鎖されることによって、ツアーの長さの最小値からどれだけ値が大きくなるのかを導出することができます。
この値を
として定義します。
この をすべての
（ただし、
）に対して導出されたとします。
このときに、
が最小となるような橋
を封鎖すると、ツアー全体の長さも最小となると言えます。
従って、与えられた をもとに、
を導出する方法について考えます。
ここで、島 から島
に移る場合について考えます。
1つ目の方法で進む方が最短となる場合では、橋 を使用することになります。
従って、
であるすべての
に対して、
\begin{align}
\mathrm{cost}_{i} \leftarrow \mathrm{cost}_{i} + (n - 2 ({x}_{k + 1} - {x}_{k}))
\end{align}
として更新されます。
また、2つ目の方法で進む方が最短となる場合では、橋 を使用することになります。
従って、
または
であるすべての
に対して、
\begin{align}
\mathrm{cost}_{i} \leftarrow \mathrm{cost}_{i} + (2({x}_{k + 1} - {x}_{k}) - n)
\end{align}
として更新されます。
これをすべての に対して行うことで、すべての
の値が求まります。
ただし、 を1つずつ更新する方法では、1つの
に対して
程度の計算量がかかってしまいます。
すなわち、最終的な
を得るためには、
程度の計算量がかかってしまい、
であるため、これは実行時間制限に間に合いません。
この計算量を落とすために、「連続する に対して同じ値を加えていく」ということに着目した、imos法 *1 と呼ばれる方法を用います。
（一般的な使い方はリンク先のものをご覧ください。）
この方法では、例えば である
に対して
だけ
に加えて更新するとしたとき、
\begin{align}
\mathrm{cost}_{ {x}_{k} } & \leftarrow \mathrm{cost}_{ {x}_{k} } + c \\
\mathrm{cost}_{ {x}_{k + 1} } & \leftarrow \mathrm{cost}_{ {x}_{k + 1} } - c
\end{align}
としてまずは更新を行います。
そして、すべての更新が終わった際に、
の順に、
\begin{align}
\mathrm{cost}_{i} \leftarrow \mathrm{cost}_{i} + \mathrm{cost}_{i - 1}
\end{align}
として更新を行っていくことにより、最終的に正しい
の値を得られることになります。
この方法では、1回あたりの更新が の計算量であることから、全体で
の計算量で求めることができます。
従って、実行時間制限に間に合うということが言えます。
このようにして求まった のうちの最小値を、橋が封鎖されていない場合の最小値に加えた値を出力することで、この問題を解くことができます。
ソースコード
main() 関数の中に、答えを出力する部分を直接実装しました。
ll n, m, x[int(2e5 + 5)]; ll cost[int(2e5 + 5)]; int main() { // 値の入力 cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> x[i]; } ll ans = 0; // 橋が1本も壊れていない場合の最小値を表す値 ans // i = 1, ..., m - 1 の順にツアーの行程を見ていき、 cost の値を更新していく for (int i = 1; i <= m - 1; i++) { // x[i] < x[i + 1] となるように、値を交換しておく bool swapped = false; // 値を交換したかを表すフラグ swapper if (x[i] > x[i + 1]) { swap(x[i], x[i + 1]); swapped = true; // もし swap した場合は、フラグを true にしておく } ans += min(x[i + 1] - x[i], (x[i] + n) - x[i + 1]); // 理想的な場合の値を更新する ll now = abs((x[i + 1] - x[i]) - (x[i] + n - x[i + 1])); // cost として加える値を表す now if (x[i + 1] - x[i] <= (x[i] + n) - x[i + 1]) { // 1つ目の方法が最短となる場合は、 x[i], ..., x[i + 1] - 1 の cost が追加される cost[x[i]] += now; cost[x[i + 1]] -= now; } else { // 2つ目の方法が最短となる場合は、 1, ..., x[i] - 1, x[i + 1], ..., n の cost が追加される cost[1] += now; cost[x[i]] -= now; cost[x[i + 1]] += now; cost[n + 1] -= now; } // もし値を交換していた場合は、もとに戻しておく if (swapped) { swap(x[i], x[i + 1]); } } // imos法を用いて cost の値を更新する for (int i = 1; i <= n; i++) { cost[i] += cost[i - 1]; } sort(cost + 1, cost + n + 1); // cost を昇順に並び替える cout << ans + cost[1] << endl; // ans に cost の最小値を足した値を出力する return 0; }
