Hatena::Grouptopcoder

tochukasoの日記

2014-08-12

**AtCoder Regular Contest 27

| 17:09

3完

A問題

問題概要

・時間と分が引数で与えられる。

・18時まであと何分あるかを返却せよ

解き方
    void solve() throws Throwable {
        int H = (17 - readInt()) * 60;
        int M = 60 - readInt();
        pw.println(H+M);
    }

B問題

問題概要

・長さが同じ2つの文字列が与えられる。

・この2つの文字列は同一の数字を示す。

・アルファベットはそれぞれ0~9の可能性がある。

・矛盾をおこなさない数字の組み合わせが何通りあるかを答える。

解き方

・効率的な方法は分からないので愚直にシミュレーション

・部分点ゲット・・・・・

・うーん。改善方法が分からない。

・アルファベットの絞り込みを行っている個所を2重ループで回すように変更。

AC!! 嘘解法っぽいなぁ・・・

・アルファベットを絞り込んでいるときに関係性があるアルファベットの数字の可能性も消去しているはずだけど、

 漏れがあるのかも

    void solve() throws Throwable {
        
        int N = readInt();
        String string1 = readString();
        String string2 = readString();
        char[] s1 = string1.toCharArray();
        char[] s2 = string2.toCharArray();
        boolean[][] prohibitAlphabets = new boolean[26][10];
        
        for (int Z = 0; Z < 2; Z++) {
            
        for (int i = 0; i < N; i++) {
            char c1 = s1[i];
            char c2 = s2[i];
            boolean isNum1 = false;
            boolean isNum2 = false;
            if (c1 < 'A') {
                isNum1 = true;
            }
            if (c2 < 'A') {
                isNum2 = true;
            }
            if(isNum1) {
                if(!isNum2) {
                    for (int j = 0; j < 10; j++) {
                        if(j == Character.getNumericValue(c1)) continue;
                        prohibitAlphabets[c2-'A'][j] = true;
                    }
                }
                
            } else {
                if(i == 0) {
                    prohibitAlphabets[c1 - 'A'][0] = true;
                }
                if(!isNum2) {
                    for (int j = 0; j < 10; j++) {
                        if(prohibitAlphabets[c1 - 'A'][j]) prohibitAlphabets[c2-'A'][j] = true;
                        if(prohibitAlphabets[c2 - 'A'][j]) prohibitAlphabets[c1-'A'][j] = true;
                    }
                }
            }
 
            if(isNum2) {
                if(!isNum1) {
                    for (int j = 0; j < 10; j++) {
                        if(j == Character.getNumericValue(c2)) continue;
                        prohibitAlphabets[c1-'A'][j] = true;
                    }
                }
            } else {
                if(i == 0) {
                    prohibitAlphabets[c2 - 'A'][0] = true;
                }
            }
        }
        }
        long res = 1;
        boolean[] used = new boolean[26];
 
        for (int i = 0; i < N; i++) {
            long count = 0;
            char c1 = s1[i];
            char c2 = s2[i];
            for (int j = 0; j < 10; j++) {
                if (c1 < 'A' || c2 < 'A' || used[c1 - 'A'] || used[c2 - 'A']) {
                    count = 1;
                    break;
                }
                if(prohibitAlphabets[c1 - 'A'][j] || prohibitAlphabets[c2 - 'A'][j]) continue;
                count++;
            }
            if(c1 >= 'A') {
                used[c1-'A'] = true;
            }
            if(c2 >= 'A') {
                used[c2-'A'] = true;
            }
            res*=count;
            
        }
        
        pw.println(res);
    }

C問題

問題概要

・典型的DP

・ナップザック問題が少し複雑になった感じ

・2種類のチケットとチケットで買えるものがあって、価値の総和が最も高い場合にいくつになるかを返却する。

・2種類のチケットのうち、1種類のチケットは物を買う時に常に消費しなければならない制約がある

解き方

・必須チケットじゃなくて通常のチケットを優先して使えばよさそう

・部分点もある問題かぁ・・・・

・買えるもののインデックス(300以下)、必須チケットの使用枚数(300以下)、通常チケットの使用枚数(300以下)の値毎に

 最大の価値をメモすることでDP出来そう。

 でも、300*300*300=2700万要素の配列かぁ・・・・メモリ足りなそうだなぁ。

