JOI 2025/2026 セミファイナル 参加記

JOI2025/2026のセミファイナルに参加しました。
それに関していろいろ書いてみます。

結果だけ言うとこんな感じでした。

1. はじめに

tau1235という名前でAtCoderなどをやっています。
こういうのを書くのは初めてなので読みづらいところなどあると思いますが許してください。
今回がJOI初参加ということもあり、かなり緊張しましたが、ボーダー(暫定)の324点を超えることができて嬉しいです。特に変なことがなければこのままファイナルに進出できるのですが、今これを書いている時点(2/2)ではどうなるかが確定していないので、常に精神をすり減らし続けています。
考えすぎてもしょうがない部分なので、得点変動がないと信じてこれ以降書きます。

何も考えずに書きすぎて思ったより長くなってしまったので、適宜読み飛ばしてください。

2. 一次予選

5分切りを狙っていましたが、2回目は30分遅刻し、3回目は普通に忘れていて参加できなかったのでベストタイムは1回目の5:18でした。

3. 二次予選

コンテストが終わった後、さすがに通るだろうとは思いました。
せっかくだからFも解いて全完したかったのと、Bが個人的に難しかったです。

4. セミファイナル(本選)

本編です。

装備とか

周りと比べてもかなりカスな装備で受けたと思います。
普段は家にあるデスクトップpcでコンテストなどに参加しているのですが、今回からオンサイト開催になったのでノートpcを持っていく必要があります。
ですが、持っていけるノートpcがChromebookとかいうスクラップしかなかったのでそれを使わざるを得ないという状況でした。どれくらいひどいかというと、VSCodeを使おうとすると重すぎてまともに使えないくらいです。タイピングしたものが反映されるまで0.5秒くらいの遅延があったり、デバッグモードを起動するのに3秒くらいかかります。

VSCodeがまともに使えないので、今回はvimを使いました。ちょっと設定をいじったのと、時々練習してvimに慣れようとしてたこともあり、本番は操作に関してそこまで苦労せずできたので、vimを使うことによる影響はそこまで出なかったとは思います。

お菓子を持ち込んでいいということで、コンビニで昼ご飯を買うついでにハイチュウ(粒がいっぱい入ってるやつ)を買いました。意外と量があって、4時間ずっと食べ続けられたので良いです。
会場にあったチョコを2つもらいました。欲を言えばもっと欲しかったですが、くれるだけ感謝すべきです。おいしかったです。

競技前

11:30ぴったりにビル前くらいにつきました。時間管理が上手すぎる。
その後コンビニで買った昼ご飯を食べるスペースを探してうろうろしていたんですが、全然見つからなくて時間かかりました。20分くらい経って、どっかの広場みたいなところに漂着しました。
なんかイベントみたいなのをやってたらしく、人が結構いました。そこの広場の端に群生していたベンチで昼食。イベントで賑わっている一方、そこだけ人がほぼいなくて静かだったので落ち着いて食べれました。

結局会場に入ったのは12:00過ぎくらいでした。意外と人がいて驚きました。
ちなみに会場の右奥らへんに座っていました。

競技

考えたこととかを書きます。記憶力が弱すぎて競技中の内容を既に忘れかけているので、一部記憶の捏造があるかもしれません。ないかもしれません。
せっかくなので詳しめに書きましたが、別に分かりやすいわけでも読みやすいわけでもないです。

一応コンテストページを貼っておきます。
https://atcoder.jp/contests/joi2026sf

A (100点)

右側のVIP席を固定すればいいです。AC(0:04)

コード(AC)

#include<bits/stdc++.h>
using namespace std;

int main(){
	int inf=2e9;
	int n;
	cin>>n;
	vector<int> a(n*2+2);
	int m0=-inf,m1=-inf;
	for (int i=0;i<n*2+2;i++)	cin>>a[i];
	int ans=-inf;
	for (int i=0;i<n*2+2;i++){
		if (i%2==0) m0=max(m0,a[i]);
		else ans=max(ans,a[i]+m0);
	}
	cout<<ans<<endl;
}

B (100点)

