https://www.acmicpc.net/contest/view/1232
韓国でオンサイトも行われたコンテストなんですが、自分のリサーチ不足か分かりませんが解説が一向に上がらないので、自分で軽くわかる範囲ですが書きました。
H 問題がわかっておりません。
他の $7$ つの問題の問題概要と自分の解法を記しておきます。
追記: H 問題の解法を教えていただきましたので、それも記しますが、今は工事中です。
突貫工事しました。
A : Number of Sorted Contiguous Subsequences
長さ $N$ の順列 $A$ が与えられます。
$A$ の部分連続列としてあり得るもののうち、単調増加になっているのは何通りですか。
$N\leq 2\times 10^{5}$
解法
$A_{i}>A_{i+1}$ を満たすところで数列 $A$ を区切ったとき、区切られた数列の長さを $L_{1}, L_{2},\dots L_{K}$ としたとき、 $\sum \dfrac{L_{i}(L_{i} + 1)}{2}$ が答えです。
例えば、 $A=(1,2,5,4,3)$ なら、 $(1,2,5),(4),(3)$ となるので、 $L=(3,1,1)$ より答えは $8$ です。
B : Overload Prevention
コンセントが $K$ 個、ケーブルが $N$ 個、電化製品が ${M}$ 個あります。
$i$ 番目のケーブルは $1$ つの差し込みプラグに対して $A_{i}$ 個の プラグ受けがあります。
電化製品は $1$ つの差し込みプラグがあり、これをプラグ受けに差し込んで使いますが、 $i$ 番目の電化製品は $D_{i}$ 本以下の延長コードを辿ることで電気が流れるプラグ受けにしか差し込むことができません。 コンセントに直接差し込めば、 $D_{i}=0$ の電化製品も使えます。
使える電化製品の数を最大化してください。
$N,M,K,A_{i},D_{i}\leq 2\times 10^{5}$
解法
スコアが $1$ ずつしか増えない場合のスコア最大化問題は二分探索を用いることができます。以下の判定問題が解ければ良いです。
- $X$ 個の電化製品を使える状態にすることができますか。
$D_{i}$ が大きい方から $X$ 個を小さい順に繋ぐことを考えます。
$k$ 番目の電化製品を繋ぐときは、 $A$ を大きい順に、全ての差し込み口が深さ $D_{k}$ 以下の状態を維持できるように、貪欲に差し込みます。そして、深さが $D_{k}$ 以下の空いている差し込み口が存在するならそこに差します。
これを繰り返して、全ての電化製品が差し込めるなら答えは $X$ 以上、そうでないなら $X$ 未満になります。
実装例 C++
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
int main() {
ll N, K, M;
cin >> N >> K >> M;
vector<ll> A(N), D(M);
rep(i, 0, N) cin >> A[i];
sort(all(A));
reverse(all(A));
rep(i, 0, M) cin >> D[i];
sort(all(D));
ll L = 0, R = M + 1;
while(R - L > 1){
ll X = (R + L) / 2;
ll ind = 0;
ll tmp = K;
ll dip = 0;
bool ok = 1;
rep(i, M - X, M){
while(dip != D[i]){
ll n_ind = min(ind + tmp, N);
rep(j, ind, n_ind) tmp += A[j] - 1;
ind = n_ind;
dip++;
}
if(tmp == 0){
ok = 0;
break;
}
else tmp--;
}
if(ok) L = X;
else R = X;
}
cout<< L <<"\n";
}
C : Bon Split
凸 $N$ 多角形が与えられます。
この多角形を面積、周りの長さが共に同じになるように $2$ 分割してください。
$3\leq N\leq 10^{6}$
解法
いくつかの定義をします。
多角形の周りの点 $A$ から $B$ までの距離を、「$A$ から多角形の周りを辺上に辿って $B$ まで行くときの、辿った辺の長さの和」と定義し、$dist(A,B)$ と表します。
$L$ を多角形の周りの長さとします。
多角形の周りの点 $A$ を通る多角形の面積を $2$ 分割する直線であり、多角形と直線の $A$ でない交点を返す関数 を $f(A)$ と表します。
まず、多角形の周りの適当にな点を頂点 $P$ とし、$Q=f(P)$ とします。
もしこれが周りの長さも $2$ 分割できている、つまり、 $2dist(P,Q)=L$ ならこれを出力します。
そうでないとき、 $2dist(P,Q) < L$ と仮定します。すると、 $2dist(P,Q) > L$ が成り立ちます。
実は中間値の定理より $P,Q$ の間に答えが $1$ つ以上存在するので、二分探索をします。
$dist(P,R) +dist(R,Q) = dist(P,Q)$ となる点 $R$ を求めます。
$2dist(R,f(R))<L$ なら $P$ を $R$ に、そうでないなら $Q$ を $R$ に置き換えます。
これを繰り返すことで、$dist(P,Q)$ が無視できる小ささになるので、これを出力します。
肝心の $f(P)$ ですが、これは多角形の三角形分割を考えると $O(N)$ で求めることができます。
実装例 C++
#include <bits/stdc++.h>
using namespace std;
using ld=long double;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
int main() {
int N;cin>>N;
using F=ld;
struct point{
F x;
F y;
};
vector<point> A(N);
rep(i,0,N) cin>>A[i].x>>A[i].y;
rep(i,0,N*2) A.push_back(A[i]);
auto dist=[&](int a) -> F {
F s=A[a].x-A[a+1].x;
F t=A[a].y-A[a+1].y;
return sqrtl(s*s+t*t);
};
vector<F> D(N*3);
rep(i,0,N*3) D[i]=dist(i%N);
auto calc_point=[&](F a) -> point {
int ind=floorl(a);
F b=a-ind;
return {
A[ind].x*(1-b)+A[ind+1].x*b,
A[ind].y*(1-b)+A[ind+1].y*b
};
};
auto calc_area=[&](point a,point b,point c) -> F {
b.x-=a.x,b.y-=a.y;
c.x-=a.x,c.y-=a.y;
return abs(b.x*c.y-b.y*c.x);
};
F sum=0;
rep(i,1,N-1) sum+=calc_area(A[0],A[i],A[i+1]);
sum/=2;
F d_sum=0;
rep(i,0,N) d_sum+=D[i];
rep(i,0,N*2) D.push_back(D[i]);
auto f=[&](F a) -> pair<F,F> {
int ind=floor(a);
point st=calc_point(a);
ld res=0,tmp=0;
ld ds=D[ind]*(ind+1-a);
rep(i,ind+1,ind+N+1){
ld v=calc_area(st,A[i],A[i+1]);
if(tmp+v<=sum) tmp+=v,ds+=D[i];
else{
ld b=(sum-tmp)/v;
res=i+b;
ds+=D[i]*b;
break;
}
}
return {res,d_sum-ds*2};
};
auto out=[&](ld a) -> void {
int ind=floorl(a);
cout<<ind%N+1<<" "<<fixed<<setprecision(20)<<a-ind<<"\n";
};
cout<<"YES\n";
auto tmp=f(0);
if(tmp.second==0){
out(0),out(tmp.first);
return 0;
}
ld L=0,R=tmp.first;
rep(rp,0,100){
ld med=(L+R)/2;
auto tmp2=f(med);
if((tmp.second<0)^(tmp2.second>0)) L=med;
else R=med;
}
tmp=f(L);
out(L),out(tmp.first);
}
D : Gas Station
一本道に $N$ 個のガソリンスタンドがあり、 $i$ 番目のガソリンスタンドは地点 $x_{i}$ にあり、ガソリンを $1$ L あたり、コスト $p_{i}$ を払って最大 $a_{i}$ L 入れることができます。また、 $x$ は $i$ に対して単調増加します。
今車が地点 $x_{1}$ にガソリンが空の状態あります。
この車はガソリンを最大 $F$ L まで貯めることができます。また、地点 $a$ から地点 $b$ に行くまでガソリンを $|a-b|$ L 消費します。
地点 $X(>x_{N})$ にたどり着けるか判定し、たどり着けるなら最小コストを出力してください。
$1\leq N\leq 5\times 10^{5}$
他の値域は $10^{9}$ 以下の正整数
解法
$f(A)$ を $A$ L 貯めるのに必要な最小コストとし、これを更新することを考えます。この形では更新しづらいので、以下のように変数を定義します。
$1\leq i\leq F$ に対して、 $D_{i}$ を今地点 $x_{1}+y$ にいるとして、 $f(y+1) - f(y)$ とします。$D$ の値は初め全て INF です。また $ans$ を $0$ で初期化します。
この $D,ans$ は以下のように変化します。
- $i$ 番目のガソリンスタンドに着いたとき
$D$ に $p_{i}$ を $a_{i}$ 個追加し、ソートした後、小さい方 $F$ 個を残し他を捨てる。
- $k$ 移動したとき
$k>F$ ならそもそも移動ができない。
以下の操作を $k$ 回行う。
$ans$ に $D_{1}$ を加算する。 $i=1,2,\dots F-1$ の順に、 $D_{i}$ を $D_{i+1}$ に置き換える。 $D_{F}$ を INF にする。
$D=(1,2,4,4,INF)$ の状態で、 $(p,a)=(3,2)$ のガソリンスタンドにたどり着いたら、 $D=(1,2,3,3,4,4,INF)\rightarrow (1,2,3,3,4)$ とする。 その後 $3$ 移動すると、$ans$ に $1+2+3=6$ 加算され、$D=(3,4,INF,INF,INF)$ となる。操作例
これを愚直にやっては時間が間に合わないので、 $D$ をラングレス圧縮した状態で持つことで実行時間内に答えを求められます。
$D$ は両端プライオリティーキューつまり、 std::map 等で実装すれば良いです。
自分の実装では入出力高速化しないと TLE してしまいました。
実装例 C++
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll N,X,F;
cin>>N>>X>>F;
vector<ll> D(N),P(N),A(N);
rep(i,0,N) cin>>D[i]>>P[i]>>A[i];
ll ans=0;
ll sum=0;
map<pair<ll,ll>,int> s;//{pri,lit}
auto push=[&](ll p,ll l) -> void {
s[{p,l}]++;
sum+=l;
};
auto pop_front=[&]() -> pair<ll,ll> {
auto tmp=(*s.begin());
s[tmp.first]--;
if(s[tmp.first]==0) s.erase(tmp.first);
sum-=tmp.first.second;
return tmp.first;
};
auto pop_back=[&]() -> pair<ll,ll> {
auto tmp=(*s.rbegin());
s[tmp.first]--;
if(s[tmp.first]==0) s.erase(tmp.first);
sum-=tmp.first.second;
return tmp.first;
};
bool ok=1;
auto proc=[&](ll d) -> void {
if(sum<d){
ok=0;
return;
}
ll use=0;
while(use!=d){
auto tmp=pop_front();
if(use+tmp.second>d){
push(tmp.first,tmp.second-d+use);
tmp.second=d-use;
}
use+=tmp.second;
ans+=tmp.second*tmp.first;
}
return;
};
auto ins=[&](ll p,ll l) -> void {
push(p,l);
if(sum<=F) return;
while(sum>F){
auto tmp=pop_back();
if(sum>F) continue;
else push(tmp.first,F-sum);
}
};
D.push_back(X);
rep(i,0,N){
ins(P[i],A[i]);
proc(D[i+1]-D[i]);
}
cout<<(ok?ans:-1)<<"\n";
}
E : Aris, Clean Up!
$H\times W$ の行列 $A,B$ が与えられます。 これらの要素は $0$ 以上 $3$ 以下の整数です。
$H\times W$ のグリッドがあり、今 $(R,C)$ にお掃除ロボットが上方向を向いています。また、全てのマス目にゴミが落ちています。
$90$ 度回転を $D$ 回した後、以下の操作を繰り返します。
掃除ロボが $(x,y)$ にいるとき、 - もしそのマスにゴミがあるなら、ゴミを回収し、$90\times A_{x,y}$ 度回転する。 - もしゴミがないなら、 $90\times B_{x,y}$ 度回転する。 $1$ マス前に進み、グリッドの外に出たら操作終了。
最後にゴミを回収するのは、何回目の操作のタイミングですか。
$H,W\leq 1024$
解法
愚直にすると TLE しますが、 Union Find Tree と同様の考えの経路圧縮をすることで、 $O(HW)$ になります。
具体的には、$T[x][y][d]$ をゴミがない地点 $(x,y)$ に $90\times d$ 回転した状態で侵入したときの次の行き先とその距離として、ゴミを回収したら、前にゴミを回収してからそれまで通った $T[x][y][d]$ をゴミを回収した地点に更新すれば良いです。
無限ループに関しては、ゴミを回収せずに同じ地点を同じ向きで通ったときなどの適切なタイミングで打ち切ってください。
実装例 C++
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int H,W;
cin>>H>>W;
int s,t,d;
ll ans=0;
cin>>s>>t>>d;
vector A(H,vector<char>(W)),B(H,vector<char>(W));
rep(i,0,H) rep(j,0,W) cin>>A[i][j];
rep(i,0,H) rep(j,0,W) cin>>B[i][j];
vector<int> dx={-1,0,1,0},dy={0,1,0,-1};
vector p(H,vector<bool>(W,1));
vector seen(4,(vector(H,vector<ll>(W,-1))));
struct point{
int x;
int y;
int dir;
};
vector to(4,vector(H,vector<pair<point,ll>>(W,{{-1,-1,-1},-1})));
rep(k,0,4) rep(i,0,H) rep(j,0,W){
int a=k,b=i,c=j;
a=(a+B[i][j])%4;
b+=dx[a];
c+=dy[a];
to[k][i][j]={{b,c,a},1};
}
ll proc=0,sum=0;
vector<point> tmp;
tmp.reserve(H*W*4);
while(true){
if(p[s][t]){
p[s][t]=0;
ans=proc;
for(auto v:tmp){
ll z=to[v.dir][v.x][v.y].second;
to[v.dir][v.x][v.y]={{s,t,d},sum};
sum-=z;
}
assert(sum==0);
tmp.clear();
d+=A[s][t]-'0';
d%=4;
s+=dx[d];
t+=dy[d];
proc++;
}
else{
if(ans==seen[d][s][t]) break;
seen[d][s][t]=ans;
tmp.push_back({s,t,d});
proc+=to[d][s][t].second;
sum+=to[d][s][t].second;
auto pos=to[d][s][t].first;
s=pos.x;
t=pos.y;
d=pos.dir;
}
if(min(s,t)==-1||s==H||t==W) break;
}
cout<<ans+1<<"\n";
}
F : Henesys Forest Trail
$N$ 匹の移動するキノコが長さ $4L$ の道にいます。
$i$ 匹目のキノコは左端から $4P_{i}+1$ の地点いて、左か右かいずれかの向きを向いていることがわかっています。
あるときからキノコたちは一斉に同じ速度で歩き始めます。
キノコは衝突したら、お互い向きを反転させます。
道の端にキノコがたどり着いたらキノコは消滅します。
あなたは歩き始めるタイミング、もしくはキノコが消滅するタイミングで笛を吹くことができます。
笛を吹くと全てのキノコの向きが反転させます。
適切なタイミングで笛を吹くことで、左で消滅するキノコの数を最大化してください。
笛を吹く回数とタイミングを「キノコ $i$ が消滅するタイミング」という形で求めてください。
$N\leq 2\times 10^{5}$
$L\leq 10^{8}$
解法
長さ $N$ の数列 $C$ を以下のように定義します。
Ants と同様にキノコ同士がすれ違うとして考え、笛を吹かないとしたとき、 $i$ 番目に消えるキノコが左で消えるなら $C_{i}=+1$ 右で消えるなら $C_{i}=-1$
変数 $ans$ を $0$ で初期化し、以下の操作を繰り返して $ans$ を最大化する問題に置き換えます。
$C$ の先頭を削除し $ans$ に加算 (キノコが消えるというイベントに対応)
$C$ の全ての要素の正負を反転させ、 $C$ 自体を reverse させる (笛を吹くというイベントに対応)
これは $C$ の累積和が最大になるタイミングで $1$ 回反転させることで $ans$ を最大化できます。
これを実装すればいいです。 反転させるまでに左で消えたキノコの数を $a$ としたとき、左から $a$ 番目のキノコが消えたタイミングで笛を吹けば良いです。
実装例 C++
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
int main() {
int N,L;
cin>>N>>L;
vector<pair<int,int>> p(N);
rep(i,0,N){
int a;
char c;
cin>>a>>c;
if(c=='L') p[i]={a*4+1,i};
else p[i]={(L-a)*4-1,i};
}
sort(all(p));
int tmp=0,mid=0,ind=-1;
rep(i,0,N){
if(p[i].first%4==1) tmp++;
else tmp--;
if(chmax(mid,tmp)) ind=i;
}
cout<<(N-tmp+mid*2)/2<<"\n";
if(ind==-1) cout<<"1\n0\n";
else{
cout<<"1\n";
ind=(ind+mid)/2;
rep(i,0,N){
if(p[i].first%4==3) p[i].first=4*L-p[i].first;
}
sort(all(p));
cout<<p[ind].second+1<<"\n";
}
}
G : Set Expression Transpile
高々 $20$ 種類の bool 変数と括弧と AND, OR, NOT 演算子で表される式が与えられます。
この式から NOT を取り除き、 AND, OR, SUBSTRACT 演算子で表される式に可能なら置き換えてください。
ただし、長さは元の $2$ 倍以下に抑えてください。
例えば
~A&B
を
B\A
に置き換える
与えられる式の長さは $2024$ 以下
解法
真面目な解法しか思いつきませんでした。
1,3 に関しては「構文解析 競プロ」などで調べればわかると思います。
2 は以下の規則に基づいて置き換えていけば良いです。
これは NOT を上に押し上げているというイメージです。
何かしらの関数を定義すればこれが $O(|S|^{2})$ で既約な形になることが証明できると思います。
既約な形にしたとき、構文木の根が NOT であれば、答えは NO です。
これをコードに書き起こせば AC をすることができます。
長さについての保証や、計算量は分かりません。
また、以下の実装例は c++ のポインタを使って実装しています。
構文解析のときに Node を格納する数列に push_back をしていますが、初めに reserve をしないとアドレス再確保によるバグが生じることに注意してください。
実装例 C++ 長い
#include <bits/stdc++.h>
using namespace std;
bool eng(char c){
return 'A' <= c && c <= 'Z';
}
struct Node{
int id;
char symbol;
int alive;
Node* pare;
array<Node*, 2> child;
};
void unite_Node(Node* p,Node* c0,Node* c1){
p->child[0] = c0;
p->child[1] = c1;
c0->pare = p;
if(c1 != nullptr){
c1->pare = p;
}
return;
}
vector<char> order={'~', '&', '\\', '|'};
int prece(char c){
if(c == '~') return 4;
if(c == '&') return 3;
if(c == '\\') return 2;
if(c == '|') return 1;
return 10;
}
bool reduce_not_sub(Node* a){
if(a == nullptr) return false;
if(a->alive == 0) return false;
if(eng(a->symbol)) return false;
int ind = 2;
for(int i = 0; i < 2; i++){
if(a->child[i] != nullptr && a->child[i]->symbol == '~'){
ind = i;
}
}
if(ind == 2) return false;
if(a->symbol == '~'){
if(ind != 0) return false;
if(a->pare == nullptr){
a->child[0]->child[0]->pare = nullptr;
}
else{
for(int i = 0; i < 2; i++){
if(a->pare->child[i] == a){
a->pare->child[i] = a->child[0]->child[0];
a->child[0]->child[0]->pare = a->pare;
break;
}
}
}
a->alive = 0;
a->child[0]->alive = 0;
}
else if(a->symbol == '&'){
a->child[ind]->alive = 0;
a->child[ind] = a->child[ind]->child[0];
a->child[ind]->pare = a;
if(ind == 0) swap(a->child[0], a->child[1]);
a->symbol = '\\';
}
else if(a->symbol == '|'){
auto b = a->child[ind];
a->child[ind] = a->child[ind]->child[0];
a->child[ind]->pare = a;
if(ind == 1) swap(a->child[0], a->child[1]);
a->symbol = '\\';
b->child[0] = a;
if(a->pare != nullptr){
for(int i = 0; i < 2; i++){
if(a->pare->child[i] == a){
a->pare->child[i] = b;
break;
}
}
}
b->pare = a->pare;
a->pare = b;
}
else if(a->symbol == '\\'){
auto b = a->child[ind];
a->child[ind] = a->child[ind]->child[0];
a->child[ind]->pare = a;
if(ind == 1){
a->symbol = '&';
b->alive = 0;
}
else{
a->symbol = '|';
b->child[0] = a;
b->pare = a->pare;
a->pare = b;
if(b->pare != nullptr){
for(int i = 0; i < 2; i++){
if(b->pare->child[i] == a){
b->pare->child[i] = b;
break;
}
}
}
}
}
else return false;
return true;
}
string node_to_str(Node* root){
if(root == nullptr){
return "";
}
string res = "";
if(eng(root->symbol)){
res += root->symbol;
return res;
}
if(root->symbol == '~'){
res = node_to_str(root->child[0]);
if(prece(root->child[0]->symbol) < prece('~')) res = "(" + res + ")";
res = "~" + res;
return res;
}
array<string, 2> tmp;
for(int i = 0; i < 2; i++){
assert(root->child[i] != nullptr);
tmp[i] = node_to_str(root->child[i]);
if(prece(root->child[i]->symbol) < prece(root->symbol) || (root->symbol == '\\' && root->child[i]->symbol == '\\')){
tmp[i] = '(' + tmp[i] + ')';
}
}
return tmp[0] + root->symbol + tmp[1];
}
struct Tree{
Node* root;
vector<Node> nodes;
int len;
int new_node(char c){
Node tmp;
tmp.alive = 1;
tmp.symbol = c;
tmp.id = len;
tmp.pare = nullptr;
tmp.child[0] = nullptr;
tmp.child[1] = nullptr;
nodes.push_back(tmp);
len++;
return len - 1;
}
int parce(string& st,int ind){
stack<int> p;
while(ind != int(st.size())){
if(st[ind] == '('){
ind = parce(st, ind + 1);
p.push(root->id);
}
else if(st[ind] == ')'){
break;
}
else{
p.push(new_node(st[ind]));
}
ind++;
}
for(auto c:order){
stack<int> st;
while(!p.empty()){
int tmp = p.top();
p.pop();
if(nodes[tmp].symbol == c && nodes[tmp].child[0] == nullptr){
if(c == '~'){
unite_Node(&nodes[tmp], &nodes[st.top()], nullptr);
st.pop();
}
else{
unite_Node(&nodes[tmp], &nodes[p.top()], &nodes[st.top()]);
st.pop();
p.pop();
}
}
st.push(tmp);
}
while(!st.empty()){
p.push(st.top());
st.pop();
}
}
assert(int(p.size()) == 1);
root = &nodes[p.top()];
return ind;
}
Tree(string S){
len = 0;
nodes.reserve(S.size());
assert(parce(S, 0) == int(S.size()));
};
void translate(){
bool ok = 0;
while(!ok){
ok = 1;
for(auto &e:nodes){
if(reduce_not_sub(&e)) ok = 0;
}
}
root = nullptr;
for(auto &e:nodes){
if(e.alive && e.pare == nullptr) root = &e;
}
assert(root != nullptr);
return;
}
};
int main() {
string S;
cin >> S;
Tree T(S);
T.translate();
if(T.root->symbol == '~'){
cout << "NO\n";
}
else{
cout << "YES\n";
cout << node_to_str(T.root) << "\n";
}
}
H : Tree Explorer
$N$ 個のフォルダが木構造みたいにあります。
toggle という操作は今いる場所のフォルダの開閉を切り替える操作です。
move k は 下に k マス進む操作です。(マイナスもあります)
今、根に対応するフォルダ $1$ の中にいる状態で、他のフォルダは閉じている状態です。
toggle, move のクエリが $Q$ 回与えられるので、 move のクエリを処理するたびに、今いるフォルダの番号を出力してください。
$N\leq 2\times 10^{5}$
$Q\leq 2\times 10^{5}$
解法
まず、全てのフォルダが開いているときのフォルダの順に並び替えます。
これらのフォルダ $i$ について、自分の祖先のうち閉じているフォルダの数 $f(i)$ を持っておきます。
toggle の操作はある区間について +1 もしくは -1 するという操作で、move はある区間について、$f(i)=0$ である $i$ の数を数えることに対応しているので、これができるデータ構造があれば良いです。
これは例えば遅延セグメントツリーで可能です。
ある区間に対して持つ構造体はその区間での $f(i)$ の最小値と、その最小値を達成する $i$ の数です。
実装例 C++
#include <bits/stdc++.h>
using namespace std;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
#include <atcoder/all>
using namespace atcoder;
struct lazy_S {
int val;
int cou;
};
using lazy_F = int;
lazy_S lazy_op(lazy_S l, lazy_S r) {
if(l.val > r.val) swap(l, r);
if(l.val == r.val) l.cou += r.cou;
return l;
}
lazy_S lazy_e() { return lazy_S{INF, 0}; }
lazy_S mapping(lazy_F l, lazy_S r) {
r.val += l;
return r;
}
//l(r(x))
lazy_F composition(lazy_F l, lazy_F r) {
return l + r;
}
lazy_F lazy_id(){return 0;}
#define lazy_calc lazy_S,lazy_op,lazy_e,lazy_F,mapping,composition,lazy_id
int target;
bool f(lazy_S v){
return v.val != 0 || v.cou < target;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
vector<vector<int>> G(N);
rep(i, 0, N){
int S;
cin >> S;
G[i].resize(S);
for(auto &x:G[i]){
cin >> x;
x--;
}
}
vector<int> L(N), R(N), inv(N), fold(N, 1);
int ind = 0;
lazy_segtree<lazy_calc> seg(N);
auto dfs = [&](auto self, int var, int d) -> void {
L[var] = ind;
inv[ind] = var;
seg.set(ind, {d, 1});
ind++;
for(auto x:G[var]){
self(self, x, d + 1);
}
R[var] = ind;
};
dfs(dfs, 0, -1);
seg.set(0, lazy_e());
ind = G[0][0];
while(Q--){
string op;
cin >> op;
if(op == "toggle"){
seg.apply(L[ind] + 1, R[ind],1 - 2 * fold[ind]);
fold[ind] ^= 1;
}
else{
int k;
cin >> k;
int a = seg.prod(0, L[ind] + 1).cou;
int b = seg.all_prod().cou;
target = max(0, min(a + k, b));
ind = inv[seg.max_right<f>(0)];
cout << ind + 1 <<"\n";
}
}
}
終わりに
自分はこのコンテストで A-E の $5$ 完でした。 H を先に見てしまって F はあと $5$ 分あれば AC できたと思います。
