AtCoder Beginner Contest 150 - 情報妖精の競プロ日記

AtCoder Beginner Contest 150(ABC150)に参加しました！

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 150
rated ~1999
2020/1/10(金) 21:00 ～ 22:40 (100分)
100-200-300-400-500-600 (6問)
ペナルティ: 5分

方針

全完

A - 500 Yen Coins

問題文

高橋君は $500$ 円玉を $K$ 枚持っています。これらの総額が $X$ 円以上である場合はYesを、そうでない場合はNoを出力してください。
制約

$1 \leq K \leq 100$

$1 \leq X \leq 10^5$

解法

持っているお金は $500K$ 円なので、これが $X$ 以上か判定すれば良いです。

感想

最初の問題なので、やるだけです。

B - Fusing Slimes

問題文

英大文字のみからなる長さ $N$ の文字列 $S$ があります。
$S$ の連続する部分列としてABCがいくつ含まれるかを求めてください。
制約

$1 \leq N \leq 50$

$S$ は英大文字からなる。

解法

殆どの標準ライブラリには、部分文字列を取り出す関数や文字列の比較を行う関数が備わっています。
例えばJavaの場合、String.substring(i - 2, i + 1);でi-2文字目からi文字目までの文字列を切り出すことができ、String.equals("ABC")でその文字列がABCと一致するか比較することができます。
従って、後はこの開始点iを $2$ から $N$ まで動かせば良く、これはfor文などで実現できます。

感想

標準ライブラリを知っておくと便利なことが多いので、調べて損は無いと思います。
そもそもそのライブラリが標準に入っている理由は、需要が高かったからなのですから。

C - Count Order

問題文

大きさ $N$ の順列 ( $(1,~2,~\cdots,~N)$ を並び替えてできる数列) $P,~Q$ があります。
大きさ $N$ の順列は $N!$ 通り考えられます。このうち、 $P$ が辞書順で $a$ 番目に小さく、 $Q$ が辞書順で $b$ 番目に小さいとして、 $|a - b|$ を求めてください。
注記
$2$ つの数列 $X,~Y$ について、ある整数 $k$ が存在して $X_i = Y_i~(1 \leq i < k)$ かつ $X_k < Y_k$ が成り立つとき、 $X$ は $Y$ より辞書順で小さいと定義されます。
制約

$2 \leq N \leq 8$

$P,~Q$ は大きさ $N$ の順列である。

入力は全て整数である。

解法

nextPermutationというアルゴリズムが存在します。
詳しくは調べていただけると分かるのですが、ある列の辞書順で次の列を求め、また辞書順で次の列が存在するか判定してくれるアルゴリズムです。
これを用いると、それぞれの順列が辞書順で最も大きい順列から何個離れているかを求めることができるので、後は差を取ると判定できます。

感想

これの上位版の問題として、辞書順で何番目？が存在します。
こちらの問題は順当な考察から解くので、もし良ければこちらもやってみてください。

D - Semi Common Multiple

問題文

長さ $N$ の偶数からなる正の整数列 $A= {a_1,a_2,...,a_N}$ と、整数 $M$ が与えられます。
任意の $k(1 \leq k \leq N)$ に対して以下の条件を満たす正の整数 $X$ を $A$ の「半公倍数」と定義します。

$X= a_k \times (p+0.5)$ を満たす負でない整数 $p$ が存在する。

$1$ 以上 $M$ 以下の整数のうちの $A$ の半公倍数の個数を求めてください。
制約

$1 \leq N \leq 10^5$

$1 \leq M \leq 10^9$

$2 \leq a_i \leq 10^9$

$a_i$ は偶数である。

入力は全て整数である。

解法

制約より $a_i$ は偶数なので、 $b_i=2a_i$ と定義します。
この時、 $X= a_k \times (p+0.5) = 2b_k \times (p + 0.5) = b_k \times (2p + 1)$ と変形され、問題は全て整数で表すことができます。
この時、 $\frac{X}{b_k} = 2p + 1$ と表せることから、 $X$ は任意の $b_k$ の倍数である、すなわち $b_1, \cdots, b_N$ の公倍数であることが分かります。
$b_1, \cdots, b_N$ の最小公倍数を $LCM$ とすると、 $X$ は整数 $c$ を用いて $X=c \times LCM$ と表すことができます。
また、 $X = c \times LCM = b_k \times (2p + 1)$ より、 $c \times \frac{LCM}{b_k}$ は奇数である必要があります。
ここで $\frac{LCM}{b_k}$ が偶数であるならば任意の正の整数を掛けても偶数なので、条件を満たす $X$ は存在しません。
逆に任意の $k$ について $\frac{LCM}{b_k}$ が奇数であるならば $c$ が奇数の時に条件を満たします。
従って、 $X=LCM, 3 \times LCM, ..., (2d - 1) \times LCM \leq M < (2d + 1) \times LCM$ を満たすような整数 $d$ が答えとなり、これは式変形すれば求まります。
$LCM$ を求める際、最小公倍数がオーバーフローする可能性には気を付けましょう。
例えば実装の工夫として、最小公倍数を求める場合には2項の最小公倍数の公式 $lcm(x, y)=\frac{xy}{gcd(x, y)}$ を用いて $LCM=lcm(b_1, lcm(b_2, \cdots, lcm(b_{N-1}, b_N)))$ と解くと思いますが、この際の各 $lcm(x,y)$ は高々2乗に収まる、すなわち $10^{18}$ 程度に収まることを利用して、もし $lcm(x, y) > M$ ならば $lcm(x, y)=M+1$ とするとオーバーフローを防げます。

