SRM 632

明日は天プロです。

300:
それぞれの区間について、条件を満たすためには、
・最大値は1つ。
・ほかの場所はd[i]がその最大値からの距離の2進表記の最後の0の個数。

5位。

// I like wolves!!
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <string.h>
#include <complex>
using namespace std;

class PotentialArithmeticSequence {
	public:
	int numberOfSubsequences(vector <int> d) {
		int ret=0;
		int n=d.size();
		for(int i=0;i<n;i++){
			for(int j=i;j<n;j++){
				int m=-1;
				int at=0;
				for(int k=i;k<=j;k++){
					if(m<d[k]){
						m=d[k];
						at=k;
					}
				}
				bool ok=true;
				for(int k=i;k<=j;k++){
					if(k==at)continue;
					if(m==d[k])ok=false;
					int t=abs(at-k);
					int cnt=0;
					while(t%2==0){
						t/=2;cnt++;
					}
					if(cnt!=d[k])ok=false;
				}
				if(ok)ret++;
			}
		}
		return ret;
	}
};

//Powered by [KawigiEdit] 2.0!

500:
さすがにフローじゃないだろうし苦手なグラフはとりあえずスルーで→フローでした・・・

900:
・真ん中から適当にとって選ぶと再訪問のときはもうそれはなかったものとしてよい
・左と右で訪れる回数は同じか1差。
・残りm個あるところからk個使う方法の個数は(m-k+1)*2^(k-1)とおり。
・2べきはあとでまとめてよい(2^(N-訪れる回数)をあとからかけるだけ)
・dp[i][j]: ラストi回でj個訪れたときの(m-k+1)の積の合計、とする。
・dp[i][j]からdp[i+1][k]に足す値はdp[i][j]*jとなる。配るDP+imos法でここをまとめることができる。
こうするとO(N^2)。

// I like wolves!!
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <string.h>
#include <complex>
using namespace std;

class PatternLock {
	public:
	int mod;
	long long pow2[10000];
	long long dp[3510][3510];
	long long fact[10000];
/*	int solve(int L,int R,int s){
		if(~dp[L][R][s])return dp[L][R][s];
		if(L==0&&R==0)return dp[L][R][s]=1;
		
	}*/
	long long sum[3510];
	int solve(int N, int MOD) {
		mod=MOD;
		pow2[0]=1;
		for(int i=1;i<10000;i++)pow2[i]=pow2[i-1]*2%MOD;
		fact[0]=1;
		for(int i=1;i<10000;i++)fact[i]=fact[i-1]*i%MOD;
		//for(int i=0;i<3500;i++)for(int j=0;j<3500;j++)
		//	for(int k=0;k<2;k++)dp[i][j][k]=-1;
		dp[0][0]=1;
		for(int i=0;i<N;i++){
			for(int j=0;j<3510;j++)sum[j]=0LL;
			for(int j=0;j<N;j++){
				sum[j+1]=dp[i][j]*(j+1)%MOD;
			}
			long long now=0;
			for(int j=1;j<=N;j++){
				now=(now+sum[j])%MOD;
				dp[i+1][j]=now;
			}
		}
		long long ret=0;
		for(int i=1;i<=N;i++){
			ret=(ret+dp[i][N]*dp[i][N]%MOD*pow2[N-i]%MOD*pow2[N-i])%MOD;
			ret=(ret+dp[i][N]*dp[i-1][N]%MOD*pow2[N-i]%MOD*pow2[N-i+1])%MOD;
		}
		return ret*2%MOD;
	}
};

//Powered by [KawigiEdit] 2.0!

292.03 + 0 + 379.56 + 0 = 671.59 (25th)
Rating: Unrated -> 2236

Hard初ACでした。これもDiv1Hardを大量に練習したおかげです。みなさんも300問解きましょう。