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

2014-07-12

ABC B12

| 00:38

今回はテスト時間内の初の4完(前に400点はあったけど、満点が401点の時だったから、これが初の全完)

A,B,Cは単純なシミュレーション

D問題

 ・V個の頂点、E個の辺がある。

 ・任意の頂点からの最長距離が最短となる頂点を求める。

 ・競技プログラミングコンテストで初めての

  ダイクストラ法を使って、O(V^3)で解いた。

  半年前なら絶対に解けなかっただろうから、これが解けたのは感慨深い。

  Rは伸びないけど、きっと力はついてると思う。

    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        
        int N = readInt();
        int M = readInt();
        int[][] roads =  readIntMatrix(M);
        
        Map<Integer, List<Integer[]>> map = new HashMap<Integer, List<Integer[]>>();
        for (int i = 1; i <= N; i++) {
            map.put(i, new ArrayList<Integer[]>());
        }
        
        for (int i = 0; i < M; i++) {
            {
                List<Integer[]> list = map.get(roads[i][0]);
                int[] arr = {roads[i][1], roads[i][2]};
                list.add(convIntArray(arr));
            }
            {
                List<Integer[]> list = map.get(roads[i][1]);
                int[] arr = {roads[i][0], roads[i][2]};
                list.add(convIntArray(arr));
            }
        }
        
        int min = Integer.MAX_VALUE;
        
        for (int i = 1; i <= N; i++) {
            
            int[] dp = new int[N + 1];
            boolean[] used = new boolean[N+1];
            Arrays.fill(dp, Integer.MAX_VALUE - 100);
            dp[i] = 0;
            for (int z = 1; z <= N; z++) {
               
                int f = -1;
                int time = Integer.MAX_VALUE;
                for (int j = 1; j <= N; j++) {
                    if(!used[j] && time > dp[j]) {
                        time = dp[j];
                        f = j;
                    }
                }
                used[f] = true;
                
                List<Integer[]> list = map.get(f);
                for (Integer[] integers : list) {
                    int to = integers[0];
                    int t = integers[1];
                    dp[to] = Math.min(dp[to], dp[f] + t);
                }
            } 
            
            int max = 0;
            for (int j = 1; j <= N; j++) {
                max = Math.max(max, dp[j]);
            }
            
            min = Math.min(min, max);
        }
        
        pw.println(min);
    }    

162位

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

2014-06-21

ABC 11

| 01:16

C

1,2,3のいずれかで移動出来る。

Nから0に移動する。

NGの数値が与えられて、NGの数字には移動出来ない。

貪欲法で3,2,1の順番に移動出来るかチェックする。


    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        String NO = "NO" ;
        String YES = "YES";
        
        int N = readInt();
        int[] ng = new int[3];
        for(int i = 0; i < 3; i++) {
            ng[i] = readInt();
            if (ng[i] == N) {
                pw.println(NO);
                return;
            }
        }
        int now = N; 
        for (int i = 0; i < 100; i++) {
            boolean isRoopUpdate = false;
            for (int j = 3; j > 0; j--) {
                boolean isUpdate = true;
                int koho = now - j;
                if (koho < 0) continue;
                for(int n : ng) {
                    if (koho == n) {
                        isUpdate = false;
                        break;
                    }
                }
                
                if (isUpdate) {
                   if (koho == 0) {
                       pw.println(YES);
                       return; 
                   }
                   now = koho; 
                   isRoopUpdate = true;
                   break;
                }
            }
            
            if (!isRoopUpdate) {
                break;
            }
        }
        
        pw.println(NO);
    }    

D問題

Dの距離を移動出来る人がN回移動したときに

X,Yの地点にいる確率を求める。

まずはSRMTCO、1C Div2のHard問題の解法を適用するも100点。

TLE。O(N^3)では間に合わない。

ニコ生の解説によると、

パスカルの三角形を使用した解法がよいみたい。

それと、こういう移動系の問題は、左と下への移動を考えないというのが

有効なテクニックになる。

上と右への移動から、左と下への移動は推測出来るってことね。