・うーーーーん。どうやって解くべきか。・・・・intのメモリ確保容量ってどれくらいだろう。

 4byteかぁ。ということは、100メガちょっと。ん?足りそうだぞ。

・MLE・・・・・30点ゲット

・やっぱりC問題はまだ解けないよなぁ。

・と思いつつもよくよく見直してlong型で配列を宣言していたのをint型に変更したらAC

    int X, Y, N;
    int[] mustTikets = null;
    int[] happiness = null;
    static int[][][] dp = null;
 
    void solve() throws Throwable {
        
        X = readInt();
        Y = readInt();
        N = readInt();
        mustTikets = new int[N];
        happiness = new int[N];
        for (int i = 0; i < N; i++) {
            mustTikets[i] = readInt();
            happiness[i] = readInt();
        }
        
        dp = new int[N][X+1][Y+1];
        pw.println(dfs(0,0,0));
    }
 
    int dfs(int i, int special, int normal) {
        if (i == N)
            return 0;
        if (dp[i][special][normal] != 0)
            return dp[i][special][normal];
        if (special >= X || mustTikets[i] + special + normal > X + Y) {
            return dp[i][special][normal] = dfs(i + 1, special, normal);
        } else {
            int last = Math.max(0, mustTikets[i] - (Y - normal) - 1);
            return dp[i][special][normal]= Math.max(dfs(i + 1, special, normal),
                    dfs(i + 1, special + 1 + last,
                            normal + (mustTikets[i] - last - 1))
                            + happiness[i]);
        }
    }

結果は59位で、2級に昇級出来ましたヽ(^o^)丿

時間があれば、D問題の部分点も取れそうだったのに残念

2014-07-28

CodeForces MemSQL

| 16:41

1完・・・・

A問題

概要

・固有名詞のリストがあらかじめ提示される。

・引数で「a..b..c」の様な文字列が与えられる。

・'.'は任意の一文字に置き換えることが出来る。

・引数がどの文字列に合致するかを調べて返却する。

解法

・あらかじめ提示されている文字列にmatch(String regex)を使用する

    void solve() throws Throwable {
        int N = readInt();
        String word = readString();
        String[] names = {
                "vaporeon", "jolteon", "flareon", "espeon", "umbreon", "leafeon", "glaceon", "sylveon"
        };

        for (String string : names) {
            if(string.matches(word)) {
                pw.println(string);
                return;
            }
        }
    }

B問題

概要

・N * Mサイズの格子が与えられる。

・任意の4点を指定することが出来る。

・[p1,p2],[p2,p3],[p3,p4]の3本の直線の長さの総和が最大になるような4点を求める。

解法

・任意の4点は、左上(0,0),右下(N,M)が中心になる。

 そのため、点の候補になりそうなものをあらかじめ列挙する。(ここの指定が甘くて落としました。)

 順列を使用するが、4Cnなので、nが20ぐらいまでなら余裕で計算できた。

