AtCoder Grand Contest 012 C: Tautonym Puzzle
http://agc012.contest.atcoder.jp/tasks/agc012_c
解法
空の列も良い文字列だとみなす。
順列 A, B があって、AとBを連結したもの(A+Bと表す)のパターン数が X だったとする。
- A←A+[foo], B←B+[foo] とすると A+B のパターン数は 2X になる。
- A←A+[foo], B←[foo]+B とすると A+B のパターン数は X+1 になる。
これを利用することで 4log(N) 個の要素で構築できる。
AtCoder Grand Contest 012 B: Splatter Painting
http://agc012.contest.atcoder.jp/tasks/agc012_b
解法
di が小さいのが鍵に見える。
dp[v][i] を「頂点 v から距離 i の範囲を dp[v][i] で塗りつぶせ」と考えると上手くいく。命令を小さい距離へどんどん伝搬していくイメージ。
補足
ある頂点から距離 d の範囲を塗りつぶすという命令は、距離 d-1 の塗りつぶし命令に分解できる。
頂点 v から距離 d の塗りつぶし命令が複数あるならば、最も新しい命令以外は無視しても良い。無視することにより計算量は O(d(n+m)) になる。
AtCoder Grand Contest 012 A: AtCoder Group Contest
http://agc012.contest.atcoder.jp/tasks/agc012_a
解法
入力を昇順にソートして考える。
適当な戦略を取ってみる。先頭から3つずつペアにしていくのはどうだろう。
_o__o__o__o_ 000111222333
oになっているのが中央値。
これは改善ができる。
_o__o___o_o_ 000111232233
改善の雰囲気から最適構造が見える。
____o_o_o_o_ 012300112233
CSAcademy Special MVC
editorial読んで概要はすぐに理解できたけど、cactus上のDPを整理するのに手間取った。この回難しすぎる。
https://csacademy.com/contest/archive/#task/special-mvc/
続きを読む