それぞれの区間$[S_i,T_i]$について、考えるべき$[L_j,R_j]$についての条件を考えると、$S_i\le R_j$と$L_j\le T_i$を満たしていればいいことが分かります。BITを使いました。
$L_j,T_i$の昇順に区間を見ていきます。$L_j\le T_i$な$j$のうち$S_i\le R_j$なものの$C_j$の総和が分かればいいので、$R_j$が同じ$j$について$C_j$の総和をBITなどで更新しつつ、適宜答えを計算していけばいいです。区間の左端の最大値を$K$として、$O((N+M)\log K)$でできます。座圧などをする必要がなかったので楽です。AC(0:15)
fenwicktreeをincludeするとき、

• fenwicktree
• fewnicktree
• fenwick_tree
• fewnick_tree

の4通りで迷っていつも勘で書いているのですが、今回は4通り全部外して泣きました。
これ一生覚えられないです。

コード(AC)

#include<bits/stdc++.h>
#include<atcoder/fenwicktree>
using namespace std;

int main(){
	using ll=long long;
	ll mt=1e6+10;
	int n;
	cin>>n;
	vector<vector<pair<int,int>>> g(mt);
	for (int i=0;i<n;i++){
		int l,r,c;
		cin>>l>>r>>c;
		g[l].push_back({r,c});
	}
	int m;
	cin>>m;
	vector<vector<pair<int,int>>> g2(mt);
	vector<ll> ans(m);
	for (int i=0;i<m;i++){
		int s,t;
		cin>>s>>t;
		g2[t].push_back({s,i});
	}
	atcoder::fenwick_tree<ll> fw(mt);
	for (int i=0;i<mt;i++){
		for (auto [r,c]:g[i]) fw.add(r,c);
		for (auto [s,j]:g2[i]) ans[j]=fw.sum(s,mt);
	}
	for (int i=0;i<m;i++) cout<<ans[i]<<endl;
}

C (100点)

多分ボーダー超えのために一番重要だった問題だったと思います。先に言うと、自分のコードは多分落とそうと思えば落とせます。これのせいで点数が確定するまで全く安心できないんですね～
そういえば、これまでの本選ではこういう問題は珍しいような気がしました。

重要そうなところ

1. $s=\{1,2,4,8,16,32\}$とすることが可能なので$k=6$にできます。よって、$k\le5$を考えればいいです
2. $s$に重複がある場合(これを$a$とする)、$\{a,a\}$から作れる和は$\{0,a,2a\}$の3つで、$\{a,2a\}$から作れる和が$\{0,a,2a,3a\}$と上位互換なことから、片方を$2a$に置き換えても損しないので、$s$に重複はないとしていい

1,2を考えると、$s$の候補は$_{63}C_5=7028847$程度です。これらすべてについて$O(2^k+N)$かけて判定していけばいいです。しかし、コードテストで試した感じだと3sくらいかかって間に合わなそうでした。とりあえずそのまま提出して66点。(1:10)
何が重いのかもよくわかりません。$k\ge \log_2N$は必要なので、$N\ge 32$なら$k=6$が確定し、$N\le32$とできるのですが、それでも2sには間に合わなそうでした。(不等号は適当)

結局、一旦諦めて他の問題に行こうと思い、やけくそで1.8sで打ち切りにするコードを書いて提出しました。少しでも部分点が取れればいいな、の気持ちだったのですが、なぜか満点が取れました。そんなことある？ AC(1:14)

想定解では、$O(2^k+N)$の判定部分をbitsetで高速化していました。なぜこれを思いつかなかったのかよくわからないです。

コード(AC)

#include<bits/stdc++.h>
using namespace std;