・また、N,Mが0の時の処理は特例として処理するようにした。

    int[][] pos = new int[8][2];
    double max = 0;
    int[] maxPos = null;

    void solve() throws Throwable {
        
        int N = readInt();
        int M = readInt();
        
        if(N == 0) {
            pw.println(0 + " " + 1);
            pw.println(0 + " " + M);
            pw.println(0 + " " + 0);
            pw.println(0 + " " + (M - 1));
            return;
        } else if(M == 0) {
            pw.println(1 + " " + 0);
            pw.println(N + " " + 0);
            pw.println(0 + " " + 0);
            pw.println((N-1) + " " + 0);
            return;
        }

        pos[0] = new int[] {0,0};
        pos[1] = new int[] {N,M};
        pos[2] = new int[] {N - 1,M};
        pos[3] = new int[] {0,1};
        pos[4] = new int[] {1,0};
        pos[5] = new int[] {N,0};
        pos[6] = new int[] {N, M -1};
        pos[7] = new int[] {0, M};
`
        permutationAll(new int[] {0,1,2,3,4,5,6,7});
        pw.println(pos[maxPos[0]][0] + " " + pos[maxPos[0]][1]);
        pw.println(pos[maxPos[1]][0] + " " + pos[maxPos[1]][1]);
        pw.println(pos[maxPos[2]][0] + " " + pos[maxPos[2]][1]);
        pw.println(pos[maxPos[3]][0] + " " + pos[maxPos[3]][1]);
    }
    void permutationAll(int[] p) {
        permutation(p, 0, p.length - 1);
    }
    void permutation(int[] elements, int nowCnt, int totalCnt) {
        if (nowCnt == 4) { 
            O++;
            double sum = 0;
            int p1 = elements[0];
            int p2 = elements[1];
            int p3 = elements[2];
            int p4 = elements[3];
            if(pos[p1][0] == pos[p2][0] && pos[p1][1] == pos[p2][1]) return;
            if(pos[p1][0] == pos[p3][0] && pos[p1][1] == pos[p3][1]) return;
            if(pos[p1][0] == pos[p4][0] && pos[p1][1] == pos[p4][1]) return;
            if(pos[p2][0] == pos[p3][0] && pos[p2][1] == pos[p3][1]) return;
            if(pos[p2][0] == pos[p4][0] && pos[p2][1] == pos[p4][1]) return;
            if(pos[p3][0] == pos[p4][0] && pos[p3][1] == pos[p4][1]) return;

            double seg1 = Math.sqrt(Math.pow(pos[p1][0] - pos[p2][0], 2) + Math.pow(pos[p1][1] - pos[p2][1], 2)); 
            double seg2 = Math.sqrt(Math.pow(pos[p2][0] - pos[p3][0], 2) + Math.pow(pos[p2][1] - pos[p3][1], 2)); 
            double seg3 = Math.sqrt(Math.pow(pos[p3][0] - pos[p4][0], 2) + Math.pow(pos[p3][1] - pos[p4][1], 2)); 
            sum = seg1 + seg2 + seg3;
//            System.out.println(sum + " " + p1 + " " + p2 + " " + p3 + " " + p4);

            if(max < sum) {
                max = sum;
                maxPos = Arrays.copyOf(elements, 4);
            }

        } else {

            for (int i = nowCnt; i <= totalCnt; i++) {
                int tmp = elements[nowCnt]; 
                elements[nowCnt] = elements[i]; 
                elements[i] = tmp;
                permutation(elements, nowCnt+1, totalCnt);
                tmp = elements[nowCnt]; 
                elements[nowCnt] = elements[i]; 
                elements[i] = tmp;
            }
        }
    }

この問題は結構時間を使ったので解きたかった。

C問題

概要

・1~NまでのトランプがMセットある。

・Mセットをごちゃ混ぜにして、N枚取得する。

・1枚トランプを引いて、また山に戻した時に、同一の数のトランプを引く確率を求める。

解法

・不明・・・・・

・コンビネーションを使うと計算量はすごい事になりそうだし、longの範囲で収まらない。

・他の人の解法だけ記しておく。

    void solve() throws Throwable {
        double N = readInt();
        double M = readInt();
        if(M == 1) {
            pw.println(1.0 / N);
            return;
        }
        pw.println(1 / N + (M-1) * (N-1) / N / (N * M - 1));
    }

Mが1の時は、トランプを混ぜないので、1/Nになるのは分かる。

それ以外の場合が分からない。

同一のカードが一枚しか入らない場合と、うーん。

D問題

概要

・タスクがN個ある。

・1個のタスクはA,B,Cを順番にこなす必要がある。

・A,B,Cそれぞれ一度に行えるタスクの個数とタスクにかかる時間が引数で与えられる。

・全てのタスクを終えるための最小の時間を答える。

解法

・動的計画法を使用する。

・タスクAは単純にフルで回す。(タスクAが終わった毎にタスクAを実行する。)

・タスクBのN個目が終わる最小の時間は、

 「タスクAのN個目が終わった時間」

 「タスクBの[N-タスクBを一度に処理できる個数]が終わった時間」

 のいずれかの後に終わる時間+タスクBにかかる時間となる。

・タスクCについてもタスクBと同様にタスクBとの比較で最小時間を計算する。

    int[] dp2 = new int[10001];
    int[] dp3 = new int[10001];
    int K = 0;
    int N1 = 0;
    int N2 = 0;
    int N3 = 0;
    int T1 = 0;
    int T2 = 0;
    int T3 = 0;

    void solve() throws Throwable {
        K = readInt();
        N1 = readInt();
        N2 = readInt();
        N3 = readInt();
        T1 = readInt();
        T2 = readInt();
        T3 = readInt();
        int before = 0;
        
        for (int i = N1; i < K + N1; i+=N1) {
            int nCnt = i / N1;
            int nTime = nCnt * T1;
            for (int j = before; j < i; j++) {
                int jCnt = (j - before) / N2 + 1;
                if(j - N2 >=0) {
                    dp2[j] = Math.max(dp2[j - N2] + T2, nTime + T2 * jCnt);
                } else {
                    dp2[j] = nTime + T2 * jCnt;
                }
            }
            before = i;
        }
        dp2[K] = dp2[K-1];
        before = 0;
        for (int i = 0; i < K; i++) {
            if(i -N3 >= 0) {
                dp3[i] = Math.max(dp2[i] + T3, dp3[i-N3] + T3);
            } else {
                dp3[i] = dp2[i] + T3;
            }
        }
        pw.println(dp3[K-1]);
    
    }

タスクAの処理にかかる時間を計算するところで、

タスクAのループ処理の終了条件をKにしているところで失敗しました。

ループの開始をタスクAで処理できる個数にしていたので、

K+N1まで計算しないとやりきらないことがあります。

結果としては1完ですが、

なぜかレートは上がりました・・・・・。

1488⇒1585

土曜か日曜の夜早め以外の時間帯は参加できなくなるので、

競プロはもうたまにだなー

2014-07-20

CodeForces R256 Div2

| 18:45

2完

A問題

概要

 ・複数の棚がある。

 ・棚にメダルとトロフィーを入れたい。

 ・一つの棚にはメダル10個までかトロフィー5個までのどちらかのみを入れる。

 ・それぞれの大会で獲得したメダルとトロフィーの数と棚の数が与えられる。

 ・全て格納出来るかどうかを答える。

解答方法

 ・メダルとトロフィーの総和をそれぞれ計算する。

 ・それぞれ格納できる数で割る。

 ・また、剰余が発生するかを確認し、剰余が発生する場合は棚の数をデクリメントする。

ただし、他の人のソースを見て気付いたけど、わざわざ剰余を計算するよりも、以下の様に書いた方がすっきりしてよい。

あらかじめ「割られる数」に割る数-1を足してやれば、余りが出た場合も切り上げで求めることが出来る。

  N -= (aS + 4) / 5;

    void solve() throws Throwable {
        int[] a = readIntArray();
        int[] b = readIntArray();
        int N = readInt();
        
        int aS = 0;
        for (int aN  : a) {
            aS += aN; 
        }
        
        int bS = 0;
        for (int i : b) {
            bS += i;
        }
        
        N -= aS / 5;
        if (aS % 5 != 0) N--;
        
        N -= bS / 10;
        if (bS % 10 !=0) N--;
        
        if(N >=0) {
            pw.println("YES");
        } else {
            pw.println("NO");
        }
    }

B問題

概要

 ・文字列Sを変形して文字列Tにすることが出来るかどうか。

 ・文字列Sの要素を削除するだけでTに出来る場合は、「automaton」

 ・文字列Sの要素を並び変えるだけでTに出来る場合は、「array」

 ・どちらも行う場合は、「both」

 ・どちらを行っても出来ない場合は、「need tree」

解答方法

 ・それぞれの文字列のアルファベットの出現回数をメモする。

 ・文字列Tの方が出願回数の多いアルファベットがある場合、「need tree」

 ・文字列Sの方が出現回数の多いアルファベットがある場合、「automaton」のフラグを立てる。

 ・文字列Sと文字列Tで最長共通部分文字列を取得し、最長共通部分文字列の長さが文字列Tと等しくない場合、「array」のフラグを立てる。

 ・上記の2点より、「automaton」、「array」、「both」を判別する。

    void solve() throws Throwable {
        String s = readLine();
        String t = readLine();
        
        int[] sA = new int[27];
        int[] tA = new int[27];
        for (char c : s.toCharArray()) {
            sA[c-'a']++;
        }
        for (char c : t.toCharArray()) {
            tA[c-'a']++;
        }
        
        boolean isAutoMaton = false;
        for (int i = 0; i < 27; i++) {
            if(sA[i] > tA[i]) {
                isAutoMaton = true;
            } else if (sA[i] < tA[i]) {
                pw.println("need tree");
                return;
            }
        }
        
        char[] sX = s.toCharArray();
        char[] tX = t.toCharArray();
            
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < t.length(); j++) {
                if(sX[i] == tX[j]) {
                    dp[i+1][j+1] = dp[i][j] + 1;
                } else {
                    dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        
        boolean isArray = false;
        if(dp[s.length()][t.length()] != t.length()) {
            isArray = true;
        }
        
        if(isAutoMaton && isArray) {
            pw.println("both");
        } else if (isAutoMaton) {
            pw.println("automaton");
        } else if (isArray) {
            pw.println("array");
        }
    }    

C問題

概要

 ・複数のフェンスがある。

 ・フェンスの横幅は1M,縦幅はそれぞれ異なる。

 ・フェンスに色を塗りたい。一回で塗れるのは縦方向、または横方向のみ。横方向に塗る場合は、塗る高さにフェンスが連続してないといけない。

 ・全てのフェンスに色を塗る時の最小の回数を求める。

解答方法(他の人のソースを参考にしてます)

 ・動的計画法を使う。

 ・dp[N+1]に、N本目を横塗りした場合の最小の塗る回数をメモする。

  やり方としては、N本目までに出現しているフェンスから遡って順々に、

  最も高さの低いフェンスから、今回横で塗りたいフェンスの高さの差を求める。

  N-j本目の最小の塗る数 + (i - j - 1)(一本遡る毎に縦塗りをする)+ 求めた高さの差

  N本目からN-j本目まで塗る場合の最小の塗る数を求める。

 

    void solve() throws Throwable {
        int N = readInt();
        int[] a = new int[N + 2];
        for (int i = 0; i < N; i++) {
            a[i+1] = readInt();
        }
        
        int[] dp = new int[N + 2];
        Arrays.fill(dp, N);
        dp[0] = 0;
        
        for (int i = 1; i <= N + 1; i++) {
            int minH = Integer.MAX_VALUE;
            for (int j = i - 1; j >= 0; j--) {
                minH = Math.min(minH,  a[j]);
                int p = Math.max(0, a[i] - minH);
                dp[i] = Math.min(dp[i], dp[j] + i-j-1 + p);
//                System.out.println(i + " " + j + " " + dp[i]);
            }
        }
        
        pw.println(dp[N+1]);
}

1501⇒1586

最高レート更新ヽ(^o^)丿

2014-07-14

CodeForces R255 Div2

| 21:24

2完

C問題も問題の解き方の方向性は間違ってなかった。

実装力の無さが悔やまれる。

いいデバッグの仕方を身につけたい。

でも、567th/ 3251で過去最高の出来。

・A問題

 数列が与えられる。

 数列をKで割った余りをテーブルに格納する。

 既に余りが格納されている場合、順序を返却する。

 一回も衝突が起きない場合は-1を返却する。

 Setを使用して既に格納されている数字を管理する。

 数列の要素を順番に処理して、追加できない場合は順序を出力する。

    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        
        Set<Integer> table = new HashSet<Integer>();

        int P = readBufInt();
        int N = readBufInt();
        for (int i = 1; i <= N; i++) {
            if(!table.add(readBufInt() % P)) {
                pw.println(i);
                return;
            }
        }
        pw.println("-1");       
    }

・B問題

 文字列が与えられる。

 文字列はアルファベットの'a'から'z"で構成されている。

 それぞれ'a'から'z'は点数を持っている。

 文字の順序*文字種の点数の総和を求める。

 また、任意の文字をk文字挿入することが出来る。

 最大値となる総和を求める。

 与えられた文字列のスコアを取得する。

 アルファベットの中で最も価値の高い文字を判別する。

 K*最も高い + 規定文字列のスコアで最大値を求める。

    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        String S = br.readLine();
        int K = readBufInt();
        int[] a = readIntArray();
        
        int sum = 0;
        int max = 0;
        char[] sA = S.toCharArray();
        for (int i = 0; i < sA.length; i++) {
            char c = sA[i];
            sum += a[c - 'a'] * (i + 1);
        }
        
        for (int i : a) {
            max = Math.max(max, i);
        }
        for (int i = 1; i <= K; i++) {
            sum += (i + sA.length) * max; 
        }
        pw.println(sum);
    }

・C問題

 数列が与えられる。

 数列の任意の一文字を好きな数字に入れ替えることが出来る。

 必ず増加する(i < i+1)ような部分数列を取得し、最長の長さを求める。

 それぞれの要素の部分数列の長さを計算し、メモをする。

 任意の一文字を替えることが出来るので、最長の部分数列は以下のいずれかのパターンが考えられる。

 ・部分数列を3つ加算出来る場合、

  この場合は真ん中の数列の長さが1,かつ、左の数列の最終数字 + 2 <= 右の数列の最初の数字の条件を満たす必要がある。

1,2,3,8,5,6,7

 ・部分数列を2つ加算できる場合、

右の数列の長さが2以上、かつ、左の数列の最後の文字 + 2 <= 右の数列の2文字目

  1,2,3,2,5,6,7

 ・部分数列を2つ加算できる場合、

  左の数列の長さが2以上、かつ、左の数列の最後から2文字目 + 2 <= 右の数列の最初の数字

1,2,8,4,5,6,7

    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        int N = readBufInt();
        int[] arr = readIntArray();
        
        if (N < 3) {
            pw.println(N);
            return;
        }
        shakutori(N, arr);
    }    

    static void shakutori (int N, int[] arr) {
        int[] subsequence = new int[arr.length + 1];
        System.arraycopy(arr, 0, subsequence, 0, arr.length);
        subsequence[arr.length] = -1;
        
        int to = 0;
        int before = 0;
        int[] dp = new int[N + 1];
        int length = 0;
        for (; to <= N; to++) {
            int now = subsequence[to];
            
            if(before < now) {
                length++;
            } else {
                for (int i = 0; i <= length; i++) {
                    dp[to - i] = length;
                }
                length = 1;
            }

            dp[to] = length;
            before = now;
        }
        dp[N] = 0;
//        for (int i = 0; i < N; i++) {
//            System.out.println(dp[i]);
//        }
        
        int max = 0;
        for (int i = 1; i < N - 1; i++) {
            int x = 0;
            if(dp[i + 1] == 1 && subsequence[i] + 1< subsequence[i + 2]) {
                x = dp[i] + dp[i + 2] + 1;
            }
            if (subsequence[i] > subsequence[i - 1] && subsequence[i] >= subsequence[i+1] ) {
                if(subsequence[i] + 1 < subsequence[i + 2]) {
                    x = Math.max(x, dp[i] + dp[i + 1]);
                }
                if (subsequence[i - 1] + 1 < subsequence[i + 1]) {
                    x = Math.max(x, dp[i] + dp[i + 1]);
                }
            }
            x = Math.max(x, dp[i] + 1);
            
            max = Math.max(max, x);
        }
        
        pw.println(Math.min(N, max));
    }

でも、この解法だとパターンわけがメンドクサイ上に、

漏れがないかの証明、判断が難しい。

これでシステムテストは通ってるけど、嘘解法な気もする。

初めにそれぞれの部分数列の長さを計算して、

あとは組み合わせるって考え方はいいと思うんだけど・・・・

D問題

 2次元配列の数列が与えられる。

 K回、縦、横の任意の列、行の総和を取得出来る。

 ただし、列の総和を取得すると、その総和を取得するための構成要素はPを減産する必要がある。

 K回の総和が最大となるように列、行から値を取得する。

 うーーーーん。

 データの量的に全探索はとても間に合わなそう。

 列か行かの総和が大きい方から毎回引けばいいか。

 サンプル通った。

 WA

 そりゃそうか。K回やらなきゃいけないんだから、マイナスを少なくするのを優先した方がいいケースもある。

 駄目だ。分からん。


1359⇒1501

念願のブルーコーダーになりました。

年内の目標はイエローコーダー!!

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