TOYPRO解説記事 - Don't quarrel(300点)
1.概要
競技プログラミングのサイト「TOYPRO」の300点問題、Don't quarrelの解説をします！
問題はコチラ！(https://app.toy-pro.net/user/questions/183)
2.問題
まーくんとくーちゃんは、お菓子が大好きです。
ここに、
二人は、じゃんけんをしてほしいお菓子をとりあっていくことにしました。
取り合うとは次のような行動を繰り返すことです。
・二人でじゃんけんをして、勝ったほうが欲しいお菓子を取り、その次に負けたほうが欲しいお菓子を取る。
しかし、くーちゃんはまーくんにいじわるをしたいので、欲しいお菓子が重複する場合は、そのお菓子を優先的に選びます。
まーくんが欲しいお菓子とくーちゃんが欲しいお菓子が与えられるので、
まーくんが欲しいお菓子をすべて手に入れられる確率(%)を求めてください。
なお、まーくんもクーちゃんと同様に欲しいお菓子が重複する場合は、そのお菓子を優先的に選びます。
制約
※
入力例-1
N = 5
M = [2, 3, 4]
K = [1, 4, 5]
出力例-1
50
入力例-2
N = 11
M = [1, 2, 3, 5, 6, 7]
K = [1, 3, 4, 9, 10, 11]
出力例-2
0
3.解説
さてさて、今回は確率の問題です。確率といえば、かなり難しいイメージを持っている方も多いと思いますが実は簡単に解ける場合もあります。
今回の場合も簡単に解けます。
問題をよく読むと、条件分岐で簡単に解くことができることがわかると思います。
まず、欲しいお菓子が1つもかぶっていない場合、つまりかぶっているお菓子が0個の場合を考えます。これは簡単で、100%の確率でまーくんが欲しいお菓子をすべて手に入れられます。
次に、欲しいお菓子が1つだけかぶっている場合を考えます。
これは、最初のジャンケンにだけ勝てばいいので、ジャンケンで勝つ確率=50%ですべて手に入れられます。
最後に、欲しいお菓子が2つ以上かぶっている場合です。
この場合は、絶対にくーちゃんが「まーくんの欲しいお菓子」の一つをとってしまいます。
これで、すべての場合を網羅することができました。
一見、かなり難しい実装になりそうですが、サンプルケースを手で試したりすると簡単に解くことができることがよくあるので、根気よく考えましょう！
4.結び
ToyProの問題、「Don't quarrel」の解説でした！
他にも面白い問題がたくさんあるので、是非ご利用ください！！！
Discussion