CodeIQ 「長くなるように、増え続けるように」 解答コード

nagaku_fuetudukeru.c

#include <stdio.h>
#include <string.h>

#define MAX_SEQ_LENGTH 200

/* seqの[s1,e1)が示す数と[s2,e2)が示す数を比較する。
 * 前者が大きければ正の数、後者が大きければ負の数、等しければ0を返す。 */
int cmp_number(const char* seq,int s1,int e1,int s2,int e2) {
	/* リーディングゼロが無ければ、長い数の方が大きい */
	if(e1-s1>e2-s2)return 1;
	if(e1-s1<e2-s2)return -1;
	/* 数を比較する */
	return strncmp(seq+s1,seq+s2,e1-s1);
}

/* 探索を行う。seq=NULLにすると、メモの初期化を行う。 */
int search(const char* seq,int now,int prev_begin) {
	static int memo[MAX_SEQ_LENGTH][MAX_SEQ_LENGTH];
	if(seq==NULL) {
		/* メモの初期化 */
		memset(memo,0,sizeof(memo));
		return 0;
	} else {
		/* 探索 */
		int result=-10000000;
		int i;
		/* 無事最後まで到達していたら、0を返す */
		if(seq[now]=='\0')return 0;
		/* 今見ている文字がゼロなら、リーディングゼロなので数列は作れない */
		if(seq[now]=='0')return result;
		/* メモにあったら、その値を返す */
		if(memo[now][prev_begin]!=0)return memo[now][prev_begin]-1;
		/* 探索を行う */
		for(i=now;seq[i]!='\0';i++) {
			if(cmp_number(seq,prev_begin,now,now,i+1)<0) {
				/* 次の数字の方が大きくなった */
				int now_result=search(seq,i+1,now)+1;
				if(now_result>result)result=now_result;
			}
		}
		/* メモを書き込んで、値を返す */
		memo[now][prev_begin]=result+1;
		return result;
	}
}

int solve(const char* seq) {
	search(NULL,0,0); /* メモを初期化 */
	return search(seq,0,0); /* 探索(メモ化再帰) */
}

int main(void) {
	int first_flag=1;
	char id[100];
	char seq[MAX_SEQ_LENGTH];
	int expected;
	while(scanf("%s%s%d",id,seq,&expected)==3) {
		int answer=solve(seq);
		if(answer!=expected) {
			if(!first_flag)putchar(',');
			printf("%s",id);
			first_flag=0;
			fprintf(stderr,"id=%s expected=%d answer=%d\n",id,expected,answer);
		}
	}
	putchar('\n');
	return 0;
}

nf_make_sample.pl

#!/usr/bin/perl

use strict;

my $input="";
while(<STDIN>){$input.=$_;}

$input =~ s/<tr>.*?<td>([0-9]+)<\/td>.*?<code>([0-9]+)<\/code>.*?<code class=\'expected\'>([0-9]+)<\/code>/&printOneData($1,$2,$3)/seg;

sub printOneData {
	my ($no,$data,$out)=@_;
	print "$no $data $out\n";
	return "";
}