AtCoder Regular Contest 117参加記（～C問題）

600点問題が解けると嬉しい！！
f:id:mmnkblog:20210418231705p:plain

A - God Sequence

各要素が正の整数である二つの数列 $a, b$ を考えることにする。この時、数列 $a$ の要素の総和と数列 $b$ の要素の総和が等しくなれば良い。 $A=B$ のとき明らかに、 $a_i = b_i$ とすることで条件を満たすことができる。

$A\lt B$ （数列 $a$ より数列 $b$ の方が長い）と仮定する。（逆ならswapする）
この時数列 $b$ の要素を $b_i = i$ となるように決めると、数列 $a$ の最後の要素を除いて $a_i = i$ とし、最後の要素を $a_A = \sum_{k=A}^{B} k$ とすることで条件を満たすことができる。最後の要素で数値を調整するイメージ。

計算量は $O(A+B)$ 。

B - ARC Wrecker

階数が同じビルがあった場合、どんな操作をしてもそれらのビルの階数は等しいままである。よって回数が同じビルはひとまとめにしておく。以降、すべての $A_i$ に重複が無いものとして考える。ついでに数列 $A$ を昇順に並び替えておく。

$X$ として選ぶ数字は数列 $A$ の要素のどれかとしてよい。また、 $X=A_i$ としたとき、少なくとも $A_i$ の値は $1$ 減るため、 $A_i$ は最大でも $A_i$ 回しか選べない。

実験するとわかるが、操作の順番は結果に関係しない。つまり「各 $i$ について、 $X=A_i$ を何回選ぶか」という情報だけわかればよい。さらに、 $X=A_i$ とした場合、 $i \le j$ を満たすすべての $j$ について、 $A_j$ の値は $1$ 減る。先ほど昇順にソートした理由はこれで、 $A_i$ が小さい順から「何回 $A_i$ を選ぶか」を決めていくことで数え上げることができる。

$X$ に $A_i$ を $k$ 回選ぶとすると、 $A_i$ と $A_{i+1}$ は共に $k$ ずつ減る。 $A_i$ の値が変わらないような $X$ に $A_{i+1}$ を選ぶ回数の最大値は、 $(A_{i+1} - k) - (A_i - k) + 1 = A_{i+1} - A_i + 1$ 回である。この数値は $k$ によらず一定である。
よって $(A_1 + 1)\times \prod_{ i = 1 }^{N-1} (A_{i+1} - A_i + 1)$ が答え。計算量はソートがボトルネックとなり、 $O(N\log N)$ 。

C - Tricolor Pyramid

文字を選ぶ操作をなにかの演算として表現したい。各文字を $0, 1, 2$ で置き換えて演算結果を表にまとめる。二つの数を $a, b$ としたとき、演算結果は $-(a+b)\bmod 3$ と表せる。

左から $i$ 番目の整数を $a_i$ とすると、最上段の整数に含まれる各 $a_i$ の個数は二項係数を用いて表せる。具体的に、最上段の整数は $(-1)^{N-1} \times \sum_{i=1}^{N} ({}_{N-1} \mathrm{ C }_i \times a_i) \bmod 3$ である。なので素直にこの式を計算すればよいが、 $\bmod 3$ 上の ${}_{N-1} \mathrm{ C }_i$ の値を求める方法がわからなかった。

http://www.junko-k.com/collo/collo29.htm
上のサイトを見ながら考えたところ、 $N-1$ を $3^k$ で割った余りで場合分けすることで $O(\log N)$ で求められることに気が付いた。なのでその場合分けを丁寧に書いて計算し解答。計算量は $O(N\log N)$ 。