Hatena::Grouptopcoder

tochukasoの日記

 | 

2014-06-28

ARC026

| 00:21

なかなか脱初心者出来ない・・・・・・

・B問題

 ルートNまで探索する。

 N自身は約数に含めないでカウントする。

 ループで割り切れる方の数とループの数が同一の場合に重複してカウントしないように気を付ける。


    String P = "Perfect"; 
    String D = "Deficient"; 
    String A = "Abundant"; 
    /**
     * @throws Throwable
     */
    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        
        long N = readLong();
        if ( N == 1) {
            pw.println(D);
            return;
        }
        long sum = 1;
        long max = (long)Math.sqrt(N);
        
        for (int i = 2; i <= max; i++ ) {
            if (N % i == 0) {
               sum += i;
               if (i != N / i) 
               sum += (N / i) ;
            }
        }
        if (sum == N) {
            pw.println(P);
        } else if (sum > N) {
            pw.println(A);
        } else {
            pw.println(D);
        }
    }    

C問題

 区間l⇔rを全て照らすように蛍光灯を付けた場合の最小コストを選択する。

 まずはDPで考える。

 DP[l=0からrまでの長さ] = その範囲内での最小コスト

 dp[i] = Min(dp[i], dp[N[l + N[C])でLになるまでループ処理を行う。

 計算量はO(N*L)。

 これでは間に合わないと思い、実装をためらう。

 時間ぎりぎりでこの方針で実装する。

 5分間に合わない。

 この方針+RMQ(Range Minimum Query)で間に合わせることが出来る

200点 121

 |