ことさら−古都プログラマーの更級日記

京都でお寺を回りながら御朱印集めをしていたエンジニアのブログ。おもに技術的なはなしとか日常的なはなし。たまにカメラの話や競馬の話も書きます。

AOJ 1277: Minimal Backgammon

はじめに

問題文概訳

「ミニバックギャモン」というシンプルなバックギャモンを考える。 このゲームは、一人でプレイする。 さいころ1つとチェッカー(プレイヤーの分身)1つを使う。

ゲームのボードには N+1 この正方形が一直線にならんでいる。 正方形には、0(スタート)からN(ゴール)までのラベルがついている。 最初に、チェッカーはスタート(0)にある。 このゲームの目的は、チェッカーをゴール(N)まで移動させることである。 チェッカーはサイコロの目のぶんだけ進む。 サイコロには1から6までの整数の目があり、どの目も等しい確率で出るとする。

チェッカーはゴールを超えたりしない。 サイコロによってゴールを超えた場合は、超えた分だけゴールから後退する。 例えば、チェッカが(N-3)にある時に5の目が出たとすると、 チェッカーは(N-2)の位置に移動する。 次のターンにサイコロを振って進む方向は、再びゴールの方向となる。

それぞれの正方形には、ゴールを除き、以下の2種類の命令が書いてあることがある。

  • Lose one turn (L): チェッカーがここで止まった場合、次のターンチェッカーは動けない
  • Go back to the start (B): チェッカーがここで止まった場合、チェッカーはスタートに戻る

ゲームのボードが与えられるので、あなたには与えられたターン以内でゲームが終わる確率を求めて欲しい。

入力

入力がいくつかのデータセットを含む。 それぞれのデータセットは以下の形式になっている

N T L B
Lose1
...
LoseL
Back1
...
BackB

Nはゴールのラベルで、 5 \leq N \leq 100。 Tはターン数で  1 \leq T \leq 100である。 LはLose one turnのマスの数、BはGo back to the startのマスの数で、  1 \leq L, B \leq N-1 である。 これらはスペース区切りで入力される

続くL行には Lose one turn のマスの番号、 B行には Go back to the startのマスの番号が与えられる。  1 \leq Lose, Back \leq N-1 で、 1つのマスに2つのLoseが重なったり、Backが重なったりはしない。 また、1つのマスにLoseとBackが同時に出現することもない。

出力

Tターン以内でゴールできる確率を出力せよ。 誤差は 0.00001 まで許容される

方針

動的計画法で解く。dp[i][j] = iターン目でマスjにいる確率 とする。doubleでも精度は問題ないが、doubleを出力する場合、Javaではちゃんとprintfを使い桁数など指定してあげること。

実装

class Main extends MyUtil{
    public static void main(String[] args) throws Exception{
        while(true){
            int n = readIntMap(0);
            int t = readIntMap(1);
            int l = readIntMap(2);
            int b = readIntMap(3);
            if(n+t+l+b == 0) break;
            
            int[] table = new int[n+1];
            // 休み
            for(int i = 0; i < l; i++){
                table[readInt()] = 1;
            }
            // 戻る
            for(int i = 0; i < b; i++){
                table[readInt()] = 2;
            }
            
            double[][] dp = new double[t+1][n+1];
            dp[0][0] = 1;
            
            for(int turn = 0; turn < t; turn++){
                for(int i = 0; i < n; i++){
                    for(int dice = 1; dice <= 6; dice++){
                        int masu = i + dice;
                        if(masu > n){
                            masu = n - (masu - n);
                        }
                        if(table[masu] == 1){
                            // 一回休みの場合
                            if(turn + 2 <= t){
                                dp[turn+2][masu] += dp[turn][i] * 1.0/6.0;
                            }
                        }else if(table[masu] == 2){
                            // スタートに戻る場合
                            dp[turn+1][0] += dp[turn][i] * 1.0/6.0;
                        }else{
                            // 普通のマスの場合
                            dp[turn+1][masu] += dp[turn][i] * 1.0/6.0;
                        }
                    }
                }
            }
            
            double ans = 0;
            for(int i = t; i >= 0; i--){
                ans += dp[i][n];
            }
            System.out.printf("%.8f\n", ans);
        }
    }
}