tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

Codeforces Beta Round #63 (Div2 Only)

春休みという流れでCodeforcesにノリで初参加。
TopCoderもあわせて久しぶりのDiv2なので嬉しい気分。

(ちなみに操作のしかたはよくわかりませんでした)

A: Young Physicist
沢山あるベクトル(3次元)の和が0ベクトルになるかどうか判定する。
書くだけ。

#include<stdio.h>
int d[3];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		int e,f,g;
		scanf("%d%d%d",&e,&f,&g);
		d[0]+=e;
		d[1]+=f;
		d[2]+=g;
	}
	if(d[0]==0&&d[1]==0&&d[2]==0)printf("YES\n");
	else printf("NO\n");
}

B: Bets
競技参加している時間帯、ラップタイム、賞金が沢山の競技者についていて、最大でどのくらいのお金がもらえるか(謎)
範囲狭いし時間でループが回せる。書くだけ。

#include<stdio.h>
int l[100];
int r[100];
int t[100];
int c[100];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		scanf("%d%d%d%d",l+i,r+i,t+i,c+i);
	}
	int ret=0;
	for(int i=1;i<=a;i++){
		int at=0;
		bool ok=false;
		int min=9999999;
		for(int j=0;j<b;j++){
			if(l[j]<=i&&i<=r[j]&&min>t[j]){
				at=j;
				ok=true;
				min=t[j];
			}
		}
		if(ok)ret+=c[at];
	}
	printf("%d\n",ret);
}

C: Game
文字列系実装問題? 問題文が理解できないけど、もし考えられるパターンが複数個あったらどうするんだろう…
適当にJavaで提出してみたがpretestで-2されるだけされておわった。

D: Dot
普通に難しいと思う。ビットDPとかかなぁ。

E: Subsegments
どう見ても座標圧縮+SegmentTree安定でした。mapとsetやらpriority_queueやらを使っている人が多かったように見える。

#include<stdio.h>
#include<algorithm>
using namespace std;
int t[100000];
int k[100000];
int zahyou[100000];
int co[100000];
int SEGTREE[262144];
void query(int at,int val){
	if(val==1)SEGTREE[at+131072]=at;
	else SEGTREE[at+131072]=-1;
	at+=131072;
	at/=2;
	while(at>0){
		SEGTREE[at]=max(SEGTREE[2*at],SEGTREE[2*at+1]);
		at/=2;
	}
	return;
}
int find(int begin,int end,int a,int b,int t){
	if(begin<=a&&b<=end)return SEGTREE[t];
	else if(begin>b||end<a)return -1;
	else return max(find(begin,end,a,(a+b)/2,t*2),find(begin,end,(a+b)/2+1,b,t*2+1));
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d",t+i);
		k[i]=t[i];
	}
	std::sort(k,k+a);
	for(int i=0;i<262144;i++)SEGTREE[i]=-1;
	for(int i=0;i<a;i++){
		zahyou[i]=lower_bound(k,k+a,t[i])-k;
	}
	for(int i=0;i<b;i++){
		co[zahyou[i]]++;
	}
	for(int i=0;i<b;i++){
		if(co[zahyou[i]]==1){
			query(zahyou[i],1);
		}
	}
	if(SEGTREE[1]!=-1)
		printf("%d\n",k[SEGTREE[1]]);
		else printf("Nothing\n");
	for(int i=1;i<a-b+1;i++){
		co[zahyou[i-1]]--;
		co[zahyou[i+b-1]]++;
		if(co[zahyou[i-1]]==1)query(zahyou[i-1],1);
		else query(zahyou[i-1],-1);
		if(co[zahyou[i+b-1]]==1)query(zahyou[i+b-1],1);
		else query(zahyou[i+b-1],-1);
		//for(int j=131072;j<131072+a;j++)printf("%d ",SEGTREE[j]);
	if(SEGTREE[1]!=-1)
		printf("%d\n",k[SEGTREE[1]]);
		else printf("Nothing\n");
	}
}

Hack:
面白そうだしCとD書けないしHackでもして遊んでみよう。
とりあえずA,B,Eの全員のソースを眺めてみる。
Aで最後の判定を三つの要素の合計が0とか三つの要素がすべて等しいと判定してる人が沢山! -> +3
他は落とせなさそう。 ->誰かが落としていました

SystemTest:
通った
496 + 956 + 0 + 0 + 2040 + 300 = 3792 (37th)
No rated -> 1760 (+260)

初参加の割りには良かったように思えます。最近のTopCoderと比較すれば。

Div2Onlyじゃない回はどのくらい解けばレート上がるんでしょう。