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の過去問たくさんやりますかね。