AtCoder AGC028 振り返り - かしのブログ

2018.10.13 21:00~のAtCoder AGC028に参加
結果はABの2完。

A - Two Abbreviations

与えられた2つの文字列を元に、条件を満たす文字列の最小の長さを出力する問題。
条件は

答えの文字列の長さ $L$ はそれぞれの文字列の長さの整数倍
答えの文字列を $N$ 個に区切った $i$ 個目の先頭は $a_i$
答えの文字列を $M$ 個に区切った $i$ 個目の先頭は $b_i$

と言い換えられる。

一つ目の条件より、 $L$ は $N、M$ の最小公倍数とわかる。証明は以下、ただし文字列は $0$ 文字目からカウントする（問題文は1文字目からカウントしている）
ある答えの文字列の長さを $nL$ とする。答えの文字列を $N$ 個に区切ったとき、その $i$ 個目の先頭は $a_i$ で、それぞれの文字列の長さは $n$ の倍数になっている。同様に、答えの文字列を $M$ 個に区切ったとき、その $i$ 個目の先頭は $b_i$ で、それぞれの文字列の長さも $n$ の倍数になっている。 $\frac{nL}{N}*i = \frac{nL}{M}*j (0 \le \frac{nL}{N}*i, \frac{nL}{M}*j < nL)$ ならば $a_i = b_j$ なら有効な文字列である。ここで、 $L$ は $NとM$ の倍数なので、ある整数 $n$ で有効な文字列ならば $n$ 1以上の全ての整数に対して成り立つ。
以上

なるべく短い文字列を出力したいので答えは最小公倍数、もしくは無効な文字列の-1になる。
次に有効かどうかの判定をする。
$\frac{L}{N}*i = \frac{L}{M}*j (0 \le \frac{L}{N}*i, \frac{L}{M}*j < L)$ ならば $a_i = b_j$ ならいいので、for文でチェックすればいい。無効な組み合わせを見つけたら-1、それがないなら最小公倍数が答え。（ $NとM$ が互いに素なら判定の必要はない）

https://beta.atcoder.jp/contests/agc028/submissions/3393088

B - Removing Blocks

全通りのシミュレーションをすると $O(N!N^2)$ とかかかるので、効率化する必要がある。
具体的には、
　　　ある $i$ 個目のブロックのポイントが加算されるのは何回か
を求めて足し合わせる。
　 $i$ 個目のブロックから $n$ 個離れたブロックが消えたときに、 $i$ 個目のブロックのポイントが加算される必要十分条件はその間のブロックが全て消されてないこと。そこだけを抜き取って場合の数を数えると $n!$ 。また、その他の順番はどうでもいいので、 $(N-n-1)!$ 通り。ポイントに関係する $n+1$ 個のブロックと関係ない $N-n-1$ のブロックの消す順番は独立していていいので、 $N-n$ 箇所に $n+1$ を重複込みで選択して挿入するので組み合わせ方は $_{N-n}H_{n+1}$ 。結局、 $n$ 個離れたブロックが消えた時に加算する必要がある回数は $c(n) = n!(N-n-1)!_{N-n}H_{n+1}$ 。
　x個目のブロックのポイントの加算回数は $\sum_{k=0}^{N-1} c(|x-k|)$ 。これを係数として、部分和を更新しながら $a_i$ に足していくと答えが求められる。