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少年をしすぎ。