SRM661

oo- +1-0 14th (2056->2159) チャレンジは偉大.

あさめだけあって楽なセットだった.反省点はMedでループ変数をintにしてたらよくわからないがバグってしまったこと(sampleでバグってよかった).適当にrepを使うんじゃなくやっぱりllでまわすべきだった.あとHardは出来るべきな気はする.

Easy:
LCM(1,...M)=LCM(N+1,...M)なる最小のMを求めよ(N<=1e6)
各素数毎に一番でかい素べきの倍数ではじめにNを超えるもの、みたいなののmax
実は各素ベキに対して2倍を取る,でも多分通る(ある範囲(3N/4 ~ N)に素ベキがあってはいけない、みたいな条件になるので多分正しいけど証明はむずそう)

Med:
i個目までのwayを1つ取ってくると,その次に色xを塗る方法の数(=i個のうちその色でない数+1(辺を生やさない))、のxに関する総和を取ると、(K-1)i+Kになるのでこれをi=0~N-1までかけるだけ(xについて線形なのでmod Mで高々周期Mのループする)

Hard:

結局距離の最大値を取りうるところとして,左右端のコの字部分(青),一つの区切りの中(緑)(これは上下に渡ってるとは限らない),複数の区切りにわたって(赤)(端っこのところで直接右に行くor遠回りして下から右に行くの2択があることに注意)の種類がある.
dp[i][j][x]="iまでj本置いて今iより左のところでの距離の最大がx の時の,i都の距離の最大値"を持つ.つまり覚えるべき場所として青とか緑とかの既に完結してるところの値と,これから伸びうる赤みたいな部分に影響する場所の2つが必要なのでこんなかんじになる.
これで遷移が次にどこに置くかのN通りだからO(N^3*N*K)になる.ダメ.
そこでx以下に出来るか?のにぶたんをする.そうするとxは覚えなくて済む(そのかわり遷移毎に閉じた方(緑,青)がx以下になってるか確かめる必要がある).そうするとO(N^3 log(NK) )になって通る.
計算すべきもの(区間に対する左端との最大の距離,とか)は先に計算しとく.緑がちょっとめんどい.
1000もない気がするけどさすがに時間内に通すのはつらそう.

Easy:

#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++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
const ll ccc=1000000;
bool prime[ccc+1];
vector<ll> pr;
void makeprime(){
	ll i,j;
	for(i=2;i<=ccc;i++) prime[i]=true;
	for(i=2;i*i<=ccc;i++) if(prime[i]) for(j=2;j*i<=ccc;j++) prime[j*i]=false;
	for(i=2;i<=ccc;i++) if(prime[i]) pr.push_back(i);
}

class MissingLCM{
	public:
	int getMin(int N){
		makeprime();
		ll M=N;
		for(ll p:pr){
			int a=-1;
			ll tmp=N;
			while(tmp) tmp/=p,a++;
			ll x=1;
			rep(i,a) x*=p;
			chmax(M,(N/x+1)*x);
		}
		return M;
	}
};

Med:

#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++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
ll ex(ll x,ll p,ll M){
	ll a=1;
	while(p){
		if(p%2) a=a*x%M;
		x=x*x%M;
		p/=2;
	}
	return a;
}
vector<ll> vc;
class ColorfulLineGraphs{
	public:
	int countWays(long long N, long long K, int M){
		ll ans=1,t=0;
		for(ll i=0;i<N;i++){
			ll x=((K-1)*i+K)%M;
			if(i>0&&x==vc[0]){
				t=i;
				break;
			}
			vc.pb(x);
		}
		if(t==0){
			rep(i,N) ans=ans*vc[i]%M;
			return ans;
		}
		rep(i,t) ans=ans*ex(vc[i],N/t,M)%M;
		N%=t;
		rep(i,N) ans=ans*vc[i]%M;
		return ans;
	}
};

Hard:

#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++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int dp[201][201],l[201][201],r[201][201],d[201][201],mn[201][201],mx[201][201];
int inf=1e9;
int sa[200],sb[200];
bool can(int N,int K,int ub){
	rep(i,N+1) rep(j,K+1) dp[i][j]=inf;
	dp[0][0]=0;
	rep(i,N){
		rep(j,K){
			if(dp[i][j]==inf) continue;
			for(int k=i+1;k<=N;k++){
				if(i==0){
					if(mx[1][k]+mn[1][k]<=ub) chmin(dp[k][j+1],mx[1][k]);
				}else{
					if(dp[i][j]+l[i][k]<=ub&&d[i][k]<=ub){
						chmin(dp[k][j+1],max(dp[i][j]+mn[i][k],r[i][k]));
					}
				}
			}
		}
	}
	rep1(i,N){
		if(dp[i][K]+mx[i][N]<=ub&&mx[i][N]+mn[i][N]<=ub) return true;
	}
	return false;
}
int da(int i,int j){
	return sa[j-1]-sa[i-1];
}
int db(int i,int j){
	return sb[j-1]-sb[i-1];
}
class BridgeBuilding{
	public:
	int minDiameter(vector <int> a, vector <int> b, int K){
		int N=a.size()+1;
		sa[0]=0,sb[0]=0;
		rep(i,N-1) sa[i+1]=sa[i]+a[i];
		rep(i,N-1) sb[i+1]=sb[i]+b[i];
		for(int i=1;i<=N;i++) for(int j=i+1;j<=N;j++){
			mn[i][j]=min(da(i,j),db(i,j));
			mx[i][j]=max(da(i,j),db(i,j));
			for(int k=i;k<=j;k++){
				chmax(l[i][j],min(da(i,k),da(k,j)+db(i,j)));
				chmax(l[i][j],min(db(i,k),db(k,j)+da(i,j)));
				chmax(r[i][j],min(da(k,j),da(i,k)+db(i,j)));
				chmax(r[i][j],min(db(k,j),db(i,k)+da(i,j)));
			}
			int s=0;
			vector<int> vc;
			for(int k=i;k<j;k++) vc.pb(a[k-1]),s+=a[k-1];
			for(int k=j-1;k>=i;k--) vc.pb(b[k-1]),s+=b[k-1];
			int M=vc.size();
			vector<int> vs(2*M+1);
			vs[0]=0;
			rep(i,M) vs[i+1]=vs[i]+vc[i];
			rep(i,M) vs[i+M+1]=vs[i+M]+vc[i];
			int y=0;
			for(int x=0;x<M;x++){
				while(vs[y]-vs[x]<=s/2) y++;
				chmax(d[i][j],min(vs[y]-vs[x],s-(vs[y]-vs[x])));
				chmax(d[i][j],min(vs[y-1]-vs[x],s-(vs[y-1]-vs[x])));
			}
/*			printf("   i,j=  %d,%d\n",i,j);
			show(mn[i][j]);
			show(mx[i][j]);
			show(l[i][j]);
			show(r[i][j]);
			show(d[i][j]);*/
		}
		int ub=20000,lb=0;
		while(ub-lb>1){
			int m=(ub+lb)/2;
			if(can(N,K,m)) ub=m;
			else lb=m;
		}
		return ub;
	}
};