tozangezan's diary

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

Google Code Jam Japan 決勝

774秒差で負け。

A: 典型DP。もちろんデバッグのほうが時間がかかる

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int dp[1000][1000];
int dat[1000];
int main(){
	int a;
	scanf("%d",&a);
	for(int T=0;T<a;T++){
		int b;
		scanf("%d",&b);
		for(int i=0;i<b;i++){
			scanf("%d",dat+i);
		}
		for(int i=0;i<b;i++)
			for(int j=0;j<b;j++)dp[i][j]=0;
		std::sort(dat,dat+b);
		for(int i=1;i<b;i++){//size
			for(int j=0;j<i;j++){
				if(j<i-1||i==1){
					dp[i][i-1]=max(dp[i][i-1],dp[j][i-1]+dat[j]*dat[i]);
					dp[i-1][i]=max(dp[i-1][i],dp[i-1][j]+dat[j]*dat[i]);
					if(j<i-1||i==1)dp[j][i]=max(dp[j][i],dp[j][i-1]+dat[i-1]*dat[i]);
					if(j<i-1||i==1)dp[i][j]=max(dp[i][j],dp[i-1][j]+dat[i-1]*dat[i]);
				}
			}
		}
		int ret=0;
		for(int i=0;i<b-1;i++){
			ret=max(ret,max(dp[b-1][i]+dat[b-1]*dat[i],dp[i][b-1]+dat[b-1]*dat[i]));
		}
		printf("Case #%d: %.12f\n",T+1,(double)ret*sin(2.0*3.14159265358979323846/b)/2);
	}
}

B:数学らしいが多倍長を使ってSmallに逃げる。

import java.util.*;
import java.math.*;
class Main{
	public static void main(String[] args){
		Scanner s=new Scanner(System.in);
		int t=s.nextInt();
		for(int T=0;T<t;T++){
			int a=s.nextInt();
			int b=s.nextInt();
			int c=s.nextInt();
			if(b==1){
				int ret=1;
				for(int i=0;i<a;i++){
					ret=ret*a%c;
				}
				System.out.printf("Case #%d: %d\n",T+1,ret);
			}else{
				BigInteger bi=new BigInteger("1");
				BigInteger mult=new BigInteger(""+a);
				for(int i=0;i<a;i++){
					bi=bi.multiply(mult);
				}
				BigInteger p=bi.mod(new BigInteger(""+c));
				int q=p.intValue();
				int val=q;
				int ret=1;
				while(bi.compareTo(BigInteger.ZERO)!=0){
					if(bi.mod(new BigInteger("2")).intValue()==1)ret=ret*val%c;
					val=val*val%c;
					bi=bi.divide(new BigInteger("2"));
				}
				System.out.printf("Case #%d: %d\n",T+1,ret);
			}
		}
	}
}

C:smallに逃げようとするが実装多すぎてデバッグ終わらない。害悪

