M-SOLUTIONS プロコンオープン

Updated:

M-SOLUTIONS プロコンオープン

Source codes

Solutions

A - Sum of Interior Angles

$180(N - 2)$ を出力する。

B - Sumo

後ろに o を挿入して $8$ 勝するかどうかを判定する。

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

まず $C = 0$ であるとして考える。 $p = A / (A + B)$ とする。 $q = B / (A + B)$ とする。

$i = 0, \dots, N - 1$ とする。先手が $N$ 回、後手が $i$ 回勝つ場合、最後は先手が勝つので、そこに気をつけると、その期待値は \[ (N + i) p^N q^i \begin{pmatrix} N + i - 1 \\\ i \end{pmatrix} \] とわかる。これの和をとる。先手が $i$ 回、後手が $N$ 回勝つ場合も同様である。

次に $C > 0$ の場合を考える。まず $P = (A + B) / 100$ とする。この時、確率 $P$ のことが起こるまでの期待値を $x$ とすると、今何もない状態から始めると、確率 $P$ で $1$ 回、確率 $(1 - P)$ で $(1 + x)$ 回かかると期待されるので、次式が成立する。 \[ x = P \cdot 1 + (1 - P) (1 + x) \] となるので全体の答えは $x = 1 / P$ 倍になる。

D - Maximum Sum of Minimum

まず $\{ c _ i \}$ が降順になっていると仮定する。辺を降順にならべているとする。このとき $i$ 本の辺に書かれているコストは $c _ i$ 以下である。これが 自明な上界 である。

この自明な上界は達成される。 具体的には $c _ 0, \dots, c _ i$ の頂点が連結になるように割り当てていけばよろしい。よってこれが最大値である。

E - Product of Arithmetic Progression

$P = 10^6 + 3$ とする。 $\mathbb{Z} / P \mathbb{Z}$ は体である。 $d = 0$ のとき答えは $x^n$ である。

まず仮に $d = 1$ のときを考える。 $x + (n - 1) \geq P$ のとき、答えは $0$ である。その他は $(x + n - 1)! / (x - 1)!$ である。

次に $d \geq 2$ のときを考える。このとき、 $d = 1$ に帰着できる。 \[ \begin{align} x (x + d) \dots (x + (n - 1)d) &= d^n \frac{x}{d} \left( \frac{x}{d} + 1 \right) \dots \left( \frac{x}{d} + (n - 1) \right) \\
&= d^n \cdot (x/d + n - 1)! / (x/d - 1)!. \end{align} \] これを先ほどと同様に求めればよろしい。

F - Random Tournament

TLE 解

$0$-indexed とする。まず入力を持っておく。

$W[i][j] = i$ が $j$ に勝つ場合は true, そうでない場合は false とする。

DP による。まず右と左の戦いは独立に行われることに注意する。すると DP テーブルを右と左でわけて持てばよろしい。

$dp _ L[b][a] = [a, b]$ で戦った時に $a$ が勝ち残れる場合は true, そうでない場合は false とする。 index が逆になっているのは後のことを考えてそうしてある。
$dp _ R[a][b] = [a, b]$ で戦った時に $b$ が勝ち残れる場合は true, そうでない場合は false とする。

初期状態: $i = 0, \dots, N$ に対し $dp _ L[i][i] = dp _ R[i][i] = $ true. 答え: \[ \sharp \{ i \in N \mid dp _ R[0][i] \land dp _ L[N - 1][i] \}. \] 遷移:長さが短い方から埋めていく必要がある。 $n = 1, \dots, N - 1$ に対し、 $a = 0, \dots, N - n - 1$ に対し、 $b = a + n$ とすると、 \[ \begin{align} dp _ L[b][a] &= (\exists c \in N)(dp _ L[b][c] \land dp _ R[a + 1][c] \land W[a][c]), \\
dp _ R[a][b] &= (\exists c \in N)(dp _ L[b - 1][c] \land dp _ R[a][c] \land W[b][c]). \end{align} \]

上の方は、 $[a, b]$ での戦いで $a$ が優勝するための必要十分条件は、 $c \in [a + 1, b]$ が存在し、 $c$ がその中で優勝し(つまり $dp _ L[b][c] \land dp _ R[a - 1][c]$)、さらに $c$ に $a$ が勝つことである(つまり $W[a][c]$)、と言っている。下の方は、同様に $[a, b]$ での戦いで $b$ が優勝するための必要十分条件は、 $c \in [a, b - 1]$ が存在し、 $c$ がその中で優勝し(つまり $dp _ L[b - 1][c] \land dp _ R[a][c]$)、さらに $c$ に $b$ が勝つことである(つまり $W[b][c]$)、ということである。

これを愚直に実装すればいいが、このままいくと $O(N^3)$ になりわずかに TLE になる。

模範解答

以上は bool で $2$ 次元配列を持っていたが、これを bitset<2010> の $1$ 次元配列で持つことにする。 これで約 $64$ 倍高速化ができるそうである。

私は一度も使ったことがないので以下詳細に書く。使う際は #include<bitset> としておく。上の true を $1$ とし、 false を $0$ とする。

宣言

bitset<2010> で型を宣言し、 $1$ つ目の index は配列、 $2$ つ目の index は bit にアクセスする。

bitset<2010> dp_L[2010];
bitset<2010> dp_R[2010];
bitset<2010> W[2010];

入力・初期状態

宣言したら $0$ が立っていると思えばいいらしい。 true を入れたいところに $1$ を立たせる。

      if (S[j] == '0')
      {
        W[j][i] = 1;
      }
      else
      {
        W[i][j] = 1;
      }
  for (auto i = 0; i < N; i++)
  {
    dp_L[i][i] = 1;
    dp_R[i][i] = 1;
  }

遷移

普通の bit 演算だと思って & で繋げる。そして $1$ つでも立っているかどうかつまり $(\exists c \in N)$ の部分は .any() とすればよろしい。

  for (auto n = 1; n < N; n++)
  {
    for (auto a = 0; a + n < N; a++)
    {
      int b = a + n;
      if ((dp_R[a + 1] & dp_L[b] & W[a]).any())
      {
        dp_L[b][a] = 1;
      }
      if ((dp_R[a] & dp_L[b - 1] & W[b]).any())
      {
        dp_R[a][b] = 1;
      }
    }
  }

解答

立っている $1$ の数をカウントするためには .count() とする。

  int ans = (dp_R[0] & dp_L[N - 1]).count();
  cout << ans << endl;

ポイント

初めて bitset なるものを知った。

Others

今日はめちゃくちゃひどかったですね。まぁ明日もまた頑張りましょう。