int main(){
  clock_t start=clock();                                     
	int n;
	cin>>n;
	vector<int> a(n);
	for (int i=0;i<n;i++){
		cin>>a[i];
		a[i]-=23;
		if (a[i]>0){
			cout<<"No\n";
			return 0;
		}
		a[i]=-a[i];
	}
	int t=63;
	vector<int> vec(100);
	vector<bool> ok(1000);
	vector<int> ans={1,2,4,8,16,32};
	int sz=6;
	int cnt=0;
	bool flag=false;
	auto dfs=[&](auto dfs,int v,int c)-> void {
		if (c>=min(n+1,6)||flag) return;
		if (v==t+1){
      clock_t end=clock();
      double time=(double)(end-start)/CLOCKS_PER_SEC*1000;
      if (time>1800){
        flag=true;
        return;
      }
			if (c<sz){
			  cnt++;
	      int s=0;
	      for (int bit=0;bit<1<<c;bit++){
	        s=0;
	        for (int i=0;i<c;i++) if (bit>>i&1) s+=vec[i];
	        ok[s]=true;
	      }
	      bool ret=true;
	      for (int i=0;i<n;i++) ret&=ok[a[i]];
	      for (int bit=0;bit<1<<c;bit++){
	        s=0;
	        for (int i=0;i<c;i++) if (bit>>i&1) s+=vec[i];
	        ok[s]=false;
	      }
			  if (ret) ans=vec,sz=c;
			}
			return;
		}
		vec[c]=v;
		dfs(dfs,v+1,c+1);
		dfs(dfs,v+1,c);
	};
	dfs(dfs,1,0);
	cout<<"Yes\n";
	cout<<sz<<endl;
	for (int i=0;i<sz;i++) cout<<ans[i]<<" \n"[i==sz-1];
}

D (45点)

パッと見で難しそうだったので、一旦E,Fの問題文を見に行きました。Eの小課題1は実装をやるだけなので、しました。
その後またDに戻ってきてDを考えました。よく見ると木についての話をしていることに気づき、木dpを考えたくなったので、必要そうな条件を考えてみます。
$dp[i][j][k]:=$頂点$i$を$j$回通り、部分木$i$でまだ照らされていない頂点のうち最も深い頂点と$i$との距離が$k-1$であるときのコストの合計の最小値
わざわざ$k-1$にしてるのは、全頂点が照らされてる状態を$k=0$にしたかったからです。

これを根から計算していくときの遷移については、$dp[i][子のjの総和][子のkの\max]$のような遷移になります。
すべての子についてdpテーブルをマージしたあと、部分木$i$のどこかしらに何回か移動する、という遷移も必要なはずです。これは部分木$i$のうち$C$の最小値を求めておけばいいです。
最後に、$j\ge k+1$なら$k=0$として適当に遷移させます。あとは根性でこれを実装します。
(説明が雑なので実装を見たほうが分かりやすいかも)

2乗の木dpっぽく実装すると時間も空間も$O(N^3)$くらいになると信じて提出しましたが、MLEもTLEも大量に出てしまいました。この時点で38点。(2:28)
(書いてる途中で気づきましたが、この実装だと多分時間が$O(N^4)$になります。)

子からのマージが終わったら、$O(N^2)$サイズの子のdpテーブルをclear()するようにしたところ、小課題3が通るようになり45点に。(2:36)

ここからはよくわかりませんでした。dfsの中で$O(N^2)$サイズのdpテーブルを作ると、dfsの深さが深くなるときにやばいことに気づいたので、dfsの外側に直前のdpテーブルだけ持たせるように実装したつもりなのですが、なぜか答えが合いません。理由は今も分かりません。

コード(45点)

dfsの外で直前のdpテーブルだけ持たせる実装をする前の実装です

#include<bits/stdc++.h>
using namespace std;