import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner SSS=new Scanner(System.in);
		int t=SSS.nextInt();
		for(int T=0;T<t;T++){
			String a=SSS.next();
			String B=SSS.next();
			if(a.length()<B.length()){
				String c=a;
				a=B;
				B=c;
			}
			String ret=a;
			if(a.compareTo(B)>0)ret=B;
			int AS=99999999;
			for(int i=0;i<(1<<a.length());i++){
				boolean asta=false;
				String b=B;
				String str="";
				for(int j=0;j<a.length();j++){
					if((i&(1<<j))>0){
						if(!asta){
							asta=true;
							str+="*";
						}
					}else{
						asta=false;
						str+=a.charAt(j);
					}
				}
				boolean ok=true;
			//	System.out.println(str);
				for(int j=0;str.charAt(j)!='*';j++){
					if(j>=b.length()||str.charAt(j)!=b.charAt(j)){
						ok=false;
						break;
					}
				}
				for(int j=0;str.charAt(str.length()-1-j)!='*';j++){
					if(j>=b.length()||str.charAt(str.length()-1-j)!=b.charAt(b.length()-1-j)){
						ok=false;
						break;
					}
				}
				String []d=str.split("\\*");
				int r=0;
				for(int j=0;j<d.length;j++)r+=d[j].length();
				if(r>b.length())ok=false;
				if(!ok){
					int s=0;
					for(int j=0;j<str.length();j++)if(str.charAt(j)=='*')s++;
					if(str.length()<ret.length()){
						ret=str;
						AS=s;
					}
					else if(str.length()==ret.length()&&s<AS){
						ret=str;
						AS=s;
					}
					else if(str.length()==ret.length()&&s==AS&&str.compareTo(ret)<0){
						ret=str;
					}
					continue;
				}
		//		System.out.print(b+" "+str+"->");
				
				if(str.charAt(0)!='*')
					b=b.substring(d[0].length());
				
				if(b.length()>0&&str.charAt(str.length()-1)!='*'&&d.length!=1){
					b=b.substring(0,b.length()-d[d.length-1].length());
				}
				
				int now=0;
				for(int j=0;j<d.length;j++){
					if(j==0&&str.charAt(0)!='*')continue;
					if(j==d.length-1&&str.charAt(str.length()-1)!='*')break;
					if(d[j].length()==0)continue;
					boolean find=false;
					for(int k=now;k<b.length()+1-d[j].length();k++){
						boolean OK=true;
						for(int l=0;l<d[j].length();l++){
							if(d[j].charAt(l)!=b.charAt(k+l)){
								OK=false;
								break;
							}
						}
						if(OK){
							find=true;
							now=k+d[j].length();
							break;
						}
					}
					if(!find){
						ok=false;
						break;
					}
				}
				if(!ok){
					int s=0;
					for(int j=0;j<str.length();j++)if(str.charAt(j)=='*')s++;
					if(str.length()<ret.length()){
						ret=str;
						AS=s;
					}
					else if(str.length()==ret.length()&&s<AS){
						ret=str;
						AS=s;
					}
					else if(str.length()==ret.length()&&s==AS&&str.compareTo(ret)<0){
						ret=str;
					}
				}
			}
			
			
			
			
			
			for(int i=0;i<(1<<B.length());i++){
				boolean asta=false;
				String b=a;
				String str="";
				for(int j=0;j<B.length();j++){
					if((i&(1<<j))>0){
						if(!asta){
							asta=true;
							str+="*";
						}
					}else{
						asta=false;
						str+=B.charAt(j);
					}
				}
				boolean ok=true;
				for(int j=0;j<str.length()&&str.charAt(j)!='*';j++){
					if(j>=b.length()||str.charAt(j)!=b.charAt(j)){
						ok=false;
						break;
					}
				}
				for(int j=0;j<str.length()&&str.charAt(str.length()-1-j)!='*';j++){
					if(j>=b.length()||str.charAt(str.length()-1-j)!=b.charAt(b.length()-1-j)){
						ok=false;
						break;
					}
				}
				String []d=str.split("\\*");
				int r=0;
				for(int j=0;j<d.length;j++)r+=d[j].length();
				if(r>b.length())ok=false;
				if(!ok){
					int s=0;
					for(int j=0;j<str.length();j++)if(str.charAt(j)=='*')s++;
					if(str.length()<ret.length()){
						ret=str;
						AS=s;
					}
					else if(str.length()==ret.length()&&s<AS){
						ret=str;
						AS=s;
					}
					else if(str.length()==ret.length()&&s==AS&&str.compareTo(ret)<0){
						ret=str;
					}
					continue;
				}
		//		System.out.print(b+" "+str+"->");
				if(str.charAt(0)!='*')
					b=b.substring(d[0].length());
				
				if(b.length()>0&&str.charAt(str.length()-1)!='*'&&d.length!=1){
					b=b.substring(0,b.length()-d[d.length-1].length());
				}
			//	System.out.println(b+" "+str);
				
				int now=0;
				
				for(int j=0;j<d.length;j++){
					if(j==0&&str.charAt(0)!='*')continue;
					if(j==d.length-1&&str.charAt(str.length()-1)!='*')break;
					if(d[j].length()==0)continue;
					boolean find=false;
					for(int k=now;k<b.length()+1-d[j].length();k++){
						boolean OK=true;
						for(int l=0;l<d[j].length();l++){
							if(d[j].charAt(l)!=b.charAt(k+l)){
								OK=false;
								break;
							}
						}
						if(OK){
							find=true;
							now=k+d[j].length();
							break;
						}
					}
					if(!find){
						ok=false;
						break;
					}
				}
				if(!ok){
					int s=0;
					for(int j=0;j<str.length();j++)if(str.charAt(j)=='*')s++;
					if(str.length()<ret.length()){
						ret=str;
						AS=s;
					}
					else if(str.length()==ret.length()&&s<AS){
						ret=str;
						AS=s;
					}
					else if(str.length()==ret.length()&&s==AS&&str.compareTo(ret)<0){
						ret=str;
					}
				}
			}
			
			System.out.println("Case #"+(T+1)+": "+ret);
		}
	}
}

result:

score:0
time:+12:54
rank:+3

負け。最近WA少年をしすぎ。