外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

P - Nyahjong

作成者 nekooooooo、siooisi、jammy、trueryob

テスター siooisi、tau0529、trueryob

配点 425 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

K=(A+B)/14K=(A+B)/14、D=∣A−7K∣D=|A-7K| とします。

役が成立するセットに含まれる猫牌の個数は 55 以上 99 以下です。したがって、D>2KD>2K ならば配分は不可能なので、-1 を出力します。

猫牌が 77 個より多いセットと少ないセットが存在する場合、両者の猫牌の個数を 77 に近づけるように交換しても、得点は減少しません。

よって、すべてのセットの牌の偏りが同じ方向である場合のみを考えれば十分です。

x,y,zx,y,z 点のセットの個数をそれぞれ p,q,rp,q,r とすると、

p+q+r=K,q+2r=Dp+q+r=K,\qquad q+2r=D

が成り立ちます。したがって、

p=K−D+r,q=D−2rp=K-D+r,\qquad q=D-2r

であり、p,q,rp,q,r が非負整数である条件は

max⁡(0,D−K)≤r≤⌊D2⌋\max(0,D-K)\le r\le\left\lfloor\frac D2\right\rfloor

となります。

合計得点は

px+qy+rz=(K−D)x+Dy+r(x−2y+z)\begin{aligned} px+qy+rz &=(K-D)x+Dy\\ &\quad+r(x-2y+z) \end{aligned}

です。

これは rr の一次式なので、rr の取りうる最小値と最大値について合計得点を計算し、大きい方を出力すればよいです。

以上より、時間計算量・空間計算量ともに O(1)O(1) でこの問題を解くことができました。

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。