int n;
using ll=long long;
vector<ll> p,c;
ll inf=1e18;
void solve4(){
	vector<int> sz(n);
	vector<vector<int>> g(n);
	for (int i=1;i<n;i++){
		g[i].push_back(p[i]);
		g[p[i]].push_back(i);
	}
	vector<ll> mc=c;
	auto dfs=[&](auto dfs,int v)-> vector<vector<ll>> {
		sz[v]=1;
		vector<vector<ll>> dp(n+1,vector<ll>(n+1,inf));
		dp[0][0]=0;
		for (int u:g[v]) if (u!=p[v]){
			auto prev=dfs(dfs,u);
			vector next(n+1,vector<ll>(n+1,inf));
			for (int i=0;i<=sz[v];i++){
				for (int j=0;j<=sz[u];j++){
					for (int k=0;k<=sz[v];k++){
						for (int k2=0;k2<=sz[u];k2++){
							next[i+j][max(k,k2)]=min(next[i+j][max(k,k2)],dp[i][k]+prev[j][k2]);
						}
					}
				}
			}
			swap(next,dp);
			mc[v]=min(mc[v],mc[u]);
			sz[v]+=sz[u];
		}
		vector next(n+1,vector<ll>(n+1,inf));
		for (int i=0;i<=sz[v];i++) for (int j=sz[v]-1;j>=0;j--){
			for (int k=0;i+k<=sz[v];k++){
				if (i+k>=j+1) next[i+k][0]=min(next[i+k][0],dp[i][j]+k*mc[v]);
				else next[i+k][j+1]=min(next[i+k][j+1],dp[i][j]+k*mc[v]);
			}
		}
		dp=next;
		return dp;
	};
	auto dp=dfs(dfs,0);
	ll ans=inf;
	for (int i=0;i<=n;i++) ans=min(ans,dp[i][0]);
	cout<<ans<<endl;
}
int main(){
	cin>>n;
	p=vector<ll>(n),c=vector<ll>(n);
	p[0]=-1;
	bool f3=true,f4=true;
	for (int i=1;i<n;i++){
		cin>>p[i],p[i]--;
		f3&=p[i]==0;
		f4&=p[i]==i-1;
	}
	for (int i=0;i<n;i++) cin>>c[i];
    solve4();
}

E (5点)

一番点数が低いです。
小課題1についてはDのところでも書きましたが、そのまま実装しました。(1:35)
それ以降の考察ですが、本当に何も得られませんでした。

解説を見たところ、この操作はプリム法なので最小全域木の辺しか使わないらしい。$C$が相異なることから最小全域木は一意だから小課題2とかが解ける、ということっぽいです。

プリム法の存在を完全に忘却してたのも良くないですが、単に忘れてたことを言い訳にするのも良くない気がしてます。(極論かもしれませんが、コンテスト中にプリム法(というかこの問題に出てくる操作)が最小全域木を取る証明ができればいいので)
まあどっちにしろ自分が弱いのが悪いです。

コード(5点)

#include<bits/stdc++.h>
using namespace std;

int n,m,t;
vector<vector<pair<int,int>>> g;
using ll=long long;
void solve1(){
	vector<ll> ans(n);
	for (int s=0;s<n;s++){
		priority_queue<pair<int,int>> q;
		q.push({0,s});
		vector<bool> vis(n);
		int now=0;
		while (!q.empty()){
			auto [d,v]=q.top();
			q.pop();
			if (vis[v]) continue;
			vis[v]=true;
			ans[v]+=now++;
			for (auto [u,c]:g[v]){
				if (vis[u]) continue;
				q.push({-c,u});
			}
		}
	}
	while (t--){
		int x;
		cin>>x;
		x--;
		cout<<ans[x]<<endl;
	}
}

int main(){
	cin>>n>>m>>t;
	g=vector<vector<pair<int,int>>>(n);
	for (int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		a--;b--;
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	if (n<=2000) solve1();
}

F (10点)

問題文の通り、変な操作をしています。とりあえず、表裏をそれぞれ2,1の位に、白黒をそれぞれ1,0に対応させて、それぞれの状態を$0,1,2,3$で表してみました。すると、状態$a,b$についての操作は、$((a$の位入れ替え$)) \oplus b)$ に置き換える操作になります。(結局、自分が解いた中ではこの言い換えは何の意味もありませんでした。そもそもこの言い換え自体無理やり感が強いので、この問題を解く上で必要ない言い換えだと思いますが、一応書きました)

$dp[l][r][i]:=$区間$[l,r)$をマージして状態$i$を作れるか
というのは$O(N^3)$で計算できます。これを使って、

$ep[l][r][i]:=$区間$[l,r)$のうち表面が白なものが$i$個あるようにできるか
というのを$O(N^4)$で計算します。一瞬$O(N^5)$になると思って焦りましたが、よく考えたら4乗に落とせました。(単純にアルゴ力が低い)
これで小課題2の10点、と思いきやWA。
操作について勘違いしてて、表裏を逆で考えていたことにしばらく気づいていませんでした。これで15分くらい溶かしたの、アホすぎる。問題文はよく読みましょう。さっと修正して10点。(3:43)

これをちょっと変えれば小課題1でも使いまわせるのですが、Dに粘着しに行ってしまったので結局取れていません。

