F - Greedy Takahashi Editorial by penguinman
高橋くんが時刻 \(X_i\) に都市 \(Y_i\) から行動を開始したあと、初めて乗るバスが \(j\) 本目のバスであるとします。そのようなバスが存在しない場合、および \(Z_i \leq S_j\) である場合、明らかに高橋くんは時刻 \(Z_i\) の時点で都市 \(Y_i\) にいます。また、\(S_j \lt Z_i \leq T_j\) を満たす場合、高橋くんは時刻 \(Z_i\) の時点で \(j\) 本目のバスに乗っています。
これ以降は、そのいずれでもない場合について考えます。
さて、以下の条件を満たす正整数 \(k\) を二分探索することを考えましょう。
- 高橋くんが \(j\) 本目のバスから始めて合計 \(k\) 本のバスに乗ったとする。このとき、一番最後に乗ったバスを乗り終わった時刻 \(k'\) は \(Z\) 以下である。
このような \(k\) が求まってさえいれば、高橋くんが時刻 \(Z_i\) の時点でどのバスに乗っているか、あるいはどの都市にいるかは単純な場合分けによって求めることができます。
判定問題を解く際に必要なものは、「一番最後に乗ったバスは（\(M\) 本のバスのうち）何本目のバスであるか」という情報です。この情報は、ダブリングというアルゴリズムを用いることで、前計算 \(O(M \log M)\)、\(1\) つの判定問題につき \(O(\log M)\) で求めることができます。
具体的な求め方は以下の通りです。
まず始めに、前計算として、\(\lceil \log_2 M \rceil = L\) として、\(i=1,2,\ldots,M\) 及び \(j=0,1,2,\ldots,L\) について、以下によって定義づけられる値 \(\text{r}[i][j]\) を求めておく。
- 高橋くんが \(i\) 本目のバスから始めてちょうど \(2^j\) 回乗り換えた、即ち合計で \(2^j+1\) 本のバスに乗ったとき、彼が乗っているバスは（\(M\) 本のバスのうち）\(\text{r}[i][j]\) 本目のバスである。
このような値 \(\text{r}[i][j]\) は、\(1 \leq j\) であるならば \(\text{r}[1][j-1],\text{r}[2][j-1],\ldots,\text{r}[M][j-1]\) の値を利用して求めることができるため、始めに各 \(i\ (1 \leq i \leq M)\) について \(\text{r}[i][0]\) を求めたあと、\(j\) の昇順に値を求めていくことで \(O(ML)=O(M \log M)\) 回の計算で全ての値を求めることができる。
次に、実際に判定問題を解くことを想定する。求めるべき情報が「高橋くんが \(j\) 本目のバスから始めてちょうど \(k\) 本のバスに乗ったとき、彼が最後に乗ったバスは（\(M\) 本のバスのうち）何本目のバスか」というものであるとき、はじめ \(j\) で初期化された変数 \(now\) について、\(i=0,1,2,\ldots,L\) の順に以下を行う。
- \(k-1\) を \(2\) 進数表記した際、\(2^i\) の位の数字が \(1\) であるなら \(now\) を \(\text{r}[now][i]\) で置き換える。
この操作によって得られた最終的な \(now\) が、求めたかった情報である。計算量は \(O(L)=O(\log M)\) となる。
以上により、この問題を解くことができました。計算量は、合計すると \(O(M \log M + Q \log^2 M)\) となります。
実装例 (Python)
N,M,Q = map(int,input().split())
bus = [[] for i in range(N+1)]
A = [0]*M
B = [0]*M
S = [0]*M
T = [0]*M
for i in range(M):
A[i],B[i],S[i],T[i] = map(int,input().split())
bus[A[i]].append([S[i],i])
for i in range(N+1):
bus[i].sort()
import bisect
dp = [[0]*20 for i in range(M)]
for i in range(M):
nex = bisect.bisect_left(bus[B[i]],[T[i],0])
if nex == len(bus[B[i]]):
dp[i][0] = i
else:
dp[i][0] = bus[B[i]][nex][1]
for i in range(1,20):
for j in range(M):
dp[j][i] = dp[dp[j][i-1]][i-1]
for i in range(Q):
X,Y,Z = map(int,input().split())
now = bisect.bisect_left(bus[Y],[X,0])
if now == len(bus[Y]) or Z <= bus[Y][now][0]:
print(Y)
continue
now = bus[Y][now][1]
if Z <= T[now]:
print(*[A[now],B[now]])
continue
left = 0
right = M
while left+1 < right:
mid = (left+right)//2
now2 = now
val = mid
idx = 0
while val:
if val % 2:
now2 = dp[now2][idx]
val //= 2
idx += 1
if T[now2] < Z:
left = mid
else:
right = mid
val = left
idx = 0
while val:
if val % 2:
now = dp[now][idx]
val //= 2
idx += 1
now2 = bisect.bisect_left(bus[B[now]],[T[now],0])
if now2 == len(bus[B[now]]) or Z <= bus[B[now]][now2][0]:
print(B[now])
continue
now = bus[B[now]][now2][1]
print(*[A[now],B[now]])
なお、ダブリング内部で二分探索を行うことで \(O((M+Q) \log M)\) で解くことも可能です。この計算量を要求されることも多々あるため、覚えておいた方がよいでしょう。
実装例 (C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M,Q; cin >> N >> M >> Q;
vector<int> A(M),B(M),S(M),T(M);
vector<vector<pair<int,int>>> bus(N+1);
for(int i=0; i<M; i++){
cin >> A[i] >> B[i] >> S[i] >> T[i];
bus[A[i]].push_back(make_pair(S[i],i));
}
for(auto &p: bus) sort(p.begin(),p.end());
vector<vector<int>> table(20,vector<int>(M));
for(int i=0; i<M; i++){
auto itr = lower_bound(bus[B[i]].begin(),bus[B[i]].end(),make_pair(T[i],-1));
if(itr == bus[B[i]].end()) table[0][i] = i;
else table[0][i] = (*itr).second;
}
for(int i=1; i<20; i++){
for(int j=0; j<M; j++){
table[i][j] = table[i-1][table[i-1][j]];
}
}
while(Q--){
int X,Y,Z; cin >> X >> Y >> Z;
auto itr = lower_bound(bus[Y].begin(),bus[Y].end(),make_pair(X,-1));
if(itr == bus[Y].end()){
cout << Y << endl;
continue;
}
int now = (*itr).second;
if(Z <= S[now]){
cout << Y << endl;
continue;
}
if(Z <= T[now]){
cout << A[now] << " " << B[now] << endl;
continue;
}
for(int i=19; i>=0; i--){
int next = table[i][now];
if(T[next] < Z) now = next;
}
itr = lower_bound(bus[B[now]].begin(),bus[B[now]].end(),make_pair(T[now],-1));
if(itr == bus[B[now]].end()){
cout << B[now] << endl;
continue;
}
int next = (*itr).second;
if(Z <= S[next]){
cout << B[now] << endl;
continue;
}
cout << A[next] << " " << B[next] << endl;
}
}
この他にも、あるバスからその次に乗るバスへ辺を貼ったグラフが根付き木の形になることを利用して問題を解くことも可能です。計算量はこちらも \(O((M+Q) \log M)\) です。
実装例 (C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M,Q; cin >> N >> M >> Q;
vector<int> A(M),B(M),S(M),T(M);
vector<vector<pair<int,int>>> bus(N+1);
for(int i=0; i<M; i++){
cin >> A[i] >> B[i] >> S[i] >> T[i];
bus[A[i]].push_back(make_pair(S[i],i));
}
for(auto &p: bus) sort(p.begin(),p.end());
vector<vector<int>> edge(M);
vector<bool> isroot(M);
for(int i=0; i<M; i++){
auto itr = lower_bound(bus[B[i]].begin(),bus[B[i]].end(),make_pair(T[i],-1));
if(itr == bus[B[i]].end()) isroot[i] = true;
else edge[(*itr).second].push_back(i);
}
vector<int> X(Q),Y(Q),Z(Q);
vector<vector<int>> ans(Q),mem(M);
for(int i=0; i<Q; i++){
cin >> X[i] >> Y[i] >> Z[i];
auto itr = lower_bound(bus[Y[i]].begin(),bus[Y[i]].end(),make_pair(X[i],-1));
if(itr == bus[Y[i]].end() || Z[i] <= (*itr).first) ans[i] = {Y[i]};
else mem[(*itr).second].push_back(i);
}
vector<int> time,city;
function<void(int)> dfs = [&](int now){
time.push_back(T[now]);
time.push_back(S[now]);
city.push_back(B[now]);
city.push_back(A[now]);
for(auto i: mem[now]){
int idx = lower_bound(time.rbegin(),time.rend(),Z[i])-time.rbegin();
if(idx == time.size()) ans[i] = {*city.begin()};
else if(idx%2 == 0) ans[i] = {*(city.rbegin()+idx)};
else ans[i] = {*(city.rbegin()+idx-1),*(city.rbegin()+idx)};
}
for(auto next: edge[now]){
dfs(next);
}
time.pop_back();
time.pop_back();
city.pop_back();
city.pop_back();
};
for(int i=0; i<M; i++){
if(!isroot[i]) continue;
dfs(i);
}
for(auto p: ans){
for(auto q: p) cout << q << " ";
cout << endl;
}
}
posted:
last update: