【Python】AtCoder Grand Contest 041の復習

スポンサーリンク
AtCoder
スポンサーリンク

AtCoder Grand Contest 041の復習を兼ねて、問題Aと問題Bの解法をまとめています。

スポンサーリンク

問題A

問題はこちら

二人の卓球選手が同じ卓球台で出会うための最小の試合回数を求めます。

卓球選手は、勝ったら左へ、負けたら右へ移動します。ただし、1番目で勝った場合、N番目で負けた場合は、その位置に留まります。

ここから、二人の卓球選手の間の距離の偶奇で場合わけして考えます。

間の距離が偶数の場合(下の図の場合、B-A=2)、

Aが負け、Bが勝つごとに、間の距離が2縮まります。

間の距離が奇数の場合(下の図の場合、B-A=1)、

お互いに近づく方向に進んでも、同じ台になることはありません。そのため、「1番目の台で勝つ」または「N番目の台で負ける」ことで、間の距離を偶数にする必要があります。

  1. 「Aが1番目の台に移動(移動回数:A-1)」または「BがN番目の台に移動(移動回数:N-B)」。どちらか移動回数が少ない方で。
  2. 端の台で留まる。(移動回数:1、間の距離:B-A-1)
  3. お互いに近づく方向に移動(移動回数:(B-A-1)/2 )

問題B

問題はこちら

まず、スコアの順に問題を降順に並べ替えます。

この時、P番目までの問題は採用される可能性がありますが、P+1番目以降は採用の可能性がわかりません。

P <= X <=N であるX番目の問題を考えます。もし、Xにジャッジ全員が投票した時(Ax+M)、XのスコアがP番目のスコア以上になれば、Xは採用されます。

Ax+MがP番目のスコア以上になるために、ジャッジが投票して良い場所と票数は下の図のようになります。

したがって、Ax+MがP番目になるために、投票できる票数の最大値は

(P-1)*M + (N-(X+1))*M + (上の図のピンク色の区間の総和)+ M

となります。

これが、票の総数であるM*Vを超えないことが、X番目の問題が採用される条件です。

このような、Xを探索するため、PからNまでの区間で二分探索をします。

タイトルとURLをコピーしました