たれながし

色々雑多に書きます

緑diff精進その4 (1/26)

解いた問題

ABC045 C - Many Formulas
ABC102 C - Linear Approximation
AGC005 A - STring
APC001 B - Two Arrays
ABC114 C - 755
ARC140 B - Shorten ARC

ABC045 C - Many Formulas

感想 (解答中に考えたこと)

evalで解けてしまいそうだが、本質じゃないので使わない。
各数字がどの桁で幾つ現れるかを考えれば良い。
基本的にどの数字も $n$ 桁目は $2^{|S|-n-3}\left( = C(n)\right)$ 個現れる。ただし $C(n)$ を現れる回数とする。
また各数字が使える回数は数式のパターンの数分なので $2^{|S|-1}$ で、 $S$ にて $k$ 桁目であった数字が $k+1$ 桁目以降に現れるはずがない。よって $k$ 桁目の数字を $S_{k}$ として、その寄与は $\sum_{n=1}^{k-1}S_{k}\times 10^{n-1}\times C(n)\;\left(k\geq 2\right)$ 。最後に $S_{k}\times\left(C(k) - \sum_{n=1}^{k-1} C(n)\right)\times 10^{k-1}$ の分を補正すれば良い。

提出コード

まぁbit全探索で良い atcoder.jp

ABC102 C - Linear Approximation

感想 (解答中に考えたこと)

絶対値の和の最小化なので、どうせ中央値あたりを考えれば良さそう。
$\sum |A_{i} - b - i| = \sum | B_{i} - b |$ のように変形すれば、 $B_{i}$ の中央値を求めれば終わり。

提出コード

なんと、 $B_{i}$ のソートを忘れていたらしく……(3WA) しかし数列の長さが偶数のケースを無視していたが、通ってしまった。 atcoder.jp

AGC005 A - STring

感想 (解答中に考えたこと)

左から消去っていうのが効いてきそう？とりあえずランレングス圧縮する。
左端の文字がTである場合は無視すれば良いので、Sから始まる文字列のみ考えれば良い。
個Sが連なっているものを、Tが連なっているものをとする。
- $S(n)T(m)\;\left(n\leq m\right)$ であれば、消去操作は $n$ 回
- $S(n)T(m)\;\left(n\geq m\right)$ であれば、消去操作は $m$ 回で、次のSのまとまりの個数に $n-m$ を加える。
$|X| - 消去回数\times 2$ が答えになる。

提出コード

左から捜索して特定の文字列になったら削除はStackで管理、めちゃ典型だ……。 atcoder.jp

APC001 B - Two Arrays

感想 (解答中に考えたこと)

APCなんてものがあるんですね……。で表されるからなす数列を考える。ここで操作は以下のように言い換えられる。
- $i, j \in \left[1, N\right]$ を選び、 $c_{i}$ に2を加算。 $c_{j}$ に-1を加算。
- 上の操作によって全ての $c_{i}$ を $0$ にすることが目標。
このことから $x=-\sum_{i=1}^{N}c_{i}$ としたとき、 $x$ が操作回数になる。これ以上操作をすると $C$ の和が1以上になるので一致することはなくなる。同様に $x$ 未満の操作回数でも一致しない。
$C$ の各要素から最短で $0$ にする方法を考える。また、 $+2$ する回数と $-1$ する回数を分けてカウントする。
$c_{i}$ が正数であるならば、 $-1$ をその数だけ繰り返せば良い。
$c_{i}$ が負数であり、偶数であるなら $+2$ をその数/2回繰り返す。奇数ならば(その数+1)/2回 $+2$ を繰り返した後に $-1$ を1回行う。
最後にとの回数およびから判定をする。
- $-1$ の回数が $+2$ よりも大きければNo
- $+2$ の回数が $-1$ よりも大きい場合、余剰分を $+2$ を1回と $+1$ を1回で繰り返せば $C$ の要素は全て0になる必要条件を満たし、操作回数が $x$ と同じになればYes
- その他回数が同じだった場合や $x$ が負数の場合の処理を書けば良い

提出コード

ABC114 C - 755

感想 (解答中に考えたこと)

上位の桁を固定しながら和を取るのが簡単そうだが、同様のもので桁DPがある。練習がてら桁DPで解いてみる。
$dp(i, j, k):=$ 上から $i$ 桁目を見た時、数字の使われ方が状態 $j$ (ビット)である場合の数。ただし $k$ は上位 $i$ 桁目まで一致しているかどうかのbool値。
上位の桁を0埋めする場合が考えられ、また3057のように途中に0を入れてはいけないので、bitで探索するときも0のみ特別に扱う必要がある。
あとは $i$ 桁目の数字と $j$ の状態から丁寧に丁寧に丁寧に状態遷移を実装してあげれば良い。

提出コード

苦しすぎた…… atcoder.jp

ARC140 B - Shorten ARC

感想 (解答中に考えたこと)

ARCであればどのタイミングで操作してもよく、AARCCであれば奇数回目で操作すると偶数回目でACまで変化できて嬉しい。つまりAARCCとARCの個数がわかればよいのでは？ -> WA
考えてみたがわからんので解説をチラ見。なるほど、A...ARC...Cを常に奇数回目で操作するようにすれば、両端のAあるいはCの個数の小さい数ぶん操作が可能になる。
つまりランレングス圧縮する過程でA...ARC...Cの塊の情報を整理すれば見通しが良くなりそう。
あとは奇数回目であればARC以外のものを優先して操作し、偶数回目であればARCを優先して操作することが必要になる。
実装方法に迷ったが、操作回数は高々 $N$ 回で抑えられるだろう(操作することにより、1文字あるいは2文字消去なので)。なのでpriority_queueを使って愚直に勘定するのが良い。

提出コード