Codeforces #138

Codeforces #138(Div 1)の参加記。

  • コンテストが始まる。A読む。苦手な類の文字列操作。
  • わからない。
  • とりあえずわかった気になって書く。
  • バグる。どうしようもないことに気付く。
  • とりあえずあきらめてB読む。
  • すごく楽しそう。これは解きたい。
  • 5分くらいで思いつく。尺取&各文字についてimos法でいける。
  • pretestとおる。
  • C読む。
  • ん？combinationを順番に求めていくだけじゃ...
  • 10^9+2000>1000000007に気付いて一瞬焦る。
  • でも分母にはそんなのは来ないから大丈夫だよね->実装する
  • 動く。出す。
  • Wrong answer on pretest 9
  • modを一か所取り忘れている。
  • pretest通る。
  • Aはわからないのでhackに逃げる。
  • hackしようと思ったものの落ちそうなケースとか思いつかない。
  • D,Eがこの時点で誰にも解かれていない。やばすぎる。
  • でもA解けないのでD読む。幾何だ。やめよう。
  • E読む。明らかにやばい。
  • Aに戻って考える。
  • コードを複雑にする作業を繰り返すといい感じになる。
  • Wrong answer on pretest 4
  • バグ見つける。
  • Wrong answer on pretest 11
  • バグ見つける。
  • Wrong answer on pretest 11
  • 諦めphase
  • コンテスト終了
  • systestちゃんと通る。


結果、BCを解くのがある程度速かったようで80位だった。Div1過去最高順位なのでうれしい。
個人的にBはすごく良問だと思う。
結局DEは解かれなかった。やばい。
rating: 1722->1843(+121). highest.わーい。

難易度は明らかにC

#include<stdio.h>
#include<vector>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
int imo[26][200001];
int main()
{
	string str,mok;
	cin>>str>>mok;
	for(int i=0;i<26;i++)
	{
		for(int j=0;j<str.size()+1;j++)
		{
			imo[i][j]=0;
		}
	}
	int pt=0;
	for(int i=0;i<mok.size();i++)
	{
		for(;;)
		{
			if(pt>=str.size())
			{
				printf("No\n");
				return 0;
			}
			if(str[pt]==mok[i])
			{
				imo[str[pt]-'a'][pt]++;
				pt++;
				break;
			}
			pt++;
		}
	}
	pt=str.size()-1;
	for(int i=mok.size()-1;i>=0;i--)
	{
		for(;;)
		{
			if(pt<0)
			{
				printf("No\n");
				return 0;
			}
			if(str[pt]==mok[i])
			{
				imo[str[pt]-'a'][pt+1]--;
				pt--;
				break;
			}
			pt--;
		}
	}
	for(int i=0;i<26;i++)
	{
		for(int j=1;j<=str.size();j++)
		{
			imo[i][j]+=imo[i][j-1];
		}
	}
	bool han=true;
	for(int i=0;i<str.size();i++)
	{
		if(imo[str[i]-'a'][i]<=0)
		{
			han=false;
		}
	}
	if(han)
	{
		printf("Yes\n");
	}
	else
	{
		printf("No\n");
	}
}

C

#include<stdio.h>
#include"stdafx.h"
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod=1000000007;
ll po(ll a,ll b)
{
	vector<int>vec;
	for(;;)
	{
		if(b==0)
		{
			break;
		}
		vec.push_back(b%2);
		b/=2;
	}
	reverse(vec.begin(),vec.end());
	ll ret=1;
	for(int i=0;i<vec.size();i++)
	{
		ret*=ret;
		ret%=mod;
		if(vec[i])
		{
			ret*=a;
			ret%=mod;
		}
	}
	return ret;
}
ll inv(ll a)
{
	return po(a,mod-2);
}
int main()
{
	int num,kai;
	scanf("%d%d",&num,&kai);
	kai--;
	vector<ll>vec;
	for(int i=0;i<num;i++)
	{
		ll zan;
		scanf("%I64d",&zan);
		vec.push_back(zan);
	}
	vector<ll>tims;
	tims.push_back(1);
	ll now=1;
	for(int i=1;i<num;i++)
	{
		now*=(kai+i);
		now%=mod;
		now*=inv(i);
		now%=mod;
		tims.push_back(now);
	}
	vector<ll>ret;
	for(int i=0;i<num;i++)
	{
		ll sum=0;
		for(int j=i;j>=0;j--)
		{
			sum+=(tims[j]*vec[i-j])%mod;
			sum%=mod;
		}
		if(i!=0)
		{
			printf(" ");
		}
		printf("%I64d",sum);
	}
	printf("\n");
}