TCO2015 Round2D

コンテスト中のメモをアップロードします。
以下は1,3,5ページ目です。

以下は2,4,6ページ目です。

250:
累積和をとって個数で割り切れるかどうか
簡単なのでメモは問題概要を把握するために書いた3ページ目の三角形だけです。

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

class BalancedSubstrings {
	public:
	long long sum[2600];
	int num[2600];
	int countSubstrings(string s) {
		int n=s.size();
		int ret=0;
		for(int i=0;i<2600;i++)sum[i]=num[i]=0;
		for(int i=0;i<n;i++){
			if(s[i]=='1'){
				sum[i+1]=sum[i]+i;
				num[i+1]=num[i]+1;
			}else{
				sum[i+1]=sum[i];
				num[i+1]=num[i];
			}
		}
		for(int i=0;i<n;i++){
			for(int j=i;j<n;j++){
				long long tr=sum[j+1]-sum[i];
				int sz=num[j+1]-num[i];
				if(sz==0||tr%sz==0)ret++;
			}
		}
		return ret;
	}
};

500:
左からとって最後だけ上手くやる

// I like wolves!!
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class BallsInBoxes{
	public long maxTurns(long N, long K){
		long ret=0;
		long t=N/K;
		if(t>=3){
			ret+=t-2;
			N-=K*ret;
		}
		while(N>K){
			long to=(N-K-1)/2;
			N=Math.max(to+K,N-to-1);
			ret++;
		}
		return ret;
	}
}
//Powered by [KawigiEdit] 2.0!

1000:
独立な事象を上手く気にかけてDP

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

class AToughGame {
	public:
	double dp[1100];
	int sum[1100];
	double expectedGain(vector <int> prob, vector <int> value) {
		int n=prob.size();
		for(int i=0;i<1100;i++){
			dp[i]=0;
			sum[i]=0;
		}
		for(int i=0;i<n;i++){
			sum[i+1]=sum[i]+value[i];
		}
		for(int i=1;i<=n;i++){
			double p=0;
			double ks=1;
			double val=0;
			double js=0;
			for(int j=0;j<n;j++){
				if(prob[j]==1000)continue;
				double tp=ks*(double)(1000-prob[j])/1000;
				if(j<i)val+=tp*dp[j];
				if(j!=i){
					p+=tp;
				}
				ks*=(double)prob[j]/1000;
			}
			p+=ks;
			val+=sum[i];
			val/=p;
			dp[i]=val;
		//	printf("%d: %f\n",i,dp[i]);
		}
		return dp[n];
	}
};

Challenge: 問題の概要を把握してなさそうなMediumを落とした

237.46 + 389.79 + 478.74 + 50 = 1155.99 (2nd)
Rating: 2273 -> 2443 (+170)
上がり続けるVolatility見てるの楽しい