HIR180's diary

ICPC World Finals 2022 を集大成に

2014-02-04

■ TopCoder SRM 607 && Codeforces 228 Div1 06:09

SRM 607

ここまで1800後半で臨んだSRMは0完だったので絶対1900の壁を越えると誓う。

Med開けしました

Med:

どうみても区間DPやるだけ。書く...がサンプル通らない

大きく回して内側をごにょごにょやれば良いパターンがあることに気づく

諦める

Easy:

割と難しそうであることがわかる。

ちょっと考えるとdp[i][j]=[i,j]が回文になる確率というO(N^2)のDPが生えたので

頑張ると通る。

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
using namespace std; 
typedef pair<int,int> P; 
typedef pair<int,P> P1; 
typedef pair P2; 
typedef long long ll; 
#define pu push 
#define pb push_back 
#define mp make_pair 
#define eps 1e-7 
#define INF 2000000000 
#define f first 
#define s second 
#define rep(i,x) for(int i=0;i
double dp[5005][5005]; 
class  
PalindromicSubstringsDiv1 
{ 
  public: 
  double expectedPalindromes(vector  S1, vector  S2) 
  { 
    string s; 
    for(int i=0;ifor(int j=0;jfor(int i=0;i1.0; 
    for(int i=0;iif(s[i]=='?') 
    { 
      if(i) dp[i-1][i]=1.0/26.0; 
      for(int j=0;j1;j++) 
      { 
        dp[j][i]=dp[j+1][i-1]*1.0/26.0; 
      } 
    } 
    else 
    { 
      if(i) 
      { 
        if(s[i-1]=='?') dp[i-1][i]=1.0/26.0; 
        else dp[i-1][i]=(s[i-1]==s[i]?1.0:0.0); 
      } 
      for(int j=0;j1;j++) 
      { 
        if(s[j]=='?') 
        { 
          dp[j][i]=dp[j+1][i-1]*1.0/26.0; 
        } 
        else 
        { 
          dp[j][i]=dp[j+1][i-1]*(s[i]==s[j]?1.0:0.0); 
        } 
      } 
    } 
    } 
    double ret=0.0; 
    for(int i=0;ifor(int j=i;jreturn ret; 
  } 
};

challenge phase 無理なものは無理です

systest 通る、Easyがそこそこ速かったので順位が良い(151位)

Rating 1866->1913(+47) やったぜ(勝利)

Codeforces

A:

にぶたんやるだけ。だがちょっと考えるとにぶたんいらなくて草

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
//これは、頭が悪く競プロが世界で一番できないHIR180が
//IOI2014日本代表になるまでのN日間の記録である。
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
#define s second
#define rep(i,x) for(int i=0;i
int num[105];
int n;
bool ok(int x)
{
	priority_queue<int>que;
	for(int i=0;iif(num[i]) que.push(num[i]);
	}
	for(int i=x;iif(que.empty()) return false;

			int a=que.top();  que.pop();
			a=min(a-1,num[i]);
			if(a) que.push(a);
	}
	return true;
}
int main()
{
	srand((unsigned int)time(NULL));
	scanf("%d",&n);
	for(int i=0;i"%d",&num[i]);
	}
	sort(num,num+n,greater<int>());
	//(lb,ub]
	int lb=0,ub=n+5;
	while(ub-lb>1)
	{
		int mid=(lb+ub)>>1;
		if(ok(mid)) ub=mid;
		else lb=mid;
	}
	printf("%d\n",ub);
}

B:

x^2,x^3,x^4,x^5,x^6の形をあらわせる数の和で表す中で

もっとも頂点が少ないもので構築する。

実はめっちゃ多くのケースを試すと落ちます(たとえばk=989426153など)

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
//これは、頭が悪く競プロが世界で一番できないHIR180が
//IOI2014日本代表になるまでのN日間の記録である。
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define f first
#define s second
#define rep(i,x) for(int i=0;i
int cnt[40005],sum=0;
int val=-1;
bool ex[2005][2005]={};
pair<int,vector<int> > gen(ll val)
{
	vector<int>a6,a5,a4,a3,a2;
	int va[7]={};
	vectorint> >ret;
	ll _val=val;
	for(int i=100;i>=1;i--)
	{
		ll x=1LL*i;
		x=x*x*x*x*x*x;
		if(x>val) continue;
		while(val>=x)
		{
			a6.pb(i);
			va[6]+=i*6;
			val-=x;
		}
	}
	val=_val;
	for(int i=100;i>=1;i--)
	{
		ll x=1LL*i;
		x=x*x*x*x*x;
		if(x>val) continue;
		while(val>=x)
		{
			a5.pb(i);
			va[5]+=i*5;
			val-=x;
		}
	}
	val=_val;
	for(int i=300;i>=1;i--)
	{
		ll x=1LL*i;
		x=x*x*x*x;
		if(x>val) continue;
		while(val>=x)
		{
			a4.pb(i);
			va[4]+=i*4;
			val-=x;
		}
	}
	val=_val;
	for(int i=1000;i>=1;i--)
	{
		ll x=1LL*i;
		x=x*x*x;
		if(x>val) continue;
		while(val>=x)
		{
			a3.pb(i);
			va[3]+=i*3;
			val-=x;
		}
	}
	val=_val;
	for(int i=40000;i>=1;i--)
	{
		ll x=1LL*i;
		x=x*x;
		if(x>val) continue;
		while(val>=x)
		{
			a2.pb(i);
			va[2]+=i*2;
			val-=x;
		}
	}
	int x=min((int)va[2],min((int)va[3],min((int)va[4],min((int)va[5],(int)va[6]))));
	if(va[2]==x) return mp(2,a2);
	if(va[3]==x) return mp(3,a3);
	if(va[4]==x) return mp(4,a4);
	if(va[5]==x) return mp(5,a5);
	if(va[6]==x) return mp(6,a6);
}
int main()
{
	srand((unsigned int)time(NULL));
	int k; scanf("%d",&k);
	int _k=k;
	for(int i=2;i*i<=k;i++)
	{
		if(_k%i==0)
		{
			while(_k%i==0)
			{
				cnt[i]++;
				_k/=i;
			}
		}
	}
	pair<int,vector<int> >vec3;
	int id=3;
	vector
vec2;
	if(_k>1) val=_k;
	else goto nxt;
	vec3=gen(val);
	for(int i=vec3.f;i<=vec3.f;i++)
	{
		vector<int>vi=vec3.s;
		for(int j=0;jint lb=1,ub=1;
			for(int d=0;dfor(int k=0;kfor(int s=lb;s<=ub;s++)
				{
					ex[s][id+k]=ex[id+k][s]=true;
				}
			}
			lb=id; ub=id+vi[j]-1; id+=vi[j];
			}
			vec2.pb(mp(lb,ub));
		}
	}
	for(int i=0;ifor(int j=vec2[i].f;j<=vec2[i].s;j++)
		{
			ex[j][id]=ex[id][j]=true;
		}
	}
	 nxt:;
	if(id==3) ex[1][3]=ex[3][1]=true;
	for(int i=2;i*i<=k;i++)
	{
		if(cnt[i])
		{
			vec2.clear();
			int x=1;
			for(int j=1;j<=cnt[i];j++) x*=i; 
			vec3=gen(x); 
			int d=id++;
			for(int i=vec3.f;i<=vec3.f;i++)
			{
				vector<int>vi=vec3.s; 
				for(int j=0;jint lb=d,ub=d;
					for(int d=0;dfor(int k=0;kfor(int s=lb;s<=ub;s++)
						{
							ex[s][id+k]=ex[id+k][s]=true;
						}
					}
					lb=id; ub=id+vi[j]-1; id+=vi[j];
					}
					vec2.pb(mp(lb,ub));
				}
			}
			for(int i=0;ifor(int j=vec2[i].f;j<=vec2[i].s;j++)
				{
					ex[j][id]=ex[id][j]=true;
				}
			}
			
		}
	}
	ex[id][2]=ex[2][id]=true;
	printf("%d\n",id);
	for(int i=1;i<=id;i++)
	{
		for(int j=1;j<=id;j++)
		{
			printf("%c",ex[i][j]?'Y':'N');
		}
		puts("");
	}
}

systest 通る、がまったくうれしくない

Rating 1938->1881(-57)

紫(大絶望)

(コンテスト後)

C:

よくよく考えると、このゲームはzero-sumなので

Jiroの最大化=Cielの最小化であり

そういう目線で見ればJiroが

「Cielは彼女にとって最善のpileを選んでいるのだから、それを邪魔しよう」

と考えるのは自明。よってやるだけ。

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define pb push_back
int main()
{
	int n; scanf("%d",&n);
	int reta=0,retb=0;
	multiset<int,greater<int> >se;
	for(int i=1;i<=n;i++)
	{
		int x; scanf("%d",&x);
		vector<int>vec;
		for(int j=0;jint a;  scanf("%d",&a);
			vec.pb(a);
		}
		for(int i=0;i2;i++) reta+=vec[i];
		for(int i=x-x/2;iif(x/2!=x-x/2) se.insert(vec[x/2]);
	}
	int cnt=0;
	for(multiset<int,greater<int> >::iterator it=se.begin();it!=se.end();++it,++cnt)
	{
		if(cnt%2==0) reta+=*it;
		else retb+=*it;
	}
	printf("%d %d\n",reta,retb);
}

こういうgreedy苦手なのでこの世から消し去られるべき