2013-11-25

■ codeforces Round #214 Div2 Only 23:13

約2ヶ月ぶりのCFでした。

{参加するつもりはなかったのですが、学校の課題が面倒でついついやってしまいました()}

開始10分後くらいにEを開く。

見るからにマンハッタン距離で、それなら45度回転しかないよね、と思ったら

通ってしまって闇でした(ちなみにsecond acceptance)

次にCをみる。どう見てもsum(a)-sum(b)*kと何番目まで見たかをもつDPに見える。

sum(a)-sum(b)*kは-10000以上10000以下のみ考えれば良いので

下駄をはかせて適当に処理すると通る。

次はA。英文読解の問題なので略。

Bは足して最小値をとるだけです。

で、Dを見たのですが分からなかったので寝ました。

~結果~

ooo-o +0/-0 29th

実はCFの過去最高に近い結果でした。

夏休み以降競プロから離れてたけど意外と前より強くなっているのかもしれない...?

最後にコードを(いずれもそれなりに短くかけて嬉しい)

E:

#include 
#include 
#include 
using namespace std;
int p[10][2],g[10][2];
int n,m,k,s;
int main()
{
	cin >> n >> m >> k >> s;
	for(int i=0;i<10;i++)
	{
		p[i][0]=g[i][0]=100000;
		p[i][1]=g[i][1]=-100000;
	}
	
	for(int i=0;ifor(int j=0;jint x;
			cin >> x;
			int f=i+j;
			int h=i-j;
			p[i][0]=min(p[i][0],f);
			p[i][1]=max(p[i][1],f);
			g[i][0]=min(g[i][0],h);
			g[i][1]=max(g[i][1],h);
		}
	}
	int ret=0;
	int rev=-1;
	for(int i=0;iint f; cin >> f;
		if(rev==-1){ rev=f; continue;}
		ret=max(ret,p[rev][1]-p[f][0]);
		ret=max(ret,p[f][1]-p[rev][0]);
		ret=max(ret,g[rev][1]-g[f][0]);
		ret=max(ret,g[f][1]-g[rev][0]);
		
		rev=f;
	}

	cout << ret << endl;
}

C:

#include 
#include 
#include 
using namespace std;
int dp[105][20005];
int a[105],b[105];
int n,k;
#define geta 10000
int main()
{
	cin >> n >> k;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=n;i++) cin >> b[i];
	for(int i=0;i<105;i++)for(int j=0;j<20005;j++)dp[i][j]=-1000000;
	dp[0][geta]=0;
	for(int i=0;ifor(int j=0;j<=20000;j++)
		{
			dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
			int f=a[i+1]-b[i+1]*k;
			if(j+f<=20000 && j+f>=0) dp[i+1][j+f]=max(dp[i+1][j+f],a[i+1]+dp[i][j]);
		}
	}
	
	cout << (dp[n][geta]<=0?-1:dp[n][geta]) << endl;
}

A:

#include 
#include 
#include 
using namespace std;
int n;
int main()
{
	cin >> n;
	for(int i=0;i<4;i++)
	{
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		if(min(a,b)+min(c,d)<=n)
		{
			cout << i+1 << " " << min(a,b) << " " << n-min(a,b) << endl;
			return 0;
		}
	}
	puts("-1");
}

B:

#include 
#include 
#include 
using namespace std;
int n,k;
int val[100005]={};
int main()
{
	cin >> n >> k;
	for(int i=0;iint x;
		cin >> x;
		val[i%k]+=x;
	}
	int mi=1000000;
	int idx;
	for(int i=0;iif(mi>val[i]) idx=i+1;
	}
	cout << idx << endl;
}

ツイートする