2023年08月09日 (水)[AtCoder] 精進１。ABC127-F「Absolute Minima」(黄 diff)。サンプルの１を読めば f(x) を１回２回置き換えたときの答えの求め方がわかる。あとは３回４回のケースが想像できればいい。■提出 #44387658 (AC / 1233 Byte / 858 ms)。f(x) を更新するにあたり b は総和を覚えるだけでいい。a については中央値と中央値からの離れ具合の総和が知りたい。それは a のソート列と累積和があればわかる。おなじみ BIT で効率的に動的に管理する。■■■精進２。ABC130-F「Minimum Bounding Box」(黄 diff)。まず入力を絞る。d={R,L,U,D} それぞれについて X 座標の最大値最小値、Y 座標の最大値最小値にしか用がない。X 座標について考える。X 座標の最大値最小値の差が減るか一定か増えるかが切り替わるかもしれない時刻が４つだけある。右に移動する X 座標の最大値が左に移動する X 座標の最大値と交差するときが１つ。右に移動する X 座標の最大値が上下に移動する点の X 座標の最大値と交差するときが１つ。３つ目と４つ目は同様に左に移動する X 座標の最小値が～。Y 座標も同じく最大４つの時刻で差の増減トレンドが変化する。求めるものは差と差の積の最小値だけど、差の増減トレンドと積との関係はどうなっているだろうか。(差が減る)×(差が減る)=(積が減る)、増×増=増、減×増=？、増×減=？。書いててわからなくなった。差が増減する早さに秒速１と２の２種類ある。１種類なら平方数を最大として上に凸のグラフのある範囲を切り取った変化をすると思ったけど、２種類だとどうなるんだろう。下に凸になることがあると思ったから三分探索をしたけど、今になって三分探索ができる単純な形の変化をするとはわからなくなってしまった。■WA×1 のち AC (1480 Byte / 187 ms)。