M-SOLUTIONS Programming Contest C～E 問題メモ

M-SOLUTIONS Programming Contest

• M-SOLUTIONS プロコンオープン 解説放送 - YouTube

C - Best-of-(2n-1)

• 2人がゲームをする
• ゲームは、以下の勝負を繰り返すことで行う
  • 勝負の勝敗は独立に、Aさんが $A\%$ で勝ち、Bさんが $B\%$ で勝ち、$C\%$ で引き分ける
• 先にどちらかが $N$ 勝したらゲームを終了する時、終了するまでに行う勝負の回数の期待値を求めよ
• 答えは、$\frac{P}{Q}$ という分数で表せるとき、$PQ^{-1} \mod{10^9+7}$ の整数で答えよ
• $1 \le N \le 10^5$
• $0 \le A,B,C \le 100$
• $1 \le A+B$
• $A+B+C=100$

素直にやるなら $k \times (k回で勝負が決する確率)$ の合計で表せる。

しかし、勝負をして必ずどちらかが勝つならいいが、引き分けという結果があるせいで理論上は無限回でも勝負ができてしまうため、上記では上手くいかない。

そんな時、一度引き分けは設定に無いものと考えて、こう考えることができる。

• 引き分けが無い場合の勝率に置き換える
  • $A\% ← A/(A+B)$
  • $B\% ← B/(A+B)$
• 引き分けが無い場合、勝負は有限回で終わるので、計算できる
• 「勝負を行って、1回引き分け以外の結果となる」までの回数期待値は $\frac{100}{A+B}$
• よって、引き分けを無視して得た結果に上記を乗算すればよい

勝者をAと仮定する。Bも同様に計算すればよい。

Bの勝利数をkとすると、$0 \le k \le N-1$ である。$N-1+k$ 回までにAが $N-1$ 勝、Bが$k$ 勝した後、$N+k$ 回目にAが勝ち、ゲームが終わる。

よって確率は、${}_{N+k-1}C_{k}(\frac{A}{A+B})^{N-1}(\frac{B}{A+B})^k \times \frac{A}{A+B}$

期待値はこれに $N+k$ をかけたものである。

これを $k=0..N-1$ まで計算すればよい。

D - Maximum Sum of Minimum

• $N$ 頂点 $1,2,...,N$ からなる木、$i$ 番目の辺は $a_i$ と $b_i$ を結ぶ
• 正の整数 $c_1,c_2,...,c_N$
• 各頂点に、$c_i$ を1つずつ書き込んだ時、木のスコアを以下で計算する
  • 各辺につき、2つの端点に書き込まれた整数のうち、小さい方をその辺のスコアとする
  • 全辺のスコアの総和を木のスコアとする
• 木のスコアの最大値と、それを達成する書き込み方の一例を示せ
• $1 \le N \le 10^4$
• $1 \le c_i \le 10^5$

なるべく大きいスコアをたくさんの辺に与えたい。$c_i$ の中で小さい整数をどう処理するかが鍵となる。

$c_i$ の中で一番小さな整数をある頂点に書き込むと、それに接続する辺のスコアは必ずその値となる。 次数の大きな頂点に書き込むと非効率だが、どこに書こうと最低1箇所はその最小値のスコアの辺はできてしまう。

1つの辺にしか接続していない葉頂点に一番小さな整数を書き込むようにすると、最小値となる辺数を1本と最低限にできる。

その辺のもう一方の端点は何でもよいため、一度最小値を書き込んだ頂点は木から外して考えることができる。

よって再帰的に「どれでもいいので葉頂点の1つに最小値を書き込み、木から外す」ことを繰り返すと、最大値を達成できる。

E - Product of Arithmetic Progression

• 以下のクエリが $Q$ 個与えられるため、全てに答えよ
  • 等差数列 $x, x+d, x+2d, ..., x+(n-1)d$ が、$x,d,n$ の3数で与えられる
  • この数列の総乗を、$\mod{10^6+3}$ で求めよ
• $1 \le Q \le 10^5$
• $0 \le x_i,d_i \le 10^6+2$
• $1 \le n \le 10^9$

等差数列の積とか、いかにも数学ネタで扱いそうな内容なのでググる。 すると、Yahoo知恵袋 Wikipediaに答えが見つかる。

$\displaystyle ((\frac{x}{d}) \times (\frac{x}{d}+1) \times (\frac{x}{d}+2) \times ... \times (\frac{x}{d}+(n-1))) \times d^n$ の形に変形できる。

よって、公差1の場合（つまり階乗）とその逆数だけ事前計算しておけば、後はその結果を使うだけで $O(1)$ なり $O(\log{何か})$ あたりで答えが出せる。

小数が出てくるのは困るが（別に小数のまま計算しても答えは出るのだが、事前計算ができない）、 modの世界では $d$ の逆数が定義できれば、$d$ で割る代わりに $d^{-1}$ をかけることで、整数のまま扱える。 定義できる条件は $d$ と $M(=10^6+3)$が互いに素であることなので、制約より必ず定義できる。

ただし、コーナーケースとして、以下のケースを除いておく。

• $x=0$ の時、項に0が含まれるため、総乗も0
• $d=0$ の時、単に$x^n$

また、$n$ の制約が $10^9$ なので大きすぎて事前計算に時間がかかりすぎるような気もするが、実は大きすぎても項の中に $10^6+3$ の倍数が必ず含まれてしまうので0になる。

具体的に何項目かは $x,d$ の値によるが、最大でも $10^6+2$ 項の中には含まれる。 これは、$kd \mod{M}$ が、$d$ と $M$ が互いに素であれば $k=0～M-1$ まで全て異なった値を取るため、 その中の最低1つには $x$ を足すと $M$ の倍数になる値が含まれるためである。

実際には、$M - xd^{-1}$ 項目の次で $M$ の倍数になるので、$n_i$ がそれより大きいと0を出力する。

以上の例外に当てはまらなければ、

$\displaystyle \frac{(xd^{-1}+n-1)!}{(xd^{-1}-1)!} \times d^n \mod{M}$ で答えが出せる。

F - Random Tournament