AGC046 参加メモ - tinumu's reminder

Cが解けてなかったらBを解きに行かなかったので激冷えするところだった。今回はB,Cをちゃんと通せたので嬉しい 259th Perf=2271 1870->1917(+47)

A - Takahashikun, The Strider

普通に頭のいい方法が思いつかなかったので本番ではシミュレーションした(doubleでいろいろ)。
最初の位置を $A$ , $1$ 回進んだ位置を $B$ として $|AO| = |BO| \wedge \angle AOB = X$ になるような $O$ を取ると、どうやら $O$ を中心とした長さ $|AO|$ の円周上に全て乗るみたい。次移動するところも、 $O$ を経由した角度が $X$ になるようにやっていけば自然となる。実際書いてみると証明っぽいことが出来る(角度を追ってみるとたしかにそうなってることが分かる)。
とすると、同じ角度のところに戻ればいいだけなので、 $kX \equiv 0 ( \mod 360 )$ になるような最小の自然数 $k$ を見つけて終わり。

B - Extension

こういう感じの問題だと、 $dp_{a,b}$ : 現在のマス目の大きさが縦 $a$ マス, 横 $b$ マス( $(a, b)$ と略す) のときの塗られ方の個数とかが求まれば嬉しそう
まあ、たとえ引数が増えたとしても適宜そこは増やすと良さそう

漸化式を求めていきたい。
$dp_{a, b}$ を作るのに必要なものは、 $(a-k, b)$ ( $k$ は自然数 ) から縦に伸ばして行かないとありえない通りと、 $(a, b-m)$ ( $m$ は自然数 ) から横に伸ばしていかないとありえない通りと、どのように伸ばしても作れる通りの $3$ 種類である。

ここで、 $dp_{a-1, b}$ は縦に伸ばさないとありえない通りを全て持っており、 $dp_{a, b-1}$ は横に伸ばさないとありえない通りを全て持っている。
そのため、 $dp_{a-1, b} \times b$ , $dp_{a, b-1} \times a$ たちを足す。すると、どのように伸ばしても作れる通りが $2$ 回加算されてしまうので困る。
どのように伸ばしても作れる通りというのは $(a-1, b-1)$ から縦横に伸ばした時に一番右下のマスを使わないようにする通りと同義であるため、漸化式は、
$dp_{a,b} = dp_{a-1, b} \times b + dp_{a, b-1} \times a + dp_{a-1, b-1} \times (a-1) \times (b-1)$
となり、これを $(C, D)$ までやる。
すると、答えは $dp_{C, D}$ となる。
これはもちろん計算量は $\mathrm{O}(CD)$ であり、十分間に合う。

C - Shift

文字列の区別の仕方が変わらない別の文字列の表現形式を考えてみる。
$0$ の数を $A$ 個とする。
このとき $0$ で文字列を区切って $A+1$ 個の区間に分けて区間 $i$ に $1$ がそれぞれ何個ずつ入っているか $B_i$ を持つような表現にする。
すると、 $1$ 回の操作が $B_j \gt 0$ であるような $j$ を $B_j - 1$ にして $i \lt j$ である $B_i$ のどこかを $B_i+1$ すると言ったような操作になって単純になる。

これで数字を $K$ 回以下左に $1$ こずつ移動させられるときにできるパターン数を数え上げするだけの問題になる。
これは反転させた配列を右に $K$ 回以下移動させる処理と同じであるため、今回はそっちを考える(やりやすいので)。

ここで考えたいのは、値を「置く」という処理を繰り返すということである。
値を置いて、実際に構成しながらパターン数を求めれば答えに間違いはなさそう。
ここで必要な情報は現在位置と現在位置より左の $1$ を何個置いてないか、何回操作を行ったかという情報である。
しかし、一回ある場所に「置いた」時にそこから「取り出す」操作は禁物で、これをすると、同じパターンを重複して数え上げてしまう(構成したものを戻してしまうことになるので、パターン数が増えることは分かるだろう)。
そのため、すでにその位置に要素を一度でも置いたかという状態も持っておく必要がある。

ここでこのようなDPを考える。
$dp_{i,j,k,l}$ : 現在 $i$ 個目までの要素を見ていて、 $i$ よりも左にある $1$ を $j$ 個置いておらず、 $k$ 回操作をすでに行っていて、区間 $i$ に対してすでに数字を一度でも置いたか $l$ が分かるときのパターン数

遷移では次の要素に移るときに元からあった要素を何個見過ごすかを決定する。見過ごした数だけ $k$ が減る。
置く/置かないの操作は $i$ 内で行ってしまって、置くとき、 $j$ が $j-1$ になる。同時に $l = 1$ になる。

$l = 1$ になっていると、元からあった要素を見過ごすことが出来ないのでそのパターンを取り除く必要がある。

見過ごす数を決めるのを for文でやっても、ならされるので、計算量は $\mathrm{O}(N^3)$ となっているはず。
実際、そのforをimosを使って無くしてみたけど、全然早くならなかったため多分同じ計算量なんだと思う。
あと、 $K$ は $N$ 回より多く使わないので予め K = min(K, N); とかしておくと楽だと思う。

感想

Dも時間があれば挑戦してみたい。
数え上げは表現形式を問題に沿うようにつくり上げるのがかなり大事なんじゃないかなと思った。