F - Takahashi on Grid Editorial
by 
MMNMM
まず、必要に応じて swap を行うことで \(s _ {x,i}\leq t _ {x,i}\) として構いません。
高橋くんは次のアルゴリズムに従って移動することで行動回数を最小にすることができます。
- はじめ、高橋くんがいるマスを \((x,y)=(s _ {x,i},s _ {y,i})\) とする。
- \(x\lt t _ {x,i}\) である限り、次を繰り返す。
- \(y\lt L _ {x+1}\) ならマス \((x,y+1)\) に移動する。
- \(L _ {x+1}\leq y\leq U _ {x+1}\) ならマス \((x+1,y)\) に移動する。
- \(U _ {x+1}\lt y\) ならマス \((x,y-1)\) に移動する。
- \(y\neq t _ {y,i}\) である限り、適切に移動する。
詳細な証明を述べることはしませんが、\(x\) 方向の移動が可能なら先にしてしまって損をしないことをいうことで示すことができます。
このアルゴリズムのもとで、高橋くんが \(x=A-1\) からスタートして \(x=B\) へ移動することを考えます。 \(y\in\mathbb Z\) について、高橋くんがマス \((A-1,y)\) にいる状態から上のアルゴリズムをはじめ、はじめて \(x=B\) となったときのマスを \((B,f _ {\lbrack A,B\rbrack}(y))\) とし、行動した回数を \(g _ {\lbrack A,B\rbrack}(y)\) とします（便宜上、\((A-1,y)\) はすべて空きマスとして扱います）。
このとき、ある \(f=\lbrack f _ L,f _ U\rbrack,g=\lbrack g _ L,g _ U\rbrack,C\) が存在し、
- \(f _ {\lbrack{A,B}\rbrack}(y)=\operatorname{clamp}(y,f _ L,f _ U)\)
- \(g _ {\lbrack{A,B}\rbrack}(y)=C+\max\lbrace0,g _ L-y,y-g _ U\rbrace\)
- \(f _ L\neq f _ U\vee g _ L\neq g _ U\implies f=g\)
を満たします（ここで、\(\operatorname{clamp}(x,a,b)\coloneqq\min\lbrace\max\lbrace x,a\rbrace,b\rbrace\) です）。
証明
区間 \(\lbrack A,B\rbrack\) の幅についての帰納法によって示します。
\(A=B\) のとき、\(f=g=\lbrack L _ B,U _ B\rbrack,C=1\) とすると条件を満たします。
\(A\lt B\) のとき、 \[f _ {\lbrack{A,B}\rbrack}(y)=\operatorname{clamp}(f _ {\lbrack{A,B-1}\rbrack}(y),L _ B,U _ B)\] および \[g _ {\lbrack{A,B}\rbrack}(y)=1+g _ {\lbrack{A,B-1}\rbrack}(y)+\max\lbrace{0,L _ B-f _ {\lbrack{A,B-1}\rbrack}(y),f _ {\lbrack{A,B-1}\rbrack}(y)-U _ B}\rbrace\] が成り立ちます。
帰納法の仮定より、\(f _ {\lbrack{A,B-1}\rbrack},g _ {\lbrack{A,B-1}\rbrack}\) に対して上の条件を満たす区間 \(f,g\) と整数 \(C\) を取ることができます。
\(\operatorname{clamp}\) 関数は合成について閉じているため、\(f _ {\lbrack{A,B}\rbrack}(y)=\operatorname{clamp}(y,\bar f_L,\bar f _ U)\) なる \(\bar f=\lbrack\bar f _ L,\bar f _ U\rbrack\) が存在します。
\(\bar f _ L\neq\bar f _ U\) ならば \(\bar f=f\cap\lbrack L _ B,U _ B\rbrack\) が成り立ち、\(f _ L\neq f _ U\) が必要なので \(f=g\) が成り立ちます。 \(f _ L,f _ U,L _ B,U _ B\) と \(y\) との大小関係を考えることで \(g _ {\lbrack{A,B}\rbrack}(y)=C+1+\max\lbrace0,\bar f _ L-y,y-\bar f _ U\rbrace\) が成り立つことがわかります。
\(\bar f _ L=\bar f _ U\) かつ \(f _ L\neq f _ U\) ならば、\(f\cap\lbrack L _ B,U _ B\rbrack=\emptyset\) です。\(f\) と \(\lbrack L _ B,U _ B\rbrack\) の大小に応じて、\(g _ L,g _ U\) のいずれか一方を \(\bar g\) として \(g _ {\lbrack{A,B}\rbrack}(y)=\bar C+|y-\bar g|\) となります。
\(f _ L=f _ U\) ならば、\(f _ {\lbrack{A,B-1}\rbrack}\) は定数関数です。\(g _ {\lbrack{A,B}\rbrack}\) は \(g _ {\lbrack{A,B-1}\rbrack}\) に定数を足したものとなるので、示されました。
区間 \(\lbrack{A,B}\rbrack\) に対して \(f _ {\lbrack{A,B}\rbrack},g _ {\lbrack{A,B}\rbrack}\) を表す \(f,g,C\) を対応させることを考えます。
隣接する区間に対応する \((f _ 1,g _ 1,C _ 1),(f _ 2,g _ 2,C _ 2)\) が与えられたときにそれらを合併した区間に対応する \((f,g,C)\) を高速に求めることができれば、この問題をセグメント木などを用いて解くことができます。
余談：処理がセグメント木などで扱える条件
隣接する区間の合併に対応する処理がセグメント木で扱えることは、「セグメント木ではモノイドを処理できる」という定式化だけでは説明できません。 ですが、一般に隣接区間の合併に対応する処理はセグメント木などで扱うことができます（このような形式の処理を包括的に扱う議論として、セグメント木に乗る構造の圏による定式化が有名です）。
今回の場合は、処理に関して区間が隣接していることを用いていないので、一般の \((f _ 1,g _ 1,C _ 1),(f _ 2,g _ 2,C _ 2)\) に対しても合併が定義できます。 この処理がモノイドになっているため、これを確かめることで「モノイドが乗る」という定式化のもとでセグメント木などで処理できることを確認できます。
具体的には、\(f _ 1=[f _ {L,1},f _ {U,1}],g _ 1=[g _ {L,1},g _ {U,1}],f _ 2=[f _ {L,2},f _ {U,2}],g _ 2=[g _ {L,2},g _ {U,2}]\) とすると、 \[f=[\operatorname{clamp}(f _ {L,1},f _ {L,2},f _ {U,2}),\operatorname{clamp}(f _ {U,1},f _ {L,2},f _ {U,2})]\] および \[g=[\operatorname{clamp}(g _ {L,2},g _ {L,1},g _ {U,1}),\operatorname{clamp}(g _ {U,2},g _ {L,1},g _ {U,1})]\] と計算することができます。 \(C\) については、\(y=g _ L\) としたときの移動回数が求める \(C\) になります。
よって、区間の合併は \(O(1)\) 時間でできることがわかりました。
列に対して更新がないためより高速なデータ構造を用いることもできますが、セグメント木を用いた \(O(N+Q\log N)\) 時間などで十分高速です。
実装例は以下のようになります。
#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/segtree>
int main() {
using namespace std;
// x の区間 [A, B] に入って出ていくときの動きとコストを表す構造
// 入るときの y 座標の値を入れると (出るときの y 座標, 移動回数) を返す
struct block{
unsigned fL, fU;
unsigned gL, gU;
unsigned long C;
pair<unsigned, unsigned long> operator()(unsigned y) const {
return {clamp(y, fL, fU), C + max(y, gL) - min(y, gU)};
}
};
// セグメント木の定義
// 二項演算は区間の合併
using segment_tree = atcoder::segtree<block, [](const block& lhs, const block& rhs) -> block {
// 区間の合併はがんばる
const auto new_fL{clamp(lhs.fL, rhs.fL, rhs.fU)}, new_fU{clamp(lhs.fU, rhs.fL, rhs.fU)};
const auto new_gL{clamp(rhs.gL, lhs.gL, lhs.gU)}, new_gU{clamp(rhs.gU, lhs.gL, lhs.gU)};
const auto new_C{lhs.C + rhs(lhs(new_gU).first).second};
return {new_fL, new_fU, new_gL, new_gU, new_C};
}, []{
// 単位元は全面素通し
return block{0, 1000000001, 0, 1000000001, 0};
}>;
unsigned N;
cin >> N;
vector<block> intervals(N);
for(auto&& [fL, fU, gL, gU, C] : intervals){
unsigned L, U;
cin >> L >> U;
// [L, U] が空いている列に対応する値を作る
fL = gL = L;
fU = gU = U;
C = 1;
}
segment_tree seg_tree{intervals};
unsigned Q;
cin >> Q;
for(unsigned i{}; i < Q; ++i){
unsigned sx, sy, tx, ty;
cin >> sx >> sy >> tx >> ty;
if (sx > tx){
swap(sx, tx);
swap(sy, ty);
}
// [sx, tx] に sy から入ったときの (出てくる y 座標, 移動回数)
const auto& [out, cost]{seg_tree.prod(sx, tx)(sy)};
// 最後に y 座標を調節して出力
cout << max(out, ty) - min(out, ty) + cost << endl;
}
return 0;
}
posted:
last update: