M-SOLUTIONS プロコンオープン
Updated:
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
今日はめちゃくちゃひどかったですね。まぁ明日もまた頑張りましょう。