tozangezan's diary

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

Ritsumeikan University Programming Camp 2012 (Day 1)

ここ最近やたらとコンテストが多いですね。まいってます。
RUPC2012っぽいものがあったので参加。nya_wolvesでした。id:snukeと二人でチームで参加しました。

A: K Cards
全部試せる。しっかり一発ACしてFAもらう。

#include<stdio.h>
#include<algorithm>
using namespace std;
int d[100];
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a+b){
		for(int i=0;i<a;i++)scanf("%d",d+i);
		int now=0;
		int p=1;
		for(int i=0;i<b-1;i++){
			p*=d[i];
		}
		for(int i=b-1;i<a;i++){
			p*=d[i];
			now=max(now,p);
			p/=d[i-b+1];
		}
		int S=0;
		for(int i=0;i<a;i++){
			for(int j=i+1;j<a;j++){
				int c=d[i];
				d[i]=d[j];
				d[j]=c;
				p=1;
		for(int k=0;k<b-1;k++){
			p*=d[k];
		}
		for(int k=b-1;k<a;k++){
			p*=d[k];
			S=max(S,p);
			p/=d[k-b+1];
		}
				c=d[i];
				d[i]=d[j];
				d[j]=c;
			}
		}
		if(S>=now)printf("%d\n",S-now);
		else printf("NO GAME\n");
	}
}

B: Spellcasters
snukeが解いてたので読んでない

C: Live Schedule
面倒なだけのDPをする。それでも[]ですんだのでまだいいほう。FAでした。

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[31][51][6];
int s[15][30];
int t[15][30];
int main(){
	int a,b,c,d;
	while(scanf("%d%d%d%d",&a,&b,&c,&d),a+b+c+d){
		for(int i=0;i<a;i++)
			for(int j=0;j<b;j++)
				scanf("%d",&s[i][j]);
		for(int i=0;i<a;i++)
			for(int j=0;j<b;j++)
				scanf("%d",&t[i][j]);
		for(int i=0;i<31;i++)
				for(int k=0;k<51;k++)
					for(int l=0;l<6;l++)
						dp[i][k][l]=-99999999;
		dp[0][0][0]=0;
		for(int i=0;i<b;i++){
			for(int j=0;j<=c;j++){
				for(int k=0;k<=d;k++){
					dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]);
					for(int l=0;l<a;l++){
						if(s[l][i]==0)continue;
						int cost=0;
						int W=0;
						for(int m=l;m<a;m++){
							if(s[m][i]==0)break;
							if(k==d&&l!=m)break;
							cost+=t[m][i];
							W+=s[m][i];
							if(l==m&&j+cost<=c){
								dp[i+1][j+cost][k]=max(dp[i+1][j+cost][k],dp[i][j][k]+W);
							}
							if(l!=m&&j+cost<=c&&k<d){
								dp[i+1][j+cost][k+1]=max(dp[i+1][j+cost][k+1],dp[i][j][k]+W);
							}
						}
					}
				}
			}
		}
		int ret=0;
		for(int i=0;i<51;i++)
			for(int j=0;j<6;j++)
				ret=max(ret,dp[b][i][j]);
		printf("%d\n",ret);
	}
}

D: Dimensional Analysis
四則演算の構文解析をしつつ変な処理もする。四則演算の構文解析したことなかったけど大量にかいたらまあなんとかなった。文字列オーラをすごく感じるものはいつもどおりJavaで。

