問題のネタバレが含まれています。
## Day1
面白い話ができない(?)し、これを見る人の大半は競技のことが知りたいと思うのでしません。
## Day2前日 本選模擬
最初の2問だけ解いて考察していたら寝てました。
## Day2 競技前
[庭園2](https://atcoder.jp/contests/joi2024yo2/tasks/joi2024_yo2_d)を解きました。Sparse Tableと二分探索で殴ったけど想定解が天才。
ちなみにJOI埋めの進度はこうなりました。絶対自力で解く人間にしては頑張ったほうだと思ってます。
ちなみに去年の本選のときのです。274点/ボーダー279点で落ちました。
## 競技中
Aを見ると、かなり難しそうな見た目をしていますが寄与を考えると二分探索で簡単に求められることが分かるので、$(1,1)$が$(1,1)$以外のマスに影響しないことに注意しながら実装すると、満点が返ってきます(0:09:25)。
前回はAで盛大に誤読したので早めにACできて安心しました。しかし、Bを実装し提出すると(0:27:24)、0点が返ってきます。焦りながら追加で3投し、何かが間違っていることに気付きます。
開始から1時間15分ほどたったあたりで「$(j-1,j-2,...,2,1)$を倒す」ではなく「$(1,2,...,j-1)$を倒す」であることに気付き、合計7投目でようやく満点を取りました(1:42:48)。
前回はCよりDの方が部分点が個人的に回収しやすかった(Cで24点、Dで50点取れた)のもあり、交互に考察します。このときに理解が微妙だったのとDiscordでチューターの方が気になったらためらわずに質問した方が良いみたいなことを言っていた(?)のを思いだしたのでClarを投げました。
この後にアナウンスもありました。
Dは[この辺](https://miscalc.hatenablog.com/entry/2022/11/11/213943)を読んで考察してました。
Dの方が簡単なのかと思いきやちゃんと考えるとCは$1→i$のパスごとに最適化する必要はなく、辺を逆にして頂点ごとにX以上の最小の辺を使うようにするだけでX以上の辺のみで全頂点に到達するために必要な会社の最大値の最小値が求まるので、座標圧縮して尺取り法でこれを前計算することにより、クエリごとに3パターンの絶対値の外し方ごとにセグ木や二分探索を使うことで計算できることが分かります。
$r' \leq r$のケースと$l < l'$のケースは二分探索で、$r < r'$かつ$l' \leq l$のケースはセグ木で実装しました。
提出すると(3:08:27)、0点が返ってきます。早めに通ったサンプルは実行していなかったのでやるとサンプル1で落ちていて、最終的にいくら必要になったのか出力させると見るからに異常な値が出てきます。
原因を探したところ明らかにヤバい実装ミスをしていたので、
修正して提出します(3:11:04)。満点が返ってきます。
これで300点となりましたが、安心できません。どう考えてもCは難易度9の最易級(8も有り得る)なのでボーダーは300点を超えると予想しました。
Dは小課題4までの46点分は$\mathrm{O}(N \cdot 2^L)$とかで解けそうなので考えるとbitDPの$\mathrm{O}(N L \cdot 2^L)$解を思いついたので書いて投げると(3:19:06)、ちゃんと46点が返ってきてくれます(Lはもう少し考察すると前計算で消せて、あとbool値で管理できるらしい こんな謎コードで通してごめんなさい...)。これ以降は計算量に$N \cdot 2^L$が入っていると絶対無理なので一旦Eに行きます。
EはFunctional Graphの気持ちになると送る先は常に1つしかないのでこれを繰り返していくことを考えると送り先までの距離が一番遠いものを送ればよさそうということが分かります。
ただもうそんなに時間がないので万が一のことを考えて先に小課題1のみの実装をします。3点が返ってきます(3:37:48)。
そして12点解法を実装します。0点が返ってきます(3:49:19)。
サンプルをちゃんと実行するとサンプル6で落ちていることが分かり、一度の時間に同じ荷物を2回送らないための実装が$i<A[i]$の時に正しく動作してないのを修正して提出、12点が返ってきます(3:53:17)。
残りの7分くらいでDとEの他の小課題の考察をしていましたが、特に何もなく終わりました。
## 競技終了後
結果は100-100-100-46-12で合計358点となりました。
予想通りCの難易度は9となりそうで、高3含めて33人が通していました。あとDは言われてみれば分かるタイプでした。こういうのどうやったら思いつけるんだろう。
また、競技結果の公表に時間がかかるということでAランク仮ボーダーが算出されました。何も問題がなければボーダーはこの点数になるということで、この点を超えたのでJOI春合宿への進出がほぼ確定しました。
## 感想
二年連続で最初の方の問題で誤読するとは思ってなかったです。今後参加する方はWAが出たら問題文を読み直してください...
BやCとWAの解決方法が分からない、解法が分からないときはとても辛かったです。また今回も春行けないのかと思いましたが、なんとかなってよかったです。
## 提出コード一覧
### A 0:09:25 100/100
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n; cin >> n; vector<int> A(n),B(n),Z;
for (int& a:A) (cin >> a),Z.emplace_back(a);
for (int& a:B) (cin >> a),Z.emplace_back(a);
sort(Z.begin(),Z.end()),Z.erase(unique(Z.begin(),Z.end()),Z.end()); int m = Z.size();
for (int& a:A) a = lower_bound(Z.begin(),Z.end(),a)-Z.begin();
for (int& a:B) a = lower_bound(Z.begin(),Z.end(),a)-Z.begin();
vector<int> C(m); C[A[0]] = 1; for (int i(1);i < n;++i) ++C[A[i]],++C[B[i]];
for (int i(2);i < n;++i) A[i] = max(A[i],A[i-1]),B[i] = max(B[i],B[i-1]);
for (int i(1);i < n;++i){
auto it = lower_bound(B.begin()+1,B.end(),A[i]);
C[A[i]] += it-B.begin()-1;
}
for (int i(1);i < n;++i){
auto it = upper_bound(A.begin()+1,A.end(),B[i]);
C[B[i]] += it-A.begin()-1;
}
int r = 0;
for (int i(0);i < m;++i) if (C[r]<=C[i]) r = i;
cout << Z[r] << ' ' << C[r] << endl;
}
```
### B 0:27:24 0/100
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n; cin >> n; vector<int> A(n),B(n),C(n+1),D(n+1),E(n+1);
for (int& a:A) cin >> a;
for (int& a:B) cin >> a;
for (int i(0);i < n;++i) C[i+1] = max(C[i]-B[i],A[i]),E[i+1] = E[i]+B[i];
for (int i(n-1);i > -1;--i) D[i] = max(D[i+1]-B[i],A[i]);
vector<tuple<int,int,int>> F;
for (int i(0);i <= n;++i) F.emplace_back(C[i],i,0),F.emplace_back(D[i],i,1);
int l = 1e9,r = -1;
while(abs(r-l)>1){
int x = (l+r)/2,mid = (l+r)/2;
int ll = 0,rr = n;
for (auto [a,b,c]:F) if (a<=x&&ll<rr){
if (c==0) x += E[b]-E[ll],ll = b+1;
else x += E[rr]-E[b],rr = b-1;
}
if (ll>=rr) l = mid;
else r = mid;
}
cout << l << endl;
}
```
### B 0:29:06 0/100
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n; cin >> n; vector<int> A(n),B(n),C(n+1),D(n+1),E(n+1);
for (int& a:A) cin >> a;
for (int& a:B) cin >> a;
for (int i(0);i < n;++i) C[i+1] = max(C[i]-B[i],A[i]),E[i+1] = E[i]+B[i];
for (int i(n-1);i > -1;--i) D[i] = max(D[i+1]-B[i],A[i]);
vector<tuple<int,int,int>> F;
for (int i(0);i <= n;++i) F.emplace_back(C[i],i,0),F.emplace_back(D[i],i,1);
int l = 1e9,r = -1;
while(abs(r-l)>1){
int x = (l+r)/2,mid = (l+r)/2;
int ll = 0,rr = n;
for (auto [a,b,c]:F) if (a<=x&&ll<rr){
if (c==0) x += E[b]-E[ll],ll = b;
else x += E[rr]-E[b],rr = b-1;
}
if (ll>=rr) l = mid;
else r = mid;
}
cout << l << endl;
}
```
### B 0:44:50 0/100
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n; cin >> n; vector<int> A(n),B(n),C(n+1),D(n+1),E(n+1);
for (int& a:A) cin >> a;
for (int& a:B) cin >> a;
for (int i(0);i < n;++i) C[i+1] = max(C[i]-B[i],A[i]),E[i+1] = E[i]+B[i];
for (int i(n-1);i > -1;--i) D[i] = max(D[i+1]-B[i],A[i]);
vector<tuple<int,int,int>> F;
for (int i(0);i <= n;++i) F.emplace_back(C[i],i,0),F.emplace_back(D[i],i,1);
int l = 1e9,r = -1; sort(F.begin(),F.end());
while(abs(r-l)>1){
int x = (l+r)/2,mid = (l+r)/2;
int ll = 0,rr = n;
for (auto [a,b,c]:F) if (a<=x&&ll<rr){
if (b<ll||b>rr) continue;
if (c==0) x += E[b]-E[ll],ll = b;
else x += E[rr]-E[b],rr = b;
}
if (ll>=rr) l = mid;
else r = mid;
}
cout << l << endl;
}
```
### B 0:51:59 0/100
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n; cin >> n; vector<int> A(n),B(n),C(n+1),D(n+1),E(n+1);
for (int& a:A) cin >> a;
for (int& a:B) cin >> a;
for (int i(0);i < n;++i) C[i+1] = max(C[i]-B[i],A[i]),E[i+1] = E[i]+B[i];
for (int i(n-1);i > -1;--i) D[i] = max(D[i+1]-B[i],A[i]);
vector<tuple<int,int,int>> F;
for (int i(0);i <= n;++i) F.emplace_back(C[i],i,0),F.emplace_back(D[i],i,1);
int l = 1e9,r = -1; sort(F.begin(),F.end());
while(abs(r-l)>1){
int x = (l+r)/2,mid = (l+r)/2;
int ll = 0,rr = n;
for (auto [a,b,c]:F) if (a<=x&&ll<rr){
if (b<ll||b>rr) continue;
if (c==0) x += E[b]-E[ll],ll = b;
else x += E[rr]-E[b],rr = b;
}
if (ll>=rr) l = mid,assert(x==E.back()+mid);
else r = mid;
}
cout << l << endl;
}
```
### B 1:30:03 0/100
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n; cin >> n; vector<int> A(n),B(n),C(n+1),D(n+1),E(n+1);
for (int& a:A) cin >> a;
for (int& a:B) cin >> a;
for (int i(0);i < n;++i) E[i+1] = E[i]+B[i],C[i+1] = max(A[i]-C[i]-E[i],C[i]);
for (int i(n-1);i > -1;--i) D[i] = max(D[i+1]-B[i],A[i]);
int r = 1e18;
for (int i(0);i <= n;++i) r = min(r,max(C[i]-D[i]-(E[n]-E[i]),0ll)+D[i]);
cout << r << endl;
}
```
### B 1:40:17 0/100
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n; cin >> n; vector<int> A(n),B(n),C(n+1),D(n+1),E(n+1);
for (int& a:A) cin >> a;
for (int& a:B) cin >> a;
for (int i(0);i < n;++i) E[i+1] = E[i]+B[i],C[i+1] = max(A[i]-E[i],C[i]);
for (int i(n-1);i > -1;--i) D[i] = max(D[i+1]-B[i],A[i]);
int r = 1e18;
for (int i(0);i <= n;++i) r = min(r,max(C[i]-D[i],0ll)+D[i]);
cout << r << endl;
}
```
### B 1:42:48 100/100
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n; cin >> n; vector<int> A(n),B(n),C(n+1),D(n+1),E(n+1);
for (int& a:A) cin >> a;
for (int& a:B) cin >> a;
for (int i(0);i < n;++i) E[i+1] = E[i]+B[i],C[i+1] = max(A[i]-E[i],C[i]);
for (int i(n-1);i > -1;--i) D[i] = max(D[i+1]-B[i],A[i]);
int r = 1e18;
for (int i(0);i <= n;++i) r = min(r,max(C[i]-D[i]-(E[n]-E[i]),0ll)+D[i]);
cout << r << endl;
}
```
### C 3:08:27 0/100
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,m,q; cin >> n >> m >> q; vector<int> Z;
vector<vector<pair<int,int>>> G(n); for (int i(0),a,b,c;i < m;++i){
cin >>a >> b >> c; --a,--b; G[b].emplace_back(c,a),Z.emplace_back(c);
}
sort(Z.begin(),Z.end()),Z.erase(unique(Z.begin(),Z.end()),Z.end()); int s = Z.size(); vector<int> R(s,1e15);
multiset<pair<int,int>> M;
for (int i(0);auto& A:G){
for (auto& [a,b]:A) a = lower_bound(Z.begin(),Z.end(),a)-Z.begin();
sort(A.begin(),A.end(),greater<pair<int,int>>());
if (!A.empty()) M.emplace(A.back().first,i);
++i;
}
for (int i(0);i < s;++i) if (M.size()==n-1){
R[i] = Z[M.rbegin()->first];
while(!M.empty()&&M.begin()->first==i){
auto [a,b] = *M.begin(); M.erase(M.begin());
G[b].pop_back(); if (!G[b].empty()) M.emplace(G[b].back().first,b);
}
}
vector<int> segtree(2*s);
for (int i(0);i < s;++i) segtree[s+i] = R[i]-Z[i];
for (int i(s-1);i;--i) segtree[i] = min(segtree[i<<1],segtree[i<<1|1]);
cin >> q;
while(q--){
int l,r,low,res(1e15); cin >> l >> r >> low;
if (R[0]<=r) res = min(res,max(l-Z[upper_bound(R.begin(),R.end(),r)-R.begin()-1],0ll));
int ll = upper_bound(R.begin(),R.end(),r)-R.begin(),rr = upper_bound(Z.begin(),Z.end(),l)-Z.begin();
for (ll += s,rr += s;ll < rr;ll>>=1,rr>>=1){
if (ll&1) res = min(res,segtree[ll++]+l-r);
if (rr&1) res = min(res,segtree[--rr]+l-r);
}
if (Z.back()>l) res = min(res,abs(r-R[upper_bound(Z.begin(),Z.end(),l)-R.begin()]));
cout << (res<=low?"Yes":"No") << endl;
}
}
```
### C 3:11:04 100/100
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,m,q; cin >> n >> m >> q; vector<int> Z;
vector<vector<pair<int,int>>> G(n); for (int i(0),a,b,c;i < m;++i){
cin >>a >> b >> c; --a,--b; G[b].emplace_back(c,a),Z.emplace_back(c);
}
sort(Z.begin(),Z.end()),Z.erase(unique(Z.begin(),Z.end()),Z.end()); int s = Z.size(); vector<int> R(s,1e15);
multiset<pair<int,int>> M;
for (int i(0);auto& A:G){
for (auto& [a,b]:A) a = lower_bound(Z.begin(),Z.end(),a)-Z.begin();
sort(A.begin(),A.end(),greater<pair<int,int>>());
if (!A.empty()) M.emplace(A.back().first,i);
++i;
}
for (int i(0);i < s;++i) if (M.size()==n-1){
R[i] = Z[M.rbegin()->first];
while(!M.empty()&&M.begin()->first==i){
auto [a,b] = *M.begin(); M.erase(M.begin());
G[b].pop_back(); if (!G[b].empty()) M.emplace(G[b].back().first,b);
}
}
vector<int> segtree(2*s);
for (int i(0);i < s;++i) segtree[s+i] = R[i]-Z[i];
for (int i(s-1);i;--i) segtree[i] = min(segtree[i<<1],segtree[i<<1|1]);
cin >> q;
while(q--){
int l,r,low,res(1e15); cin >> l >> r >> low;
if (R[0]<=r) res = min(res,max(l-Z[upper_bound(R.begin(),R.end(),r)-R.begin()-1],0ll));
int ll = upper_bound(R.begin(),R.end(),r)-R.begin(),rr = upper_bound(Z.begin(),Z.end(),l)-Z.begin();
for (ll += s,rr += s;ll < rr;ll>>=1,rr>>=1){
if (ll&1) res = min(res,segtree[ll++]+l-r);
if (rr&1) res = min(res,segtree[--rr]+l-r);
}
if (Z.back()>l) res = min(res,abs(r-R[upper_bound(Z.begin(),Z.end(),l)-Z.begin()]));
cout << (res<=low?"Yes":"No") << endl;
}
}
```
### D 3:19:06 46/100
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; cin >> n; vector<int> A(n),B; for (int& a:A) (cin>>a),B.emplace_back(a);
sort(B.begin(),B.end()),B.erase(unique(B.begin(),B.end()),B.end()); int m = B.size();
for (int& a:A) a = lower_bound(B.begin(),B.end(),a)-B.begin();
vector<int> dp0(1<<m,m),dp1(1<<m,m),res(1<<m,m);
for (int i(0);i < (1<<m);++i) res[i] = __builtin_popcount(i);
for (int i(0);i < n;++i){
swap(dp0,dp1),swap(dp1,res),fill(res.begin(),res.end(),m);
for (int k(0);k < (1<<m);++k){
if ((k>>A[i])&1) res[k] = min(res[k],dp0[k]);
for (int j(0);j < A[i];++j) if ((k>>j)&1) res[k^(1<<j)|(1<<A[i])] = min(res[k^(1<<j)|(1<<A[i])],dp0[k]);
}
for (int k(0);k < (1<<m);++k){
if ((k>>A[i])&1) res[k] = min(res[k],dp1[k]);
for (int j(0);j < A[i];++j) if ((k>>j)&1) res[k^(1<<j)|(1<<A[i])] = min(res[k^(1<<j)|(1<<A[i])],dp1[k]);
}
}
int r = 22; for (int i(0);i < (1<<m);++i) r = min({r,dp1[i],res[i]});
cout << r << endl;
}
```
### E 3:37:48 3/100
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,m; cin >> n; vector<int> A(n); for (int& a:A) (cin >> a),--a;
cin >> m;
if (m==1){
int x,y; cin >> x >> y; --x,--y;
vector<int> V(n);
while(x!=y){
if (V[x]) (cout<<-1<<endl),exit(0);
V[x] = 1,x = A[x];
}
cout << count(V.begin(),V.end(),1) << endl;
}
}
```
### E 3:49:19 0/100
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,m; cin >> n; vector<int> A(n); for (int& a:A) (cin >> a),--a;
cin >> m;
vector D(n,vector<int>(n,1e18));
for (int i(0);i < n;++i){
int x = i,y = 0;
while(D[i][x]==1e18) D[i][x] = y++,x = A[x];
}
vector<multiset<int,greater<int>>> M(n),U(n);
for (int i(0),a,b;i < m;++i){
cin >> a >> b; --a,--b;
if (D[a][b]==1e18) (cout<<-1<<endl),exit(0);
M[a].emplace(D[a][b]);
}
for (int i(0);;++i){
bool end = 1;
for (int k(0);k < n;++k){
M[k].merge(U[k]);
while(!M[k].empty()&&*M[k].begin()==0) M[k].erase(M[k].begin());
if (!M[k].empty()) end = 0,U[A[k]].emplace(*M[k].begin()-1),M[k].erase(M[k].begin());
}
if (end) (cout<<i<<endl),exit(0);
}
}
```
### E 3:53:17 12/100
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,m; cin >> n; vector<int> A(n); for (int& a:A) (cin >> a),--a;
cin >> m;
vector D(n,vector<int>(n,1e18));
for (int i(0);i < n;++i){
int x = i,y = 0;
while(D[i][x]==1e18) D[i][x] = y++,x = A[x];
}
vector<multiset<int,greater<int>>> M(n),U(n);
for (int i(0),a,b;i < m;++i){
cin >> a >> b; --a,--b;
if (D[a][b]==1e18) (cout<<-1<<endl),exit(0);
M[a].emplace(D[a][b]);
}
for (int i(0);;++i){
bool end = 1;
for (int k(0);k < n;++k) M[k].merge(U[k]);
for (int k(0);k < n;++k){
while(!M[k].empty()&&*M[k].begin()==0) M[k].erase(M[k].begin());
if (!M[k].empty()) end = 0,U[A[k]].emplace(*M[k].begin()-1),M[k].erase(M[k].begin());
}
if (end) (cout<<i<<endl),exit(0);
}
}
```
Sign in with Wallet
Connect another wallet