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

SRM669

writerでした。
解説
div2
easy:
概要:アイドルがライブをします

mapとかを使いましょう

med:
概要:あみまみがゲームをします

実はどうくっつけても同じ結果になります
例えばa,b,cとすると
a*b + (a+b)*c とかになって,一般に実は異なる二つのすべての積になります.これは簡単に計算できて,O(N)も可能です. (和の二乗-二乗の和)/2.

hard:
概要:響はいろいろ好きです

まず0-1-..(N-1)にlineを固定して,その後N!/2倍すると答えになります.
これを数えるには,d[v][u]をv-u間のコスト とすると、
d[v][u]<=d[v][v+1],d[v+1][v+2]...d[u-1][u] となる必要があります
任意のv,uについてこれが成り立つことが実は十分条件です(これの証明はマトロイド的に見ればすぐわかる)
今このline上のコストを全探索しても間に合うので,line上のコストを決め打ちした後,各辺について0になれるかどうか?を確かめていきできるなら2倍していけばOKです.
O(2^N * N^3)

div1
easy:
概要:あみまみ
最終状態のみに依存します!!!(逆から操作を見るとdiv2medと同じなので)
貪欲じゃないです。
軽いmath.

med:
div2hardの強い版.
結局d[v][u]は、
区間[u][v]の中のmax 以上であればいいので、
dp[u][v][k]=区間u-v間でmaxがkにする方法(これはu-vの間の任意の辺を決めることを含みます)(u-u+1,u+1-u+2..とかだけではない)

更新は,u-v間でどこがmaxか、を全部探索します.maxが複数ある場合は左のほうを見ることにする、と決めると選んだとこの左はk-1以下で,右はk以下でやることを強制されます.その部分をはさむような辺は全部k以上ならなんでも良いです
~以下のとこはsumとっとけばいいです
冷静に考えるとdpは区間の長さにしか依らないのでオーダーが落ちてO(N^2 * K)です

hard:

概要:やよいおりが旅行してみんなにおみやげを買う

使うお金をちいさい方から順に並べると,うまい部分でうまい具合に切れていることがわかります.なので頑張ってDPします.(説明が面倒くさくなった)
f[n][b][a]=b*M^nを,"必ず1を使い全てM^a以下で作る方法"
g[n][b][a]=(作りたい数の下n桁)の一番上の桁をbにしたもの を作る 方法, ただしM^a以下を使う(1は使わなくても良い)
とかやると,
さっき言ったうまい切れ目のところで,切れ目の直後に何を使ってるか みたいなのを全部試すと遷移が出来るようになります
(うまい切れ目というのはgを考える時に出てくるような数のこと)

コード達
d2e:

//import java.io.*;
//import java.util.Map;
//import java.util.HashMap;
public class LiveConcert{
	public static int maxHappiness(int h[],String s[]){
		Map<String,Integer> mp = new HashMap<>();
		for(int i=0;i<h.length;i++){
			String st=s[i];
			if(!mp.containsKey(st)||mp.get(st)<h[i]) mp.put(st,h[i]);
		}
		int ans=0;
		for(Integer x:mp.values()) ans+=x;
		return ans;
	}
}

d2m:

public class CombiningSlimes{
	public static int maxMascots(int[] a){
		int N=a.length;
		int ans=0;
		for(int i=0;i<N;i++) for(int j=0;j<i;j++) ans+=a[i]*a[j];
		return ans;
	}
}

d2h:

//O(2^N*N^3)
public class LineMSTDiv2{
	public static int count(int N){
		long mod=(long)(1e9+7);
		long ans=0;
		int E=N-1;
		for(int i=0;i<(1<<E);i++){
			int d[]=new int[E];
			for(int j=0;j<E;j++){
				d[j]=(i>>j)&1;
			}
			int tmp=1;
			for(int a=0;a<N;a++) for(int b=a+2;b<N;b++){
				Boolean free=true;
				for(int j=a;j<b;j++) if(d[j]==1) free=false;
				if(free){
					tmp*=2;
					if(tmp>=mod) tmp-=mod;
				}
			}
			ans+=tmp;
			if(ans>=mod) ans-=mod;
		}
		for(int i=3;i<=N;i++) ans=ans*i%mod;
		return (int)ans;
	}
}

d1e:

public class SubdividedSlimes{
	public static int best(int S,int K){
		return (S*S-S%K*(S/K+1)*(S/K+1)-(K-S%K)*(S/K)*(S/K))/2;
	}
	public static int needCut(int S,int M){
		int ub=S,lb=0;
		while(ub-lb>1){
			int m=(ub+lb)/2;
			if(best(S,m+1)>=M) ub=m;
			else lb=m;
		}
		if(ub==S) return -1;
		return ub;
	}
}

d1m:

public class LineMST{
	public static int count(int N,int L){
		long mod = (long)(1e9+7);
		long[][] ex = new long [L+1][N*N/4];
		long[][] dp = new long [N][L+1];
		for(int i=1;i<=L;i++){
			ex[i][0]=1;
			for(int j=1;j<N*N/4;j++) ex[i][j]=ex[i][j-1]*i%mod;
		}
		for(int i=0;i<N;i++) for(int j=0;j<L+1;j++){
			if(i==0){
				dp[i][j]=1;
				continue;
			}
			if(j==0){
				dp[i][j]=0;
				continue;
			}
			long val=0;
			for(int k=0;k<i;k++){
				val=(val+dp[k][j-1]*dp[i-1-k][j]%mod*ex[L+1-j][(k+1)*(i-k)-1])%mod;
			}
			dp[i][j]=(dp[i][j-1]+val)%mod;
		}
		long ans=dp[N-1][L];
		for(int i=3;i<=N;i++) ans=ans*i%mod;
		return (int)ans;
	}
}

d1h:

//O(M*(log_M(X))^3);
public class PowerPartition{
	public static int calc(int M, long X){
		int N=0;
		int[] d = new int[64];
		while(X>0){
			d[N]=(int)(X%M);
			X/=M;
			N++;
		}
		long f[][][]=new long [N][M][N];
		long g[][][]=new long [N][M][N];
		long mod=(long)(1e9+7);
	
		for(int n=0;n<N;n++) for(int b=0;b<M;b++) for(int a=0;a<N;a++){
			if(n==0){
				f[n][b][a]=1;
				continue;
			}
			long val=0;
			if(b>1){
				for(int i=0;i<=Math.min(a,n);i++){
					val=( val + f[n-i][1][a-i]*f[n][b-1][i] )%mod;
				}
			}else{
				for(int i=0;i<=Math.min(a,n-1);i++){
					val=( val + f[n-1-i][1][a-i]*f[n-1][M-1][i] )%mod;
				}
			}
			f[n][b][a]=val;
		}
		for(int n=0;n<N;n++) for(int b=0;b<=d[n];b++) for(int a=0;a<N;a++){
			if(n==0){
				g[n][b][a]=1;
				continue;
			}
			long val=0;
			if(b>0){
				for(int i=0;i<=Math.min(a,n);i++){
					val=( val + f[n-i][1][a-i]*g[n][b-1][i] )%mod;
				}
			}else{
				val=g[n-1][d[n-1]][a];
			}
			g[n][b][a]=val;
		}
		return (int)g[N-1][d[N-1]][N-1];
	}
}