コード(10点)

#include<bits/stdc++.h>
using namespace std;

int n,q;
string s,t;
void solve1(){
	vector dp(n+1,vector(n+1,vector<bool>(4)));
	vector<int> val(n);
	for (int i=0;i<n;i++){
		val[i]+=2*(s[i]=='W');
		val[i]+=(t[i]=='W');
	}
	for (int i=0;i<n;i++) dp[i][i+1][val[i]]=true;
	auto f=[&](int a,int b){
		int rev=(a&2)/2+(a&1)*2;
		return (b^rev);
	};
	for (int d=2;d<=n;d++){
		for (int l=0;l<n;l++){
			int r=l+d;
			if (r>n) break;
			for (int mid=l+1;mid<r;mid++){
				for (int i=0;i<4;i++) for (int j=0;j<4;j++){
					if (dp[l][mid][i]&&dp[mid][r][j]){
						dp[l][r][f(i,j)]=true;
					}
				}
			}
		}
	}
	vector ep(n+1,vector(n+1,vector<bool>(n+1)));
	for (int i=0;i<=n;i++) ep[i][i][0]=true;
	for (int d=1;d<=n;d++){
		for (int l=0;l<n;l++){
			int r=l+d;
			if (r>n) break;
			for (int mid=l+1;mid<=r;mid++){
				for (int j=0;j<4;j++) if (dp[l][mid][j]){
					for (int i=0;i<=n;i++) if (ep[mid][r][i]){
						if (i+j/2<=n) ep[l][r][i+j/2]=true;
					}
				}
			}
		}
	}
	while (q--){
		int p;
		cin>>p;
		int l,r,m;
		cin>>l>>r>>m;
		l--;
		if (ep[l][r][m]) cout<<"Yes\n";
		else cout<<"No\n";
	}
}
int main(){
	cin>>n>>s>>t>>q;
	if (n<=100) solve1();
	else assert(0);
}

競技後

ボーダー発表まで

問題数が5問から1問増えたことで、ボーダーラインがいつもより上がり、Dまでが満点必須になるだろうと予想していたこともあり、ボーダーは400くらいになることを覚悟していました。それに加え、Discordで自分より点数が高い人がまあまあいて、絶望していました。競技終了後は、さすがに落ちたかな、と放心状態でした。

そういえば、この時間にtatyamさんが話しかけてくれました。ICPCの放送(確か)で顔は見たことはありましたが、実際に見たり話したのは初めてだったので、嬉しかったです。キャラメルを配っていました。おいしかったです。
放心状態だったこともあり、残念ながら会話はあまり覚えていないのですが、難しめのセットだったみたいなことを言ってた気がします。

ボーダー発表

緊張しました。ボーダーの発表がされた後のことは、驚きすぎてあまり記憶にありません。正直、実感がなさ過ぎて今も結果を疑っています。

それ以降

社会性が終わっているので、比較的すぐ会場を出ました。会場を出る前に、chokudaiさんと写真を撮ってもらおうかとも思いましたが、ハードルが高くて諦めてしまいました。
その後はマックを食べて帰宅しました。

5. セミファイナルまでにやったこと

いわゆる精進というやつです。他の人と比べても同じようなことをやってると思います。
この記事の中で、読む価値が一番ありそうなところは多分ここです。

主にやったこと

• コンテストに出る
• 難易度9までを埋める
• バチャを走る

1 - コンテストに出る

出れるコンテストには基本参加しました。AtCoder,yukicoder,Codeforces,CodeChefなど、ひたすら参加して生活習慣が破壊されていた時期もありました。生活習慣は大事にしましょう。
私の場合はRatedで出れるものはRatedで出るようにしていました。Unratedで出るとやる気をなくす気がして、なんとなくRatedで参加しています。そこまで深い理由はないです。

2 - 難易度9までを埋める

2020年くらいまでの難易度5~9を順に埋めていました。
考察ストックを作るために、時間があるときに問題文を読んで、通学時間や授業中に考察をする、というのをほぼ毎日やっていました。これをすると、必然的に競プロのことを考える時間が増えるので、案外良かったのかもしれません。

3 - バチャを走る

