37.50.48

%20 の ブログ

yukicoder No.832 麻雀修行中

この記事は、yukicoder No.832 麻雀修行中 の解説です。

\(H[i]=\)「牌 \(i\) の枚数」とする。
各牌がアガリ牌かどうかを判定するために、以下のようにする。

その牌が元々 \(4\) 枚ある牌の場合、(この問題の定義では)アガリ牌ではないので判定対象から除外する。
実際にその牌を追加する( \(H[i]+=1\) )(後で元に戻す)。
雀頭(ジャントウ:問題文でいう「 AA 」)を仮定する。
同じ牌を \(2\) 枚使うので、\(2\) 枚以上ある牌だけが雀頭の候補となる。
雀頭にした牌を \(2\) 枚使う( \(H[i]-=2\) )(後で元に戻す)。
ガリ牌と雀頭を仮定すると、残り \(12\) 枚を \(4\) 面子(メンツ:\(3\) 枚 \(1\) 組のやつ)に分けることになる。
\(111222333\) は、\(\{123,123,123\}\) の代わりに \(\{111,222,333\}\) と解釈することができるので、同じ順子(シュンツ:\(123\) や \(567\) など)は \(2\) 個までしかないと決めつけてよい。

次のような DP を考える。

  • \(dp[i][j][k]=\)「牌 \(i\) まで見て、順子の先頭が \(j\) 個、順子の真ん中が \(k\) 個あるという状態を作れるかどうか」

ここで、「先頭」は例えば \(567\) の \(5\)、「真ん中」は例えば \(234\) の \(3\) を指す。
次のように初期化する。

  • \(dp[0][0][0]=\mathrm{true}\)
  • \(dp[0][j][k]=\mathrm{false}\)( \((j,k)\ne(0,0)\) のとき)

順子の先頭や真ん中として使う牌を決めたとき、それより \(1\) 大きい牌を予約したことになる。予約されているはずの牌が足りなければ無効な遷移である。
予約された牌を使い終わって残った牌の枚数が \(3\) 以上なら \(3\) 枚で刻子(コーツ:\(222\) や \(999\) など)ができる。
よって、次のような遷移になる。

  • for \(i\) in \(1\cdots9\)
    • for \(j\) in \(0\cdots2\)
      • for \(k\) in \(0\cdots2\)
        • \(t=H[i]-j-k\) として、\(t\ge0\) のとき、\(dp[i][t\%3][j]|=dp[i-1][j][k]\)

\(dp[9][0][0]=\mathrm{true}\) ならば仮定は正しい。

七対子は \(H[i]=2\) となる \(i\) の個数が \(7\) 個かどうかを判定すればよいので明らか。