読者です 読者をやめる 読者になる 読者になる

AGC009

DEGwerは天才。
日露交流コンテストみたいなのが事前にあったのでネタバレを抑えるのが大変だった

A:後ろは押す場所が一意に決まるので後ろから決めていく貪欲.

B:xが誰に勝ったか、というのはわかるので、その部分をどういう順で戦わせるか考えると、相手のトーナメントの深さがわかっていれば浅いやつと先に戦えば良い.

C:dp[a][b]:Aの最後がa,Bの最後がb の通り数. とするとO(N^2). 連続して片方に置く分には(置けるなら)通り数は変わらないので、dp[a][a+1]とdp[a+1][a]の二つに着目すると、dp[a][a+1以上]みたいなのはdp[a][a+1]か0になる.これで1次元のDPにすると更新は区間になるので、頑張る.
初期化と最終的な答えは、一番初めに-infをAに,次に-infをBに割り振って、最後にinfを割り振る、と考えると楽.
本質的に同じだけどもうちょっと見通しのいい方法があって、
DPa[i][j]を,i番目まで見て最後aを置いていて、最後にbを置いたのはj となる通り数とおいて、DPa[i]という配列を一気に更新すると考えると、自然に区間sum,点val,refresh(全部0にする)が必要になる、BITでもって、最後のはこれまでのクエリを巻き戻してやればできる.

列を二つに分ける典型っぽい.

D:天才,めちゃくちゃ難しいと思う

まず実際のuninity kの構成をしたときに,中心として選んだ部分にkと書く,という風にして木にラベルを付ける問題になる.この条件は、「二つの同じラベルaの付いた頂点の間にはaより大きいラベルが存在する」と同値になる.書くのが面倒になったので公式解説に対する追加部分だけ書くと、このfの単調性は,f(x,y,..)=「各xの2進表記をinf進数だと思って足して、それより大きい最小の各桁01のもの」となることがわかるので、これから明らか.
結局この貪欲が何やってるかというと、「部分木の最小のuninity kを持つ」という嘘貪欲よりもうちょっと情報を持っていて、今kの構成状況のどの状態にいるかというのまで持って貪欲している.
これを持たなきゃいけないというのは、ただの一直線のものを端から木DPすると考えると、状態としては上述のものを持たないとどうしようもない、ということから考えつくべきっぽいが、難しいですね

E:これ解けないのは反省ですが、難しいです
まず多分木の形で考えるのはいいとして、そのあとちゃんと数式に落として、あと難しいのは深さdiがhoge個, みたいなまとめ方をするんじゃなくて最終的なもののK進表記がどうなってるか、というのを固定して考えると条件がmod K-1で一致,かつN以下 みたいなふうにかける.

どうやれば解けたかというと、数を数えるんだから、その複数ある表記法をわたって考えると難しくて、ちゃんと正規化してひとつのK進数、と思って本来数えたいものを素直に数えればよかったわけですね.

解きたかったなあ


すごいセットだった.

D:

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
int bsr(int x) { return 31 - __builtin_clz(x); }
bool B(int x,int i){return (x>>i)&1;}
const int MN = 100000;
int N;
vector<int> G[MN];
int dfs(int v,int p=-1){
	int b[20]={};
	for(int u:G[v]) if(u!=p){
		int tmp=dfs(u,v);
		rep(i,20) if(B(tmp,i)) b[i]++;
	}
	int ret=1e9;
	for(int i=19;i>=0;i--){
		if(b[i]>=2) break;
		if(b[i]==0){
			int x=0;
			for(int j=19;j>i;j--) if(b[j]) x|=1<<j;
			x|=1<<i;
			ret=x;
		}
	}
	return ret;
}
int main(){
	cin>>N;
	rep(i,N-1){
		int a,b;
		cin>>a>>b;
		a--,b--;
		G[a].pb(b);
		G[b].pb(a);
	}
	int tmp=dfs(0);
	cout<<bsr(tmp)<<endl;
}

E:

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
ll dp[2001][2001];
void add(ll &x,ll y){
	x+=y;
	x%=mod;
}
int N,M,K;
int main(){
	cin>>N>>M>>K;
	int D=(N+M-1)/(K-1);
	dp[0][0]=1;
	ll ans=0;
	rep(d,D){
		rep(a,N+1){
			int b=(K-1)*d-a;
			if(!(0<=b&&b<=M)) continue;
			rep(k,K){			//K-1 (continue)
				int na=a+k,nb=b+(K-1-k);
				if(na>N||nb>M) continue;
				add(dp[na][nb],dp[a][b]);
			}
			rep1(k,K-1){			//K (end)
				int na=a+k,nb=b+(K-k);
				if(na<=N&&nb<=M&&(N-na)%(K-1)==0&&(M-nb)%(K-1)==0) add(ans,dp[a][b]);
			}
		}
	}
	cout<<ans<<endl;
}