tozangezan's diary

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

SRM 483 Div2

なぜか起きられました。

250:DigitHoles
やるだけ。夜補正であること以外は問題なし。

public class DigitHoles{
	public int numHoles(int a){
		String b=String.valueOf(a);
		int ret=0;
		for(int i=0;i<b.length();i++){
			switch(b.charAt(i)){
				case '0':
				case '4':
				case '6':
				case '9':
					 ret++;
					 break;
				case '8':
					ret+=2;
					break;
			}
		}
		return ret;
	}
}

500:MovieSeating
順列計算の問題。
しかしなぜか1,{"."}というコーナーケースが。いつもどおりResubmit。でも380点くらいとれた

public class MovieSeating{
	public long P(int a,int b){
		long ret=1;
		long A=a;
		for(int i=0;i<b;i++){
			ret*=(A-i);
		}
		return ret;
	}
	public long getSeatings(int a,String[] b){
		long ret=0;
		for(int i=0;i<b.length;i++){
			int now=0;
			for(int j=0;j<b[i].length();j++){
				if(b[i].charAt(j)=='.')now++;
			}
			ret+=P(now,a);
		}
		if(a>1)
		for(int i=0;i<b[0].length();i++){
			int now=0;
			for(int j=0;j<b.length;j++)
			{
				if(b[j].charAt(i)=='.')now++;
			}
			ret+=P(now,a);
		}
		return ret;
	}
}

1000:BestApproximationDiv2
問題文が1000のわりに分かりやすい。そしてなぜか自分の目にはやるだけ問題にみえた。
BigDecimalを使ってみる。そして普通に計算させる。
おっと、TLEしたぞwww →分母、分子が両方偶数のときを探索しない
これで間に合った(1.7sec?)
どうやら本来は2分探索で解くらしいけど、そんなの思いつくほうがおかしいと思う。というかなんでBigDecimal使ってる人1人しかいなかったんだろう…

import java.math.*;

public class BestApproximationDiv2{
	public String findFraction(int a,String b){
		BigDecimal bd=new BigDecimal(b);
		int max=0;
		int maxBUNPO=0;
		int maxBUNSHI=0;
		for(int i=1;i<=a;i++){
			int ok=0;
			BigDecimal bunshiDAI=new BigDecimal(ok=bd.multiply(new BigDecimal(i)).intValue()).setScale(50).divide(new BigDecimal(i),BigDecimal.ROUND_DOWN);
			if(i%2==0&&ok%2==1){
					String takeshi=bunshiDAI.toPlainString();
								int sames=1;
			for(int j=2;j<Math.min(takeshi.length(),b.length());j++){
				if(takeshi.charAt(j)==b.charAt(j))sames++;
				else break;
			}
			if(sames>max){
				max=sames;
				maxBUNPO=i;
				maxBUNSHI=bd.multiply(new BigDecimal(i)).intValue();
			}
			}else {
			
			
			BigDecimal bunshiSHOU=new BigDecimal(ok+1).setScale(50).divide(new BigDecimal(i),BigDecimal.ROUND_DOWN);
		
			/*BigDecimal nextDAI=new BigDecimal(1.0);
			nextDAI=nextDAI.setScale(50);
			nextDAI=bunshiDAI.divide(new BigDecimal(i),BigDecimal.ROUND_DOWN);
			BigDecimal nextSHOU=new BigDecimal(1.0);
			nextSHOU=nextSHOU.setScale(50);
			nextSHOU=bunshiSHOU.divide(new BigDecimal(i),BigDecimal.ROUND_DOWN);
			*/
			String takeshi=bunshiDAI.toPlainString();
			String kiyoto=bunshiSHOU.toPlainString();

			//if(i%2==0&&ok%2==1)System.out.println(takeshi+" "+kiyoto);
			int sames=1;
			for(int j=2;j<Math.min(takeshi.length(),b.length());j++){
				if(takeshi.charAt(j)==b.charAt(j))sames++;
				else break;
			}
			if(sames>max){
				max=sames;
				maxBUNPO=i;
				maxBUNSHI=bd.multiply(new BigDecimal(i)).intValue();
			}
	sames=1;
			for(int j=2;j<Math.min(kiyoto.length(),b.length());j++){
				if(kiyoto.charAt(j)==b.charAt(j))sames++;
				else break;
			}
			if(sames>max){
				max=sames;
				maxBUNPO=i;
				maxBUNSHI=bd.multiply(new BigDecimal(i)).intValue()+1;
			}
			}
		}
		return maxBUNSHI+"/"+maxBUNPO+" has "+max+" exact digits";
	}
}

Challenge Phase:
ビヨン君になれました。狩りの時間だ!
500に1,{"."}を突っ込んで6つ落とした。気がついたら他の人の1000が全部落とされてしまった。本当は1000も落としたかったのですが……

System Test:
なぜか全部通ってしまった

結果
248.20 + 387.75 + 421.40 + 300.00 = 1357.35(5位)
1167 -> 1351

次回からDiv1なのでDiv1の過去問たくさんやりますかね。