kmjp's blog

競技プログラミング参加記です

AtCoder ARC #010 : A - 名刺交換、B - 超大型連休

ARC#010に参加。Bでしょうもないミスでかなり苦戦したため、結局Dのsmallまでしか行かなかった。
もっとも、今の自分の知識的にDの完答には少しギャップがあったのだが…。
ではまずAとBから。
http://arc010.contest.atcoder.jp/tasks/arc010_1
http://arc010.contest.atcoder.jp/tasks/arc010_2

A - 名刺交換

これは問題文を素直にシミュレートすればよい。
現在持っている名刺がA枚以下ならB枚足し、次の消費量分引く。
途中で名刺がマイナスになったら終了。

int N,M,A,B;

void solve() {
	int f,r,i,j,k,l;
	N=GETi();
	M=GETi();
	A=GETi();
	B=GETi();
	
	FOR(i,M) {
		if(N<=A) N+=B;
		j=GETi();
		N-=j;
		if(N<0) {
			_P("%d\n",i+1);
			return;
		}
	}
	
	_P("complete\n");
	return;
}

B - 超大型連休

祝日一覧が渡されるので、最大の連休数を答える。

これ、問題文が足りないと思うんだけどな…
というのも「2011年から振替休日が2012年に続いている」という前提を勝手においてしまいミス連発した。
「祝日を増やすことにした」だから2011年分の祝日は考慮しない、ということか…?

それは置いておくと、まず土日に休日フラグを立てた上で与えられた祝日に休日フラグを当てていけばよい。
土日と休日がぶつかったら適宜次の日に振替休日を取っていく。
入力された日付の順番は気にする必要はない。

int N;
int bit[367];
int day[]={31,29,31,30,31,30,31,31,30,31,30,31};

int tod(int m,int d) {
	int i;
	FOR(i,m-1) d +=day[i];
	return d-1;
}

void solve() {
	int f,r,i,j,k,l;
	ZERO(bit);
	FOR(i,366) {
		if(i%7==0 || i%7==6) bit[i]=1;
	}
	
	N=GETi();
	FOR(i,N) {
		scanf("%d/%d",&j,&k);
		l=tod(j,k);
		FOR(k,366) {
			if(bit[l]==0) {
				bit[l]=1;
				break;
			}
			l++;
			if(l>=366) break;
		}
	}
	
	int ma=0;
	int cu=0;
	FOR(i,366){
		if(bit[i]) cu++;
		else cu=0;
		ma=max(cu,ma);
	}
	
	_P("%d\n",ma);
}

まとめ

またも問題文にやられている感じ…。