エクサウィザーズ 2019
Updated:
Source codes
Solutions
A - Regular Triangle
$A = B = C$ であるかどうかを判定する。
B - Red or Blue
R と B の文字数を数えてどちらが大きいか判定する。
C - Snuke the Wizard
解法
$0$-indexed とする。 $f \colon N \to \mathbb{Z}$ を以下で定める。
$f(n) = $ 最初座標 $n$ にあったゴーレムが全ての呪文を詠唱し終えた後にいる座標。ただし左端から消滅した場合は $-1$ を返し、右端から消滅した場合は $N$ を返すと規約する。
このとき、次式が成立する。
\[ -1 \leq f(0) \leq f(1) \leq \dots \leq f(N - 1) \leq N. \tag{C.1} \]
すなわち相対的な位置関係が逆になることはない。もし逆になることがあるとすると矛盾が導かれる。すぐ証明できるので略。
$f(n)$ の計算にかかる時間は $O(Q)$ であるが、 (C.1) 式があるので、 $f(n) \in N$ となる $n$ の個数は二分探索で $O(\log N)$ 回で求めることができる。よって全体の計算量は $O(Q \log N)$ である。
実装の注意点
string について
string を $2 \times 10^5$ 回も連結するとそれだけで TLE する。 この場合は
char T[200010];
char D[200010];
として、
for (auto i = 0; i < Q; i++)
{
char t, d;
cin >> t >> d;
T[i] = t;
D[i] = d;
}
とした方が安全である。
めぐる式二分探索について
【めぐるのアルゴリズム講座】
— 因幡めぐる@競技プログラミング (@meguru_comp) 2016年2月9日
二分探索（整数）の書き方
難しさ：４ pic.twitter.com/LGLbkS0D7l
ここではかなり使い勝手がいい。ポイントはめぐるちゃんの言っている通りなのだが、あえて補足するならば以下のようになる。
- 二分探索とは $ok$ と $ng$ の境界点を ある 1 つだけ求める 方法である。
- 初期値 $ok$ と $ng$ は 実際は探索されないので番兵で良い 。
今回は後者が有効である。
int ok = N;
int ng = -1;
while (abs(ok - ng) > 1)
{
int t = (ok + ng) / 2;
if (f(t) == -1)
{
ng = t;
}
else
{
ok = t;
}
}
int left = ok;
ポイント
こういう問題は priority queue か二分探索であるような気がする。
D - Modulo Operations
$N!$ 通りをランダムに選んで最後に残った数の確率を有理数で表し、これを $\mathbb{Z} / (10^9 + 7) \mathbb{Z}$ 上で保持することにする。黒板に書かれている数の期待値の $N!$ 倍が答えである。
$dp[i][mask] = mask$ の要素を使い、かつ黒板に $i$ が書かれている確率、
$DP[i] = \sum _ {mask} dp[i][mask]$
と定める。当然 $dp$ は $N \times 2^N$ 通りあるので保持不可能であるが、よく考えると $mask$ を保持する必要がないことが分かる。
まず $S$ は昇順に並んでいると仮定して良い。黒板に $i$ が書かれている時に何が起こっているのか考える。 $S$ の元のうち $i$ より大きいものについてはまとめて扱っても構わない。なぜならそれで $i$ の剰余をとっても $i$ のままであるからである。したがって管理する必要はない。そして $i$ 以下の要素については、必ず未使用である。使用していると黒板に書かれている数字は $i$ 未満になるからである。つまりここから次の本質的な遷移は $i$ 以下の要素に対して等確率で行われるとすれば遷移がまとめられる。
以上を考慮して、 $DP$ について DP をすることができる。初期状態： $DP[X] = 1$, otherwise $DP[i] = 0$. 答え：
\[
N! \times \sum _ {i = 0} ^ N DP[i] \times i.
\]
遷移： $i = N, \dots, 0$ に対し、
\[
A _ i = \{ S _ j \in S \mid S _ j \leq i \},
\]
$K _ i = \sharp A _ i$ とした際に、 $K _ i = 0$ ならば break; 、そうでないならば $S _ j \in A _ i$ に対し、
\[
DP[i \% S _ j] \mathbin{ {+} {=} } \frac{1}{K _ i} DP[i],
\]
そのあと $DP[i] = 0$ とする。
ポイント
やっぱり確率を $\mathbb{Z} / (10^9 + 7) \mathbb{Z}$ で管理するのはわかりやすいなと思った。類題は以下がある。
- AGC030 D - Inversion Sum これも確率の問題だと思うとわかりやすい。
E - Black or White
黒白の順列を $B \times W$ の grid の経路に対応させて考える。 $0$-indexed とする。答えを $ans[k]$ の中に入れるものとする。ここで $ans[k]$ と $ans[k - 1]$ がどのように異なるのかを考える。以下の解説放送の画像参照。ただし $1$-indexed であることに注意。
この grid の下で、 $ans[k]$ とは、ランダムに経路を選んだ際に $k$ 番目の進行方向が下である確率のことである。この確率は、場所ごとに以下のようになる。
- 右端にすでに到達している場合は、確率 $1$ 、
- 下端にすでに到達している場合は、確率 $0$ 、
- その他の点においては $1/2$ 。
そこで $ans[k - 1]$ と $ans[k]$ の違いが生じる場所を考えると、それは以下の $2$ パターンしかないことが分かる。
- $k - 1$ 回目で左端から $1$ つ前まで到達している場合。この場合 $k - 1$ 回目で右を選ぶと、 $k$ 回目では下を選ぶしかない。ゆえに $1/2$ の確率で $1/2 \mapsto 1$ になるので、合計すると $1/4$ だけ $ans[k]$ の方が $ans[k - 1]$ より大きいことが分かる。
- $k - 1$ 回目で下から $1$ つ前まで到達している場合。この場合 $k - 1$ 回目で下を選ぶと、 $k$ 回目では右を選ぶしかない。ゆえに $1/2$ の確率で $1/2 \mapsto 0$ になるので、合計すると $1/4$ だけ $ans[k]$ の方が $ans[k - 1]$ より小さいことが分かる。
上の確率を $q _ k $ 、下の確率を $p _ k$ とすると、次式が成立する。
\[
\begin{align}
p _ k &= \begin{pmatrix} k - 1 \\\ B - 1 \end{pmatrix} \left( \frac{1}{2} \right)^{k - 1}, \\
q _ k &= \begin{pmatrix} k - 1 \\\ W - 1 \end{pmatrix} \left( \frac{1}{2} \right)^{k - 1}.
\end{align}
\]
ただし二項係数は index を外れるときや負のときは $0$ をとると規約する。 $ans$ は以下で与えられる。 $ans[0] = 1/2$, $k = 1, 2, \dots, B + W$ に対し、
\[
ans[k] = ans[k - 1] - \frac{1}{4} p _ k + \frac{1}{4} q _ k.
\]
差分の計算は $O(1)$ でできるので、答えは $O(B + W)$ で求まる。
ポイント
これは本番中にできた。しかし rng さんの解説のようにすっきりとは解けなかった。
- $2$ 種類のものの順列は grid に帰着させる。
- $ans[k]$ と $ans[k - 1]$ の差分だけ更新する。