PKU1115: Statistical Trouble

超大作。

時間もメモリも厳しいので、本当にぱない。
やることは入力から表を沢山生成するだけ。
とりあえず6KB書いてサンプルあわせてみたらTLEって出て、原因をがんばって探すもTLEで、ようやく出力がネックになっていることに気がついて、そこで出力をStringBufferに全部書き換えて、今度はMLEしたのでHashMapの配列を普通の配列にするなどして適当にごちゃごちゃやった。ソース汚い。

Time Limit 1000MS Memory Limit 10000KBで
Time 3891MS Memory 9360Kで通った。(Javaだと補正で時間制限は伸びるのだが、それでもぎりぎりの時間である。)

とにかく大変でした。書くのに3時間かかりました。(他の人は一問にもっと時間をかけるというのを聞くのでこわいです)

import java.util.*;
import java.io.*;

class Main{
	public static void main(String[] args) throws IOException{
	//	long sec=System.currentTimeMillis();
		InputStreamReader isr=new InputStreamReader(System.in);
		BufferedReader br=new BufferedReader(isr);
		//Scanner s=new Scanner(System.in);
		String title=br.readLine();
		HashMap<String,Integer> map=new HashMap<String,Integer>();
		String ans[][]=new String[101][128];
		int to[][]=new int[101][128];
		String[] answers=new String[101];
		String[] questionname=new String[101];
		String[] person=new String[5000];
		int [][]data=new int[128][128];
		int[][]p1=new int[128][128];
		int[][]p2=new int[128][128];
		int []right=new int[128];
		int[]bottom=new int[128];
		int pr[]=new int[128];
		int pb[]=new int[128];
		boolean amariR[]=new boolean[128];
		boolean amariB[]=new boolean[128];
		char []c1;
		char[]c2;
		int now=0;
		String line=br.readLine();
		while(true){
			answers[now]="";
			if(line.equals("#"))break;
			questionname[now]=line.substring(4);
			map.put(line.substring(0,3),now);
			while(true){
				line=br.readLine();
				if(line.charAt(0)!=' ')break;
				answers[now]+=line.substring(1,2);
				ans[now][(int)(line.charAt(1))]=line.substring(3);
				to[now][(int)(line.charAt(1))]=answers[now].length()-1;
			}
			now++;
		}
		int per=0;
	//	System.err.println(System.currentTimeMillis()-sec);
		while(true){
			String t=br.readLine();
			if(t.equals("#"))break;
			person[per++]=t;
		}
	//	System.err.println(System.currentTimeMillis()-sec);
		while(true){
			StringBuffer out=new StringBuffer(10000);

			String RE=br.readLine();
			if(RE.equals("#"))break;
			String rowcol[]=RE.split(" ");
			out.append(title+" - "+RE.substring(8)+"\n");
			int at1=map.get(rowcol[0]);
			out.append(rowcol[0]+" "+questionname[at1]+"\n");
			int AT1=answers[at1].length();
			c1=answers[at1].toCharArray();
			for(int i=0;i<AT1;i++){
				out.append(" "+c1[i]+" "+ans[at1][(int)c1[i]]+"\n");
			}
			int at2=map.get(rowcol[1]);
			int AT2=answers[at2].length();
			c2=answers[at2].toCharArray();
			out.append(rowcol[1]+" "+questionname[at2]+"\n");
			for(int i=0;i<AT2;i++){
				out.append(" "+c2[i]+" "+ans[at2][(int)c2[i]]+"\n");
			}
			out.append("\n");
			out.append("      ");
			for(int i=0;i<AT2;i++){
				out.append(" "+rowcol[1]+":"+c2[i]);
			}
			out.append(" TOTAL\n");
			for(int i=0;i<AT1;i++)
				for(int j=0;j<AT2;j++)
					data[i][j]=p1[i][j]=p2[i][j]=0;
			for(int i=0;i<per;i++){
				int one=to[at1][(int)(person[i].charAt(at1))];
				int two=to[at2][(int)(person[i].charAt(at2))];
				/*for(int j=0;j<AT1;j++)if(c1[j]==person[i].charAt(at1)){
					one=j;
					break;
				}
				for(int j=0;j<AT2;j++)if(c2[j]==person[i].charAt(at2)){
					two=j;
					break;
				}*/
				data[one][two]++;
			}
			for(int i=0;i<AT1;i++){
				int mo=0;
				for(int j=0;j<AT2;j++){
					mo+=data[i][j];
				}
				if(mo==0){
					for(int j=0;j<AT2;j++)p1[i][j]=-1;
					continue;
				}
				boolean amari[]=new boolean[AT2];
				int temp=0;
				for(int j=0;j<AT2;j++){
					if(data[i][j]*100%mo==0){
						temp+=p1[i][j]=data[i][j]*100/mo;
					}
					else{
						temp+=p1[i][j]=data[i][j]*100/mo;
						amari[j]=true;
					}
				}
				for(int j=0;j<AT2&&temp<100;j++){
					if(amari[j]){
						temp++;
						p1[i][j]++;
					}
				}
			}

			for(int i=0;i<AT2;i++){
				int mo=0;
				for(int j=0;j<AT1;j++){
					mo+=data[j][i];
				}
				if(mo==0){
					for(int j=0;j<AT1;j++)p2[j][i]=-1;
					continue;
				}
				boolean amari[]=new boolean[AT1];
				int temp=0;
				for(int j=0;j<AT1;j++){
					if(data[j][i]*100%mo==0){
						temp+=p2[j][i]=data[j][i]*100/mo;
					}
					else{
						temp+=p2[j][i]=data[j][i]*100/mo;
						amari[j]=true;
					}
				}
				for(int j=0;j<AT1&&temp<100;j++){
					if(amari[j]){
						temp++;
						p2[j][i]++;
					}
				}
			}
			for(int i=0;i<AT1;i++){
				right[i]=0;
				amariR[i]=false;
				for(int j=0;j<AT2;j++)right[i]+=data[i][j];
			}
			for(int i=0;i<AT2;i++){
				bottom[i]=0;
				amariB[i]=false;
				for(int j=0;j<AT1;j++)bottom[i]+=data[j][i];
			}
			int temp=0;
			for(int i=0;i<AT1;i++){
				temp+=pr[i]=right[i]*100/per;
				if(right[i]*100%per!=0)amariR[i]=true;
			}
			for(int i=0;i<AT1&&temp<100;i++){
				if(amariR[i]){
					pr[i]++;
					temp++;
				}
			}
			temp=0;
			for(int i=0;i<AT2;i++){
				temp+=pb[i]=bottom[i]*100/per;
				if(bottom[i]*100%per!=0)amariB[i]=true;
			}
			for(int i=0;i<AT2&&temp<100;i++){
				if(amariB[i]){
					pb[i]++;
					temp++;
				}
			}
			for(int i=0;i<AT1;i++){
				out.append(" "+rowcol[0]+":"+c1[i]);
				for(int j=0;j<AT2;j++){
					out.append(String.format("%6d",data[i][j]));
				}
				int total=0;
				for(int j=0;j<AT2;j++)total+=data[i][j];
				out.append(String.format("%6d",total));
				out.append("\n      ");
				for(int j=0;j<AT2;j++){
					if(p1[i][j]!=-1){
						out.append(String.format("%5d",p1[i][j]));
						out.append("%");
					}else out.append("     -");
				}
				if(right[i]!=0)out.append("  100%\n      ");
				else out.append("     -\n      ");
				for(int j=0;j<AT2;j++){
					if(p2[i][j]!=-1){
						out.append(String.format("%5d",p2[i][j]));
						out.append("%");
					}else out.append("     -");
				}
				
				out.append(String.format("%5d",pr[i]));
				out.append("%\n");
			}
			out.append(" TOTAL");
			for(int i=0;i<AT2;i++){
				out.append(String.format("%6d",bottom[i]));
			}
			out.append(String.format("%6d\n",per));
			out.append("      ");
			for(int i=0;i<AT2;i++){
				out.append(String.format("%5d",pb[i]));
				out.append("%");
			}
			out.append("  100%\n");
			out.append("      ");
			for(int i=0;i<AT2;i++){
				if(bottom[i]>0)out.append("  100%");
				else out.append("     -");
			}
			out.append("  100%\n\n");
			System.out.print(out);
	//	System.err.println(System.currentTimeMillis()-sec);
		}
	}
}

こういうのまであっさり通すHuziwaraはぱないと思う。みなさん解きましょう。