外部サイトへ移動します

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

別タブで開く

解説

K - Nyaxas Hold'em

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529、trueryob

配点 400 点

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

解説

わりとねこくんが持っている数字 2 の枚数を XX、対戦回数を M=N/5M=N/5 とします。

強さ ii の手札に勝つためには、数字 2 が少なくとも i+1i+1 枚必要です。したがって、相手の弱い手札から順に勝てるだけ勝つことを考えます。

強さ ii の手札の個数を CiC_i とし、i=0,1,…,4i=0,1,\ldots,4 の順に処理します。このとき、

k=min⁡(Ci,⌊Xi+1⌋,M)k=\min\left(C_i,\left\lfloor\frac{X}{i+1}\right\rfloor,M\right)

回勝つことができるので、答えに kk を加え、

X←X−k(i+1),M←M−kX\gets X-k(i+1),\qquad M\gets M-k

と更新します。

弱い手札ほど勝つために必要な数字 2 の枚数が少ないため、この貪欲法は最適です。また、残ったトランプは各手札が 55 枚になるように自由に配っても、確保した勝利数は減少しません。

数字 2 の枚数を数えるのに O(N)O(N) 時間、その後の処理に O(1)O(1) 時間かかるため、全体の時間計算量は O(N)O(N) です。

ユーザー解説

ユーザー解説を書く

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