Hatena::Grouptopcoder

tochukasoの日記

 | 

2014-08-12

天下一プログラマコンテスト予選A

| 17:09

1完

A問題

問題概要

・1~1000までを辞書順(1,10,100,1000,11,110・…999)で出力せよ

解き方

・3重ループ+1000を出力するための例外処理?を書く。

・Stringのlistに1~1000を突っ込んでArrays#sortで書いた方がよさそう。

    void solve() throws Throwable {
        
        for (int i = 1; i <= 9; i++) {
            pw.println(i);
 
            for (int j = 0; j <= 9; j++) {
                pw.println(i+""+j);
                for (int j2 = 0; j2 <= 9; j2++) {
                    pw.println(i+""+j+j2);
                        
                    if(i == 1 && j == 0 && j2 == 0) {
                        pw.println("1000");
                    }
                }
            }
            
        }      
    }

B問題

問題概要

・2種類の攻撃方法があって、攻撃毎に掛ける時間や、使用するエネルギー的なものの量が違う。

・また、コンボの概念もある。

解き方

・シミュレーションするだけ。

・のはずが、全く解けず。時間だけ過ぎる。。。

・32まではAC、、、、以降が全部×。

・なんだろうなぁ。組みなおしてみよう。C問題も不明。

300位ぐらい。ひどい結果だった

**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問題の部分点も取れそうだったのに残念

 |