1つ前の項目で、2020年以降を解かなかったのはこれをするためです。2週間くらい前からJOIの本選バーチャルコンテストをやっていました。ボーダーを超えたのは6回中4回だったらしいです。
本番の時間感覚とか緊張感とかに慣れるためにも何回かやっておくことをお勧めします。
特に、バーチャルコンテストではバーチャル順位表というものが見れると思うのですが、見ないでやることを強く勧めます。自分だけの可能性もありますが、順位表が見れるときと見れないときを比べると、この問題は結構解かれてるからもう少し考えてみる、とか、あと数点とったらボーダーは超えそうだからこの小課題は何としても解こう、みたいなのができないので、精神的にも立ち回り的にも結構変わると思ってます。
本番はもちろん順位表を見れないので、それに慣れるためにもバーチャルコンテストはやるべきな気がします。

6. さいごに

来年以降

自分は来年のJOIには出るつもりはないです。なので、今回が最初で最後のJOI参加だったということになるのですが、まあ頑張った方だと思います。

来年もチャンスがある人へ

来年も参加する予定の人は、頑張ってください。1年は長いようで短いようで長いので、なんとでもなると思います。なんとでもなる、というのは言い方が良くないかもしれないので付け加えると、もし自分が去年JOIに出ていたとしても、ぎりぎり二次予選を通過できるかどうかのレベルだったので、1年あればこのくらいまでは行ける可能性があるということです。

去年のこの時期のレートを見てみたのですが、ちょうど入水したくらいでした。
https://atcoder.jp/users/tau1235/history/share/abc392

参加できるけど参加するする予定がない人は、参加してみてほしいです。私は去年参加しなかったことをかなり後悔しています。初参加がラストイヤーなのは流石にプレッシャーがやばかったです。
一次予選で落ちようが二次予選で落ちようが、参加して損になることはほぼないです。

蛇足

不正とかの話？(見なくていい)

あまりこういう話はしないようにしていましたが、いい機会(?)なので書きたくなってしまいました。この記事の中で一番価値のない所です。

最近、AtCoderとかAJLとか競プロ周りでAIとか不正やらが度々話題になりますね。
今回のセミファイナルに参加した人たちはある程度信頼できそうな気もします？
もしセミファイナルで不正に成功した人がいたら教えてください。普通にどうやったかが気になります。

定期的にオンサイトに参加するくらいしか信用を得る方法ってなさそうなんですけど、どうなんでしょうか。そもそも信用なんて必要か？という話もあります。
ただ、実際は不正してないのに不正をしていると言われるのは誰でも嫌な気持ちになりそうなので、それは私もちょっと嫌かもしれません。

こういうことを気にせず生きていけるようになりたいです。

ファイナル(春合宿)に向けて

できる限りやります。IOI代表まで行くのは流石に無理だと思いますが、可能性は0ではないので頑張ります(自分以外の全員のパソコンが壊れるくらいのことが起きないと厳しい)。
まあ、セミファイナルの成績はファイナルに出る人の中で下位の方だと思うので、ファイナルではせめて中位くらいには入りたいですね。

せっかくなので、今回のセミファイナルのD,E,F(解けてないやつ)のupsolveも近いうちにやりたいです。
Eの小課題2くらいまでは解説を見ましたが、他はまだ見てないので、もう少し考えて粘ろうと思います。

それと、ファイナルまでに入黄したいです。入黄したら入黄記事も書きたいです。
ちなみに、今までARCで黄perfを取ったことがないので、今ABCで勝って入黄したとしても秒で青に戻りそうです。
ARCを解きまくる期間をそろそろ作りたいです。

ファイナル出る人へ

自分は今回のセミファイナルではほとんど人と話すことができなかったので、ファイナルではもう少し話せたらいいと思ってます。誰か話しかけてください(他力本願)。話しかけてくれると泣いて喜びます。

本当に最後

ここまで色々書いてみましたが、調子に乗ってかなり偉そうなことを書いた気がします。強い人から見ると鼻で笑われるような内容だったと思いますが、許してください。
修正した方がよさそうな内容や誤字などがあれば修正します。

ここまで書いておいて、点数変動で落ちる可能性があるのが本当に怖いです。
ファイナルに参加できたらまた参加記を書くつもりなので、読んでくれるとうれしいです。