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]; } }