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\) 個かどうかを判定すればよいので明らか。
