はじめに

問題文概訳

「ミニバックギャモン」というシンプルなバックギャモンを考える。このゲームは、一人でプレイする。さいころ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);
        }
    }
}

猫でもわかるWebプログラミングと副業

本業エンジニアリングマネージャー。副業Webエンジニア。Web開発のヒントや、副業、日常生活のことを書きます。

AOJ 1277: Minimal Backgammon

はじめに

問題文概訳

入力

出力

方針

実装