Hello 2019 (Codeforces) 参加記録＆解説（A～D, F）

Codeforces

2019年最初のコンテストはABCDFの5完で111位！幸先いいですね。

A. Gennady and a Card Game

Codeforces

問題概要

2文字の文字列でトランプのカードを表す。1文字目がランク、2文字目がスートに対応する。

場にあるカードが与えられ、さらに5枚の手札が与えられる。場にあるカードに対して、ランクまたはスートの少なくとも一方が一致するカードをプレイすることができる。

手札の中にプレイできるカードがあるかどうか判定せよ。

制約

省略

解法

手札を順に場のカードと比較し、1文字目または2文字目が一致するものがあるかを判定すればよいです。

ACコード

Codeforces

B. Petr and a Combination Lock

Codeforces

問題概要

$n$ 個の角度 $a_{1}, ..., a_{n}$ が度数法で与えられる。それぞれの角度に対して左回り/右回りを自由に選んで、1周あたり360度のダイヤルを回す。操作が全て終わった時にダイヤルが最初と同じ位置にあるような回し方が可能であるかどうか判定せよ。

制約

$1 \le n \le 15$
$1 \le a_{i} \le 180$

解法

左回りをプラス、右回りをマイナスとして角度を符号付きで全て合計したときに、その値が360度の倍数になっていればよいです。

制約より $O(2^{n})$ が十分間に合うので、回す方向を全探索してそれぞれ計算すればよいです。

ACコード

Codeforces

私の実装はbit全探索です。hackを狙ってコードを読んでいたら、再帰関数での実装も多く見られました。

C. Yuhao and a Parenthesis

Codeforces

問題概要

括弧だけで構成された文字列が $n$ 個与えられる。文字列2つをペアにして正しい括弧列をできるだけ多く作りたい。1つの文字列が2つ以上のペアに属することはできない。

作ることができるペアの最大数を求めよ。

制約

$1 \le n \le 10^{5}$
全ての文字数の合計は $5 \times 10^{5}$ を超えない

解法

正しい括弧列の条件は、( を+1、) を-1とする累積和を取ったときに、

文字列全体の合計がちょうど0である。
頭から見て、どの時点でも累積和が0以上である。

を満たすことです。

このことを考えると、2つの文字列をペアにして正しい括弧列とするためには、ある非負整数 $k$ に対して

前半の文字列
- 合計が $k$ である。
- 頭から見て、どの時点でも累積和が0以上である。
後半の文字列
- 合計が $-k$ である。
- 頭から見て、どの時点でも累積和が $-k$ 以上である。

をそれぞれ満たす必要があります。

あとはそれぞれの文字列に対して累積和の最小値と合計を計算して、「合計が $x$ で、最小値の条件を満たすものの個数」を整数 $x$ ごとに集計します。その値を $mp\lbrack x \rbrack$ とすると、正整数 $k \gt 0$ について正しい括弧列は $\min(mp\lbrack k \rbrack, mp\lbrack -k \rbrack)$ 個作れます。合計0の文字列は合計0の文字列とペアになるので、 $\lfloor\frac{mp\lbrack 0 \rbrack}{2}\rfloor$ 個作れます。これらを全て加算すれば答えが求められます。

ACコード

Codeforces

D. Makoto and a Blackboard

Codeforces

問題概要

整数 $v$ の初期値を $n$ とする。整数 $v$ に対して、以下の操作を $k$ 回行う。

その時点での $v$ の約数の中からランダムに1つ選ぶ。どの約数が選ばれる確率も等しいものとする。 $v$ をその約数で置き換える。

操作が終わった後の $v$ の値の期待値を求めよ。答えは有理数となるため、その値を既約分数 $\frac{P}{Q}$ としたときの $PQ^{-1} \mod 10^{9}+7$ の値を出力せよ。

制約

$1 \le n \le 10^{15}$
$1 \le k \le 10^{4}$

解法

「約数を等確率で1つ選ぶ」という操作をしたときに、 $v$ のそれぞれの素因数の個数がどうなるか考えます。 $v$ にある素因数 $p$ が $m$ 個含まれているとすると、操作後の素因数 $p$ の個数は $0, 1, ..., m$ 個の中から等確率に1つ選ばれると考えることができます。そしてこの事象は素因数ごとに独立であるとみなすことができます。

