コンテスト中のメモをアップロードします。
以下は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見てるの楽しい