解説
わりとねこくんが持っている数字 2 の枚数を 、対戦回数を とします。
強さ の手札に勝つためには、数字 2 が少なくとも 枚必要です。したがって、相手の弱い手札から順に勝てるだけ勝つことを考えます。
強さ の手札の個数を とし、 の順に処理します。このとき、
回勝つことができるので、答えに を加え、
と更新します。
弱い手札ほど勝つために必要な数字 2 の枚数が少ないため、この貪欲法は最適です。また、残ったトランプは各手札が 枚になるように自由に配っても、確保した勝利数は減少しません。
数字 2 の枚数を数えるのに 時間、その後の処理に 時間かかるため、全体の時間計算量は です。
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。