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ですので問題ありませんでした．

□コード

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まであと少し…．