JOI '09 本選:3- あみだくじ
問題
https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf
解法
ある横の辺を消すということは,その辺を通る2つのパスの中のその辺の高さ以降のパスが逆になることを意味する.ゆえに,任意の横の辺を消したとき,ある2つの縦棒のスコアが逆になる.この「ある2つの縦棒」を全ての横の辺について調べることを考える.これは全ての縦の辺について愚直にシミュレーションし,その過程で通った横の辺にメモをしていく形で求めることが出来る.
全ての辺についてその辺を消したときに J 君の得点がどう変化するかを,得点の変化する差分を計算し求めればよい.O(NH + M).
解答
0-index と 1-index が混在していて実装ミスをしていた.