次に、雀頭の確定であるが、牌の合計値から雀頭の候補を絞りこむことができる。面子は、連続した3つの数値、または同一の3つの数値であるため、3で割り切ることができる。よって、牌の合計値を3で割った余りによって、雀頭となりうる数が{1,4,7}、{2,5,8}、{3,6,9}のいずれかに絞りこむことができる。そのため、最大3つの雀頭候補について2枚以上あるかどうかを調べ、2枚以上ある場合に、残りの12枚で面子ができるかを調べればよい。

次に順子の確定であるが、一つの牌の枚数が3枚以外の場合、その3枚以外の牌は必ず順子の一部とならなくてはならない。よって、値の昇順に、3枚以外の牌の数（牌の数を3で割った余り）の分だけ、値、値+1、値+2の牌の枚数を取り去っていけばよい。

最後に残った牌の数が、各値について0または3であれば刻子とすることができるため、そのような場合はOKとして返せばよい。

以下、麻雀の役判定のサイトを参考とした。

【コード】

2019-06-19

AOJ 0042 （A Thief : 泥棒）

AOJ-PCK

【問題】

https://onlinejudge.u-aizu.ac.jp/problems/0042

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0042

【解説】

いわゆる0-1ナップザック問題。

動的計画法にて解いていけばよい。漸化式や解説については、リンク先のwikipediaを参照。

dpテーブル"dp[w]"を用意し、添え字は風呂敷に入っている品物の重さとしている。これを、各品物の数の分だけ操作していく。dpテーブルに入れる値は、品物iの価値を$v_i$、重さを$w_i$とすると、要素jについて、 $$ dp[j] = \max (dp[j], dp[j - w_i] + v_i)　(j - w_i ≧ 0) $$ となる。すなわち、風呂敷にその品物を入れられるだけの重さに余裕があれば、入れる前の価値に品物の価値を加えた値を求め、その値がその重さにおける価値を上回っていれば、値を更新する、ということになる。これを、配列の末尾から先頭に向かって処理していけばよい。

最後に全ての品物に対して処理した結果の配列の最大値をとれば、それが解となる。

配列を操作する場合に昇順で辿ってしまうと、同じ品物を複数入れてしまうことに注意する。

【コード】

2019-06-18

AOJ 0040 （Affine Cipher : アフィン暗号）

AOJ-PCK

【問題】

https://onlinejudge.u-aizu.ac.jp/problems/0040

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0040

【解説】

アフィン暗号を複合する問題。文字$\gamma$について、$F(\gamma) = (\alpha \cdot \gamma + \beta) \bmod 26 $の処理を行っているため、$\{\alpha,\beta\}$を総当たりで試して複合していき、正しく複合されているかを判定すればよい。制約より、$\alpha$は1～26のうち、26と互いに素（最大公約数が1）の数、$\beta$は0～25である。

複合する式については、 $$ F(\gamma) = (\alpha \cdot \gamma + \beta) \bmod 26 $$ であることから、 $$ \gamma = \frac{F(\gamma) + (26 - \beta)}{\alpha} \bmod 26 $$ となる。なお、modの世界では通常の除算ができないため、$\alpha$で割るかわりに$\alpha$の逆元（モジュラ逆数）を掛ける必要がある。また、a=0,b=1・・・とするため、入力した文字コードから"a"に該当する文字コードを引き、処理後に"a"に該当する文字コードを足している。

逆元については、他のプログラミングコンテスト等でも多用するため、ライブラリ化しておくと便利。

ほぼ静的な計画法

競技プログラミングで解いた問題の解法とコードを晒していくページ。ややマイナーなC♯。

AOJ 0047 （Cup Game : カップゲーム）

【問題】

【解説】

【コード】

AOJ 0046 （Differential : 標高差）

【問題】

【解説】

【コード】

AOJ 0045 （Sum and Average : Sum and Average）

【問題】

【解説】

【コード】

AOJ 0044 （Prime Number II : 素数 II）

【問題】

【解説】

【コード】

AOJ 0043 （Puzzle : パズル）

【問題】

【解説】

【コード】

AOJ 0042 （A Thief : 泥棒）

【問題】

【解説】

【コード】

AOJ 0040 （Affine Cipher : アフィン暗号）

【問題】

【解説】

【コード】