オムロンプログラミングコンテスト2026 （AtCoder Beginner Contest 479）

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

オムロンプログラミングコンテスト2026 （AtCoder Beginner Contest 479） Eまで。Fがすぐ分からなかったのでG行ったら解けず終了。 C bit全探索 D 左右から累積max、累積minを取っておけば、「左にいって右」などの最小コストが計算可能 E 子孫に足すか、全体に足して子孫に引くか。

— titia (@titia_til) October 11, 2026

F - Narrow Passage

　概ね自力でAC。解法ツイートは見たけど、それはあまり参考にせず解いた。

　結構時間がかかったので、Gに行かずFに集中していれば解けたかは微妙なところ。

　S[i]→T[i]へ線を結んだものを考える。

　基本的には、abs(S[i]-T[i])の和だが、交差している場合をどうするか。

・a→b(a<b)とc→d(c>d)が、逆向きに交わっている場合、答えを+1（交差するときの操作）し、a+1→bとc-1→dの操作と捉える。

・a→b(a<b)とc→d(c<d)が、c<a<b<dのように、抜かしている場合、答えを+1し、a-1→bとc+1→dの操作と捉える。

　のようにすれば良い。

　交差の回数はBITを使えば求めることができる。