そのため、まず $n$ を素因数分解してしまい、素因数ごとに考えます。ある素因数 $p$ についてだけ注目すると、「 $i$ 回操作後に素因数 $p$ が $j$ 個含まれている確率」を $dp_{p}\lbrack i \rbrack\lbrack j \rbrack$ とするようなDPを考えることができます。

遷移は、 $dp_{p}\lbrack i \rbrack\lbrack j \rbrack$ に $(j+1)^{-1}$ を掛けたものを $dp_{p}\lbrack i+1 \rbrack\lbrack j_{2} \rbrack (j_{2} = 0, ..., m)$ に加算することで計算できます。「 $k$ 回の操作後に素因数 $p$ が $j$ 個含まれている確率」、すなわち $dp_{p}\lbrack k \rbrack\lbrack j \rbrack$ を以降 $P\lbrack p, j\rbrack$ と表記します。

これを全ての素因数について計算すると、全ての $n$ の約数について $v$ が最後にその数になっている確率を計算できます。ちょっと数式がごちゃごちゃするので、仮に $n$ の相異なる素因数が $p_{1}, p_{2}$ の2種類だとして、それぞれの個数を $m_{1}, m_{2}$ とします。

このとき $n$ の約数は $p_{1}^{j_{1}}p_{2}^{j_{2}}$ と表現できて、最後にその数が残る確率は $P\lbrack p_{1}, j_{1}\rbrack P\lbrack p_{2}, j_{2}\rbrack$ となります。求めたいのは期待値なので、 $p_{1}^{j_{1}}p_{2}^{j_{2}} P\lbrack p_{1}, j_{1}\rbrack P\lbrack p_{2}, j_{2}\rbrack$ を全て合計すればよいです。

これらを約数ごとに全て計算してもよいですが、さらに簡単にする方法があります。求めたい値は $p_{1}^{j_{1}}p_{2}^{j_{2}} P\lbrack p_{1}, j_{1}\rbrack P\lbrack p_{2}, j_{2}\rbrack$ を全ての $j_{1} = 0, ..., m_{1}$ と $j_{2} = 0, ..., m_{2}$ の組み合わせについて合計したものですが、これを分配法則を使ってまとめると

$(p_{1}^{0}P\lbrack p_{1}, 0\rbrack + p_{1}^{1}P\lbrack p_{1}, 1\rbrack + \cdots + p_{1}^{m_{1}}P\lbrack p_{1}, m_{1}\rbrack) \times (p_{2}^{0}P\lbrack p_{2}, 0\rbrack + p_{2}^{1}P\lbrack p_{2}, 1\rbrack + \cdots + p_{2}^{m_{2}}P\lbrack p_{2}, m_{2}\rbrack)$

という形になり、 $p_{1}$ と $p_{2}$ を完全に分離できます。そのためそれぞれで値を求めておいて、最後に掛け算する方法でも期待値を求めることができます。

ここまでの話は素因数の種類数が2個でない場合でも成り立ちます。それぞれの素因数ごとに値を求めて全部掛け算すればよいです。

ACコード

（分配法則不使用）Codeforces
（分配法則使用）Codeforces

分配法則使用コードのほうが圧倒的にシンプルなのでオススメです。

F. Alex and a TV Show

Codeforces

問題概要

$1, ..., n$ までの番号が付けられた多重集合がある。始めはどの集合も空である。

以下の4種類のクエリを $q$ 個処理せよ。

1 x v 番号 $x$ の集合を $v$ 1つだけの集合に置き換える。
2 x y z 番号 $x$ の集合を、番号 $y, z$ の集合の和集合に置き換える。
3 x y z 番号 $x$ の集合を、番号 $y, z$ の集合の「直積集合」に置き換える。ただしここでは要素同士の組の代わりに、それらの要素の最大公約数を直積集合の要素とする。
4 x v 番号 $x$ に含まれる要素 $v$ の個数の偶奇を出力する。

制約

$1 \le n \le 10^{5}$
$1 \le q \le 10^{6}$
クエリ1, 4について、 $1 \le v \le 7000$

解法

それぞれの集合の状態として、単純に各値の個数や偶奇を持っていてはクエリの処理が間に合いません。特に最大公約数を求める処理が厄介なので、これを処理しやすいような状態の持ち方を考える必要があります。

状態 $state\lbrack x \rbrack\lbrack v \rbrack$ を、「集合 $x$ に含まれる要素のうち、 $v$ を約数に持つ要素の個数の偶奇」とするような状態を持ちます。このときクエリ2は $v$ ごとに要素数を足せば良いので、偶奇をビットで管理している場合はXORで計算できます。