正答は明日考えよう。

・・・・・・・

やっと出来た。

5時間ぐらいかかったんじゃなかろうか・・・・

パスカルの三角形を使って、nCi(nは事象の起きる総数。iは対象の事象)を計算する。

上下方向に進む確率(nCi) * 上下方向に進む事象の中で目的にたどり着く確率(iCx) * 左右方向に進む事象の中で目的にたどり着く確率((N-i)Cy)

上下方向に進む全パターンの総和が対象の確率となる。

パスカルの三角形は組み合わせの確率を出すのに便利だ。

Nが1000以内なら使えそう。

    static class Pascale {
        
        
        static BigDecimal[][] probability = new BigDecimal[1010][1010];
        
        static {
           //probability[0] = new double[1]l;
            for (int i = 0; i < probability.length; i++) {
                Arrays.fill(probability[i], BigDecimal.ZERO);
            }
           probability[0][0] = BigDecimal.ONE;
           for (int i = 1; i < probability.length; i++) {
              //probability[i] = new double[i + 1];
              probability[i][0] = BigDecimal.ONE;
              probability[i][i] = BigDecimal.ONE;
              for (int j = 1; j < i ; j++) {
                  probability[i][j] = probability[i - 1][j - 1].add(probability[i - 1][j]);
              }
           }
            
        }
        
        static BigDecimal calc(int cnt, int pCnt) {
            BigDecimal allCnt = new BigDecimal(2).pow(cnt); 
            BigDecimal elementCnt = probability[cnt][pCnt]; 
            BigDecimal p = elementCnt.divide(allCnt, MathContext.DECIMAL128);
            return p;
        }
    }
    
    /**
     * @throws Throwable
     */
    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int D = sc.nextInt();
        
        int X = sc.nextInt();
        int Y = sc.nextInt();
        
        if (X % D != 0 || Y % D != 0) {
            pw.println(0);
            return;
        }
       
        X = Math.abs(X / D);
        Y = Math.abs(Y / D);
         
        BigDecimal res = BigDecimal.ZERO;
        for (int i = X; i <= N; i++) {
            
            // iは上下方向への総移動回数
            // moveXCntは目的方向への移動回数
            int moveXCnt = (i - X);
            if (moveXCnt %2 !=0) {
                // 目的方向への移動後に余った移動回数が偶数でない場合に目的地に戻れないのでコンテニューする
                continue;
            }
            moveXCnt = moveXCnt / 2 + X;

            int moveYCnt = (N - i - Y);
            if (moveYCnt < 0 || moveYCnt %2 !=0) {
                continue;
            }
            moveYCnt = moveYCnt / 2 + Y;
            res = res.add(Pascale.calc(N, i).multiply(Pascale.calc(i, moveXCnt).multiply(Pascale.calc(N - i, moveYCnt))));
        }
        
        pw.println(res);
    }    

400点で65位。

過去最高かな?yeah

2014-06-15

ARC025

| 22:27

B問題すら解けなかったのは問題だ・・・・・

ただのシミュレーションなのになぁ

縦横の累積和すらうまく取れないとか。

オワコン過ぎる。

簡単な問題をひたすら解くべし。

    void solve() throws Throwable {
        startTime = System.currentTimeMillis();
        
        int a = readBufInt();
        int b = readBufInt();
        
        int[][] choko = new int[a][];
        for (int i = 0; i < a; i++) {
            choko[i] = readIntArray();
        }

        int max = 0;

        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                int[] dp = new int[b + 1];
                for (int k = 0; k + i < a; k++) {
                    int line = 0; 
                    for (int l = 0; l + j < b; l++) {
                        boolean isEven = (i + k + j + l) % 2 == 0;
                        int now = choko[i + k ][j + l];
                        now = isEven ? now : -now;
                        line += now; 
                        dp[l] = dp[l] + line ;
                        if (dp[l] == 0) {
                            max = Math.max(max, (k + 1) * (l + 1));
                        }
                    }
                }
            }
        }
        pw.println(max);
    }