TopCoder SRM 483

SRM 483(9/26 1:00~3:00)

今回は，Easyを出来るだけ正確かつ早く解く事を目標としました．

■BestApproximationDiv1(Div1 Easy)

□問題
"0.dddddd"という形の小数numberが与えられる．分母がmaxDen以下の分数d/nとnumberを比較し，小数点以下何桁目まで一致しているかを数える．一致桁数が最も大きい分数を求めよ．但し，答えが複数存在する場合には，分母が小さいものを，分母が等しい場合は，分子の小さいものを出力せよ．

□解法
全探索するとO(maxDen²)となりますが，1≦maxDen≦1000ですので問題ありませんでした．

□コード

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3.   
4. public class BestApproximationDiv1{  
5.     public String findFraction(int maxDen, String number){  
6.         int bestD=1, bestN=0;  
7.         int maxDigit=0;  
8.         for(int d=maxDen;d>=1;d--){  
9.             for(int n=d-1;n>=0;n--){  
10.                 String s=((double)n/d)+"";  
11.                 if(s.length()==1)  
12.                     s+=".";  
13.                 s+="000000";  
14.                 int digit=1;  
15.                 for(int i=2;i<number.length()&&i<s.length();i++){  
16.                     if(number.charAt(i)!=s.charAt(i))  
17.                         break;  
18.                     digit++;  
19.                 }  
20.                 if(digit>=maxDigit){  
21.                     bestD=d;  
22.                     bestN=n;  
23.                     maxDigit=digit;  
24.                 }  
25.             }  
26.         }  
27.         return bestN+"/"+bestD+" has "+maxDigit+" exact digits";  
28.     }  
29. }  

import java.util.*;
import java.lang.*;

public class BestApproximationDiv1{
    public String findFraction(int maxDen, String number){
        int bestD=1, bestN=0;
        int maxDigit=0;
        for(int d=maxDen;d>=1;d--){
            for(int n=d-1;n>=0;n--){
                String s=((double)n/d)+"";
                if(s.length()==1)
                    s+=".";
                s+="000000";
                int digit=1;
                for(int i=2;i<number.length()&&i<s.length();i++){
                    if(number.charAt(i)!=s.charAt(i))
                        break;
                    digit++;
                }
                if(digit>=maxDigit){
                    bestD=d;
                    bestN=n;
                    maxDigit=digit;
                }
            }
        }
        return bestN+"/"+bestD+" has "+maxDigit+" exact digits";
    }
}

■Challenge
他の人達の回答が結構長くて，読めませんでした．

■Result
○×× 0 -0
190.00p

今回は，HardがMediumよりも簡単という噂が聞こえてきて，Hardを解かなかった事を後悔していましたが，意外や意外，実は難しい問題だったようで，多くの人がSystem Testで落とされていました．

■Rating
1372 -> 1463

結構上がりました．4回連続Rating上昇です．目標のYellowCoderまであと少し…．