import java.util.*;
class Main{
	static int[][] dim;
	static HashMap<String,Integer> map;
	static String fact;
	static int[]dame;
	static int[] solve(int a,int b){
		int kakko=0;
		int last=0;
		int N[][]=new int[100][dim[0].length];
		int K[]=new int[100];
		int at=0;
		String q="";
		for(int i=a;i<b;i++){
			if(fact.charAt(i)=='('){
				if(kakko==0)last=i;
				kakko++;
			}else if(fact.charAt(i)==')'){
				kakko--;
				if(kakko==0){
					N[at]=solve(last+1,i);
					if(N[at][0]==-99999999)return dame;
				}
			}else if(kakko==0){
				if(fact.charAt(i)=='+'){
		//	System.out.println(q);
					if(q.length()>0){
						N[at]=dim[map.get(q)];
					}
					K[at++]=1;
					q="";
				}
				else if(fact.charAt(i)=='-'){
		//	System.out.println(q);
					if(q.length()>0){
						N[at]=dim[map.get(q)];
					}
					K[at++]=2;
					q="";
				}
				else if(fact.charAt(i)=='*'){
	//		System.out.println(q);
					if(q.length()>0){
						N[at]=dim[map.get(q)];
					}
					K[at++]=3;
					q="";
				}
				else if(fact.charAt(i)=='/'){
		//	System.out.println(q);
					if(q.length()>0){
						N[at]=dim[map.get(q)];
					}
					K[at++]=4;
					q="";
				}else{
					q+=fact.charAt(i);
				}
			}
		}
		boolean OK=true;
	//	System.out.println(q);
		if(q.length()>0)N[at]=dim[map.get(q)];
		int []now=new int[dim[0].length];
		int []val=new int[dim[0].length];
		for(int i=0;i<dim[0].length;i++)now[i]=N[0][i];
		int Last=0;
	//	System.out.println(a+" "+b);
	//	System.out.println(Arrays.toString(now));
		for(int i=0;i<at;i++){
			if(K[i]<3&&Last>0){
				for(int j=0;j<dim[0].length;j++){
					if(now[j]!=val[j])return dame;
					now[j]=N[i+1][j];
				}
	//	System.out.println(i+" "+K[i]+" "+Arrays.toString(now));
			}else if(K[i]<3){
				for(int j=0;j<dim[0].length;j++){
					val[j]=now[j];
					now[j]=N[i+1][j];
				}
	//	System.out.println(i+" "+K[i]+" "+Arrays.toString(now));
				Last=1;
			}else if(K[i]==3){
				for(int j=0;j<dim[0].length;j++)now[j]+=N[i+1][j];
	//	System.out.println(i+" "+K[i]+" "+Arrays.toString(now));
			}else{
				for(int j=0;j<dim[0].length;j++)now[j]-=N[i+1][j];
	//	System.out.println(i+" "+K[i]+" "+Arrays.toString(now));
			}
		}
		if(Last>0){
	//	System.out.println(Arrays.toString(now));
			for(int j=0;j<dim[0].length;j++){
				if(now[j]!=val[j])return dame;
			}
		}else{
	//	System.out.println(Arrays.toString(now));
			for(int j=0;j<dim[0].length;j++){
				val[j]=now[j];
			}
		}
		return val;
	}
	public static void main(String[] args){
		Scanner s=new Scanner(System.in);
		while(s.hasNext()){
			int a=s.nextInt();
			int b=s.nextInt();
			int c=s.nextInt();
			if(a+b+c==0)System.exit(0);
			dim=new int[b][a];
			dame=new int[a];
			dame[0]=-99999999;
			String name[]=new String[b];
			for(int i=0;i<b;i++){
				name[i]=s.next();
				for(int j=0;j<a;j++)dim[i][j]=s.nextInt();
			}
			fact=s.next();
			map=new HashMap<String,Integer>();
			for(int i=0;i<c;i++){
				String v=s.next();
				String w=s.next();
				for(int j=0;j<b;j++){
					if(name[j].equals(w)){
						map.put(v,j);
					}
				}
			}
			int []ans=solve(0,fact.length());
	//		for(int i=0;i<ans.length;i++)System.out.print(ans[i]+" ");
			if(ans[0]==-99999999){
				System.out.println("error");
			}else{
				boolean OK=false;
				for(int i=b-1;i>=0;i--){
					boolean ok=true;
					for(int j=0;j<a;j++)if(ans[j]!=dim[i][j])ok=false;
					if(ok){
						System.out.println(name[i]);
						OK=true;
						break;
					}
				}
				if(!OK)System.out.println("undefined");
			}
		}
	}
}

E: School Excursion

問題よく読んでないけど最小費用流らしい。snukeが解いてた。みんな最小費用流ライブラリもってないらしい。

F: Strawberry Cake

