ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC046(ARC062) D - AtCoDeerくんと変なじゃんけん / AtCoDeer and Rock-Paper

条件の作成

問題
 提出コード

解法

自分はシミュレーションをしました。
相手が $p$ を出してきたときは、必ずこちらも $p$ をだして相手にポイントが渡らないようにし、そして余った $p$ を出せる回数で得点を稼ぐ、といった方針です。
ということで、まずは相手の $p$ の回数をカウントします。これを $P$ とします。
そして、前からシミュレーションします。今自分が $p$ を連続で出すことができる回数を $G$ とします。今見ているターンで、相手が

$p$ を出した場合
あいこにするために、自分も $p$ を出します。 $G$ と $P$ のカウントを1つ減らします。
$g$ を出した場合
$P \lt G$ だった場合、得点に1追加し、 $G$ を1減らします。
それ以外のパターンでは、 $G$ のカウントを1増やします。

このシミュレーションを最後まで行えば、答えが求まります。

ですが、実際はこのあたりのシミュレーションはどうでもよくて、 $N/2 - P$ が答えになります。
最悪のパターンである、自分がすべてグーを出した場合の得点は $-P$ であり、ここから、自分がパーを出す回数を1増やすと、常に得点は1増えるため、パーを出せるだけ出すのが最善であり、最終的に上の数式が答えになります。
と解説に書いてありました。

感想

C問題同様、最終的な答えは綺麗な式になりますが、結局自分はシミュレーションをしていました。D問題は、式を出すよりもシミュレーションをした方がおそらくはやく解けるので、まぁどちらでもよかったかなと思っています。
思考の過程としては、まず相手に得点を取られないようにするにはどうすればいいか、を考え、そのためには相手がパーを出したタイミングで常に自分がパーを出せばいいことがわかり、そのうえで自分が得点を重ねていくためにどのような動きをすればいいか？を考えると、上のようなシミュレーションにたどり着きました。