Hatena::Grouptopcoder

tochukasoの日記

 | 

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

 |