Codeforces Round 784 (Div. 4) E-H を解いた記録
E – 2-Letter Strings
問題の概要
長さ $2$ の文字列が $n$ 個与えられる．各文字列は $a$ から $k$ までの英小文字からなる．
整数の組 $(i, j)$ のうち， $i$ 番目の文字列と $j$ 番目の文字列がちょうど1箇所だけ異なるようなものはいくつあるか？
ただし， $i \lt j$ とする．
制約
- $1 \leq n \leq 10^{5}$
解法
$cnt[x][y]$ : 1文字目が $x$ で2文字目が $y$ な文字列の個数
ただし， $x, y$ は実際には整数値とする．具体的には， $’a’ \to 0, ‘b’ \to 1, ‘c’ \to 2, \dots$ とする．
という配列を持ち，条件を満たすような整数の組を数え上げましょう．
実装例
F – Eating Candies
問題の概要
$n$ 個のキャンディが1列に並んでいる．左から $i$ 個目のキャンディの重さは $w_{i}$ である．
Alice は左端から， Bob は右端から順にキャンディを食べる．このとき，あるキャンディを食べずに次のキャンディを食べることは許されない．
Alice と Bob がそれぞれ食べたキャンディの重さの総和が等しくなるようにするとき，二人が食べられるキャンディの個数の合計を最大化せよ．
制約
- $1 \leq n \leq 2 \times 10^{5}$
- $1 \leq w_{i} \leq 10^{4}$
- 入力はすべて整数
解法
左端から何個キャンディを食べるかを全探索します．
$$ memo[\text{右端から食べたキャンディの重さの総和}] = \text{右端から食べたキャンディの個数} $$
という連想配列を事前に作っておけば， $O(n \log n)$ などで全探索できます．
実装例
G – Fall Down
問題の概要
$n$ 行 $m$ 列のグリッドが与えられる．グリッドには3種類のマスがある．
- 空っぽのマス
- 石があるマス
- 障害物があるマス
石は床（グリッドの一番下），障害物，または他の動けなくなった石にぶつかるまで下に落ち続ける．すべての石が落ちたあとのグリッドの状態を出力せよ．
制約
- $1 \leq n, m \leq 2 \times 50$
解法
一番下の列から順に，上から石が落ちてくるかを愚直に確認すればよいです． $n, m$ が小さいので，愚直にやっても十分間に合います．
実装例
H – Maximal AND
問題の概要
要素数 $n$ の数列 $a$ と非負整数 $k$ が与えられる．数列 $a$ に対して，下記の操作を $k$ 回まで行える．
- 数列の任意の1要素を選び，その要素の $j$ 番目のビットを1にする．ただし， $0 \leq j \leq 30$ である．
$a_{1} AND a_{2} AND \dots AND a_{n}$ を最大化せよ．
制約
- $1 \leq n \leq 2 \times 10^{5}$
- $0 \leq k \leq 10^{9}$
- $0 \leq a_{i} \lt 2^{31}$
解法
上位ビットから考えます．最終的な答えの上位ビットを1にできるのであれば，下位ビットで頑張るよりも上位ビットを1にするほうが明らかにお得です．
そこで，30番目のビットから0番目のビットまでについて，数列 $a$ の全要素のビットを残り操作回数で1にできるかをチェックすれば良いです．