たるい幾何。CTPCのとき以来に見える面倒そうな幾何。(実は昨日あたりJOIのNightman解いてましたが。)
方針としては
まず原点と各頂点を通る直線の傾きを全部求めて
それらをソートして、すると範囲が生まれるので(当然、±∞っぽいものも無いといけません)
このy=mx(hoge<=m<=piyo)のmの範囲について処理すればいいということになります。
なんとなく二つに分けられる多角形の面積の差の絶対値は凸関数になるのでは?という仮定の下mで三分探索。
三分探索では毎回多角形と直線の交点を求めて面積を求めましたが、何とかとおりました。
なにしろ時間がぜんぜんなくてもうこれ適当に書いてなんとかなりゃいいや!みたいな感じでコンパイル通ってからテストケース1回で通った(っぽくみえる)状態になり、そのまま適当に送ったら一発ACもらえたのがなんとも運がよかったのかもしれないし、他の人もやたらとAC率高かったので単に通しやすい誤差設定だったのかもしれない。
でもさっきのあれの凸仮定は正しいと思うんですがどうなんでしょう。

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
double x[20],y[20];
double t[20];
double S=0;
int n;
double Abs(double a){return a<0.0?-a:a;}
double f(double m){
	int count=-1;
	double oneX=0;
	double oneY=0;
	for(int i=0;i<n;i++){
		int v=(i+1)%n;
		if(x[i]!=x[v]){
			double Y=m*x[i];
			if(min(y[i],y[v])<Y&&Y<max(y[i],y[v])){
				if(~count){
					double V=0;
					for(int j=count+1;j<i;j++){
						V+=x[j]*y[j+1]-x[j+1]*y[j];
					}
					V+=x[count+1]*oneY-oneX*y[count+1];
					V+=x[i]*Y-x[i]*x[i];
					V=Abs(V)/2;
					return -Abs(S-V-V);
				}else{
					count=i;
					oneX=x[i];
					oneY=Y;
				}
			}
		}else{
			if((y[i]-y[v])/(x[i]-x[v])!=m){
				double X=(x[i]*((y[v]-y[i])/(x[v]-x[i]))+y[i])/(m-(y[v]-y[i])/(x[v]-x[i]));
				double Y=m*X;
				if(min(x[i],x[v])<X&&X<max(x[i],x[v])){
					if(~count){
						double V=0;
						for(int j=count+1;j<i;j++){
							V+=x[j]*y[j+1]-x[j+1]*y[j];
						}
						V+=x[count+1]*oneY-oneX*y[count+1];
						V+=x[i]*Y-X*x[i];
						V=Abs(V)/2;
						return -Abs(S-V-V);
					}else{
						count=i;
						oneX=X;
						oneY=Y;
					}
				}
			}
		}
	}
}

int main(){
	int a;
	while(scanf("%d",&a),a){
		n=a;
		for(int i=0;i<a;i++)scanf("%lf%lf",x+i,y+i);
		for(int i=0;i<a;i++){
			S+=x[i]*y[(i+1)%a]-x[(i+1)%a]*y[i];
		}
		int now=0;
		S=Abs(S)/2;
		for(int i=0;i<a;i++){
			if(Abs(x[i])>0.00001)t[now++]=y[i]/x[i];
		}
		t[now++]=9999999999999.99999;
		t[now++]=-9999999999999.99999;
		std::sort(t,t+now);
		for(int i=0;i<now;i++){
			double L=t[i];
			double R=t[i+1];
			for(int j=0;j<100;j++){
				double p1=(L*2+R)/3;
				double p2=(L+R*2)/3;
				if (f(p1) > f(p2)){
					R = p2;
				} else {
					L = p1;
				}
			}
			if(f(L)>-0.000000001||f(R)>-0.000000001){
				printf("%.15f %.15f\n",2.0,2.0*L);
				break;
			}
		}
	}
}

G: Sports Days

さすがにわからない。

Result
なぜか1位でした。いろんな大会含めて優勝はPCK2011以来。まあこういう強い人たちがいるなかで優勝できたのは、運とチームでやったこともあるでしょうが、自信にはならなくもないかな、うん、どうだろうね、まあFA2個も出せたのは嬉しいね、
簡単に言えばpnsnkですね。