AtCoder ARC #007 - kmjp's blog

ARC007はリアルタイム参加できなかったので、後日練習しました。
なんとか4問解けた。
問題はこちら：http://arc007.contest.atcoder.jp/assignments

A 帰ってきた器物損壊！高橋君

１文字と文字列が与えられるので、最初の１文字以外を出力する。
これは特に考えず完了。

char key[10];
char str[100];

void solve() {
	
	ZERO(key);
	ZERO(str);
	GETs(key);
	GETs(str);
	
	char* p = str;
	while(*p) {
		if(*p != key[0]) _P("%c",*p);
		p++;
	}
	_P("\n");
}

B 迷子のCDケース

対象のCD(nu[j])と、今外にあるCD(nc)を交換するという作業を繰り返す。

int N,M;
int nu[101];

void solve() {
	int m,d,i,j;
	int vx,vy,nc;
	
	GET2(&N,&M);
	int c=0;
	FOR(i,N) nu[i]=i+1;
	
	FOR(i,M) {
		nc = GETi();
		if(nc==c) continue;
		FOR(j,N) {
			if(nu[j]==nc) {
				nu[j]=c;
				c=nc;
				break;
			}
		}
	}
	
	FOR(i,N) _P("%d\n",nu[i]);
}

C 節約生活

最大10個しか時間の長さが無いので、各10個の時間それぞれでTVを付け始めたとき、常時TVを見られるか2^10通り列挙した。
「全てのテレビを点けてからは～～」などの前提条件がややこしいので、最初にoが先頭に来るよう文字列をローテートしています。

char str[100];
int bitcount(int n) {
	int i=0;
	while(n>0) {i += n%2; n>>=1;}
	return i;
}

void solve() {
	int m,d,i,w,j;
	int ns=0;
	int s[100];
	int sl;
	int val,goal,min,pat;
	
	GETs(str);
	sl=strlen(str);
	
	while(*str=='x') {
		FOR(i,sl-1) str[i]=str[i+1];
		str[sl-1]='x';
	}
	val=0;
	FOR(i,sl) if(str[i]=='o') val |= 1<<i;
	goal = (1<<sl)-1;
	min = 999;
	FOR(pat,1<<sl) {
		int tv = bitcount(pat);
		if(tv>min) continue;
		
		int t=0;
		FOR(i,sl) {
			if(pat & (1<<i)) t |= (val<<i) | ((val<<i)>>sl);
		}
		
		if((t & goal)==goal) min=tv;
	}
	
	_P("%d\n",min);
}

D 破れた宿題

等差数列の部分文字列から、初項と公差を求める問題。
最初初項と公差を頑張って求めようとしたけど、初項はすぐに求まることが分かった。
というのも、初項は最初の１ケタで確定する。というのも公差を大きく取れば、残りの文字列の数値にできるから。
先頭が０の時だけは注意で、頭に１を付けて、先頭にあるだけの０を付けたのものが初項になる。

残りの文字列の長さを見て、残りが２項目だけか３項目以降も入るか見ている。
３項目以降もありそうな場合、考えられる２項目を全部列挙して、それぞれ３項目以降がちゃんと等差数列になっているか確認している。

実際は、３項目以降もあるパターンは早期に実装できたけど２項目止まりのパターンでコーナーケースが多く正解まで８回もミスってしまった。
今回多倍長演算があるのでPerlで実装。use bigintを行うと整数が勝手に多倍長になるので楽だが、なんか一部小数になるとdoubleの範囲外(10^308以上)になったときオーバーフローして困った。

#!/usr/bin/perl

use Data::Dumper;
use bigint;

while(<>) {
	chomp;
	solve($_);
}

sub solve {
	my $vl = $_[0];
	$fl=1;
	if(substr($vl,0,1)=='0'){
		$f=1;
	}
	else {
		$f = substr($vl,0,1);
		$vl = substr($vl,1);
	}

	while(length($vl)>0 && substr($vl,0,1)=='0') {
		$f*=10;
		$fl++;
		$vl = substr($vl,1);
	}

	$sl=length($vl);
	if($sl==0) {
		out($f,1);
	}
	elsif($sl<$fl) {
		$up=1;
		while(1) {
			$min=$vl*(10**$up);
			$max=($vl+1)*(10**$up)-1;
			if($min>=$f+1) {out($f,$min-$f); last;}
			if($max>=$f+1) {out($f,1); last;}
			$up++;
		}
	}
	elsif($sl==$fl) {
		if($vl<$f+1){ $vl*=10;};
		out($f,$vl-$f);
	}
	else {
		#探す
		
		for $len(1..(length($vl))) {
			$nv = substr($vl,0,$len);
			$dif = 0+$nv-$f;
			if($dif<1){ next;}
			
			$ok=1;
			$left = substr($vl,$len);
			while(length($left)>0) {
				$nv+=$dif;
				if(length($nv)<=length($left)) {
					$t = 0+substr($left,0,length($nv));
					if($t != $nv){ $ok=0; last;}
					$left=substr($left,length($nv));
				}
				else {
					$nvl = 0+substr($nv,0,length($left));
					if($nvl!=$left){ $ok=0;}
					last;
				}
			}
			if($ok==1) {
				out($f,$dif);
				last;
			}
		}
	}
}

sub out {
	printf "%s %s\n",$_[0],$_[1];
}

まとめ

本番出てたらDは部分点取れたかな…？
本番ではないとはいえ、解き切れたのは良かった。
多倍長演算ではいつも迷うので、Pythonを覚えようかな。