感想

重いし罠があるし400点問題としては難しい分類の問題です。
ついでに言うとテストケースも誤っているし、正直言って辛いね……。

E - Change a Little Bit

問題文

$0, 1$ からなる長さ $N$ の異なる $2$ つの数列 $S, T$ に対し、関数 $f(S, T)$ を以下のように定めます。

$S$ に対し以下の操作を繰り返して $T$ と等しくすることを考える。このとき行う操作のコストの和として考えられる最小の値が $f(S, T)$ である。

$S_i$ を ( $0$ から $1$ 、もしくは $1$ から $0$ に) 変更する。この操作のコストは、変更の直前に $S_j \neq T_j (1 \leq j \leq N)$ であったような整数 $j$ の個数を $D$ として、 $D \times C_i$ である。

$0, 1$ からなる長さ $N$ の異なる $2$ つの数列の組 $(S, T)$ は $2^N \times (2^N - 1)$ 通り考えられます。これらすべてに対する $f(S, T)$ の和を $10^9+7$ で割った余りを計算してください。
制約

$1 \leq N \leq 2 \times 10^5$

$1 \leq C_i \leq 10^9$

入力は全て整数である

解法

まず、同じ数列の組が存在したとしても答えに影響はしない(そのような数列のコストは $0$ である)ので、同じ数列の組を許容します。
また、数列 $S'=0,0,\cdots,0$ とし、数列 $T'$ の $i$ 番目の項を $S_i$ と $T_i$ の値が異なるなら $1$ 、そうでないなら $0$ と定めた新しい数列を考えると、元の数列から新しい数列へは一対一に対応するので、元の問題の代わりに数列 $S', T'$ について解いても一般性を失いません。
この時、数列 $S'$ は常に $0$ であることから、ある数列 $(S', T')$ に対応する数列 $(S, T)$ は全部で $2^N$ 個あることが分かります。
従って、各数列 $T'$ について解き、その答えを最終的に $2^N$ 倍すると元の問題の答えになることが分かります。
さて、ある数列 $T'$ についてある数列 $p$ が存在して $T'_{p_1}, \cdots, T'_{p_n}$ が $1$ であり、この $p$ の順に操作するとします。
この時のコストは $\sum_{i=1}^{n}{i \times C_{p_i}}$ であることから、 $p$ の順番は $C_i$ の大きい順にすることが最適であることが分かります。
よって、まず $C$ を降順ソートしておくものとします。
次に、 $T'$ について各 $C_i$ が何回コストとして数えられるかを考えます。
まず $T'_i$ が $1$ であるような組合せは明らかに $2^{N-1}$ 通りあります。
また、 $T'_i$ が $1$ であり、かつ $T'_j (j < i)$ が $1$ であるような組合せ(先に $j$ を取るために $i$ が複数回数えられる)は各 $j$ について $2^{N-2}$ 通りあります。
従って、各 $i$ について $C_i$ は $(i+1) \times 2^{N-2}$ 通りあることが分かるので、最終的なコストは $2^N \times \sum_{i=1}^{N} C_i \times (i + 1) \times 2^{N-2} = 4^{N-1} \sum_{i=1}^{N} (i + 1) C_i$ です。

感想

期待値の線形性など、何が独立に数え上げられるかを知っていると割と自明に見える問題だと思います。
この手の言い換えは高校数学でも頻出なので、もし良ければ数Aなどを勉強してみると良いのかもしれません。

F - Xor Shift

問題文

非負整数からなる長さ $N$ の数列 $a=\{a_0,\ldots,a_{N-1}\}$ と $b=\{b_0,\ldots,b_{N-1}\}$ が与えられます。
すぬけ君は $0 \leq k < N$ を満たす整数 $k$ と、 $0$ 以上の整数 $x$ を決めて、新しく長さ $N$ の数列 $a'=\{a_0',\ldots,a_{N-1}'\}$ を次のようにして作ります。

$a_i'= a_{i+k \mod N}\ XOR \ x$

$a'$ が $b$ と等しくなるような $(k,x)$ の組を全て求めてください。
制約

$1 \leq N \leq 2 \times 10^5$

$0 \leq a_i,b_i < 2^{30}$

入力中のすべての値は整数である。