目次
AtCoder Regular Contest 153 B,C,E問題メモ
B - Grid Rotations
問題
- $H \times W$ のグリッドにそれぞれ文字 $C_{i,j}$ が書かれている
- $Q$ 回、以下の操作を行う
- $a_i,b_i$ が与えられる
- グリッドを、$a_i$ 行目と $a_i+1$ 行目の間の線、$b_i$ 列目と $b_i+1$ 列目の間の線で十字に分割する
- 分割された4つの長方形領域をそれぞれ180度回転する
- 最終的なグリッドに書かれた文字を出力せよ
- $HW \le 5 \times 10^5$
- $1 \le Q \le 2 \times 10^5$
解法
タテヨコは独立に考えていい。
最初の $i$ 行目が最終的に $r_i$ 行目、$j$ 列目が $c_j$ 列目に移るなら、答えの $(r_i,c_j)$ のマスにあるのは $C_{i,j}$ である。
なので、1次元のクエリ操作を2回考えればよい。
縦方向($H$ 行)の操作を考えるとする。
愚直に考えると区間反転をいっぱいしなきゃいけなくて、そんなこと短時間でできるの? となる。
だが、今回は「2つに区切った区間をそれぞれまるっと反転」と決まっているので、実験してみると良い性質がすぐ見えてくる。
最初 1 2 3 4 5 6 7 |-------|-----| a=4 1回目 4 3 2 1 7 6 5 |---|---------| a=2 2回目 3 4 5 6 7 1 2 |-----------|-| a=6 3回目 1 7 6 5 4 3 2 |-------|-----| a=4 4回目 5 6 7 1 2 3 4
結局、1回の操作では $1,2,...,N$ の並びが逆順+転回を起こす。
特に2回の操作をまとめると、$a_1→a_2$ の順で操作が発生すると $(a_1-a_2)\mod{H}$ だけ転回する。
よって、2個ずつ、いくつ転回したかを追っていって、$Q$ が奇数なら最後の操作だけ愚直にやればよい。
C - ± Increasing Sequence
問題
- $-1$ または $1$ からなる数列 $A=(A_1,...,A_N)$ が与えられる
- 以下の条件を全て満たす数列 $x=(x_1,...,x_N)$ を構築できるか判定し、可能なら一例を挙げよ
- $|x_i| \le 10^{12}$
- 狭義単調増加、つまり $x_i \lt x_{i+1}$
- $A_i \times x_i$ の $i=1~N$ にわたる総和が $0$
- $1 \le N \le 2 \times 10^5$
解法
符号が $A_i$ によって反転されうるため、$A_ix_i$ の正負が入り交じる。
総和を特定の1つとかある範囲で調整する、ということを考える際、 狭義単調増加は置ける値の範囲が $i$ ごとに変わるため扱いにくくて、できれば広義単調増加で考えたい。
最初に $x'=(1,2,3,...,N)$ と仮決めして、そこからの差分 $y$ を考えると、$y$ は広義単調増加であれば良くなる。
よって、$x'$ をそのようにした際の $A_ix'_i$ の総和を $S$ とする。
A -1 1 -1 -1 1 -1 x' 1 2 3 4 5 6 ---------------------- -1 2 -3 -4 5 -6 → S = -7
ここで、たとえば $S$ が負で、$A_1=-1$ だったとき、$y_1$ は好きなだけ減らせるので、逆に総和は $S$ から好きなだけ増やせることになる。($10^{12}$ という制約はあるが、一端無視して)
A -1 1 -1 -1 1 -1 ---------------------- x' 1 2 3 4 5 6 y -7 0 0 0 0 0 x -6 2 3 4 5 6 ---------------------- 6 2 -3 -4 5 -6 → S = 0
また、同様に $S$ が負で、$A_N=1$ だったとき、$y_N$ は好きなだけ増やせるので、同様に $S$ から好きに増やせる。
$S$ が正の時は逆に、$A_1=1$ または $A_N=-1$ なら総和を好きに減らせる。
じゃあ、そうでない時は?
$y$ には、先頭からある範囲までに一定値を減じる、または末尾からある範囲に一定値を加えてもよい。
たとえば $S$ が負($-k$)なら、$y_1~y_j$ に一斉に一定値を減じたとき総和が $k$ 増加してくれればよいので、$A_1~A_j$ の総和が負(特に微調整を考えると $-1$)ならよいことになる。
よって、$A_i$ の先頭or末尾からの累積和を取っていって、
- $S$ が負なら
- ①先頭からの累積和で、総和が $-1$ になるところ
- ②末尾からの累積和で、総和が $+1$ になるところ
- いずれかを見つけ、その範囲の $y$ に①なら $S$ を加算、②なら $S$ を減算
- $S$ が正なら
- ③先頭からの累積和で、総和が $+1$ になるところ
- ④末尾からの累積和で、総和が $-1$ になるところ
- いずれかを見つけ、その範囲の $y$ に①なら $S$ を減算、②なら $S$ を加算
すれば、調整が可能となる。
(最初に述べた、先頭・末尾の1項だけで調整する操作も、この処理にまとめられる)
$S \neq 0$ で、そのような箇所が全く登場しないとき(-1と+1が、良い括弧列となっているとき)は、調整ができず不可能。
で、最後にこれが $10^{12}$ を超えないかだが、
- $S$ は、最大 $\dfrac{N(N+1)}{2} \le 約 2 \times 10^{10}$ で、$\pm S$ が $y_i$ の範囲
- $x'$ の最大値は $2 \times 10^5$
- よって $x=x'+y$ の絶対値は $10^{11}$ を超えない
ので大丈夫と分かる。
E - Deque Minimization
問題
- '1'~'9'からなる文字列 $X$ に対し、以下を考える
- $X$ に以下の操作を行い、文字列 $S$ を得る
- $S$ を空文字列で初期化する
- $X_1,X_2,...,X_N$ の順に、$S$ の先頭または末尾に挿入する($X_i$ は $X$ の $i$ 文字目)
- この操作により得ることができる $S$ のうち、整数としてみたときに最小のものを $f(X)$ とする
- '1'~'9'からなる文字列 $Y$ が与えられるので、$f(X)=Y$ となるような $X$ の個数を $\mod{998244353}$ で求めよ
- $1 \le |Y| \le 200000$
解法
$f(X)$ を構成するための操作
$X_1$ はまぁそのまま挿入するとして、最小にするなら下記のようにすればよい。
- $X_i$ ($i \ge 2$)を $S$ に挿入するとき、その時点の $S$ の先頭を $S_1$ として、
- $S_1 \ge X_i$ なら、$X_i$ を先頭に挿入
- $S_1 \lt X_i$ なら、$X_i$ を末尾に挿入
$S_1=X_i$ の場合も本当に先頭でいいのか? と思うが、上記の方針をとる以上、
- 暫定の $S$ が全て同じ文字なら、先頭と末尾どちらに挿入しても変わらない
- 重複を除くため、先頭に挿入することで統一する
- $S$ が全て同じでないなら、どこかではじめて $S_1$ と異なる文字 $c$ が出てくる
- この $c$ は、必ず $S_1$ より大きい
- $c$ が $S_1$ より小さくて、$S_1$ より後に挿入されたなら、先頭に来ているはず
- $c$ が $S_1$ より小さくて、$S_1$ より前に挿入されたなら、$S_1$ の方が後に来ているはず
- よって $X_i$ は先頭に挿入し、$S_1$ が続く長さを長くした方が良い
また、$S=11233$ を作れるけど、途中段階では敢えて $S=32131$ みたいにすることで、最終的には $11233$ としたときより $S$ を小さくできる、みたいなことは起こらない。
$11233$ にしようと $32131$ にしようと、これ以降、何をどのような順で前・後ろに挿入可能かは全く同条件であり、
(同じ並び)11233(同じ並び) (同じ並び)32131(同じ並び)
なら確実に前者の方が小さい。その時々で最小となるように前・後ろのどちらに挿入するかを決めていってよい。
よって、$X$ が決まっているなら、そこから $f(X)$ を作る操作は意外と単純である。
先頭を固定した場合の数
先頭要素 $X_1$ が $Y$ の何文字目にあたるか($Y$ がどこから生成されていったか)を固定する。
$Y_i$ から生成されたと決め打つと、そこから後は左右に広がっていったことになるので、
- $Y_{i-1}→Y_{i-2}→...→Y_2→Y_1$
- $Y_{i+1}→Y_{i+2}→...→Y_N$
$X_2$ 以降の要素の並び順は、上記のような2つの列をマージしたものに限定される。
(マージ:ここでは、列の中での順序は保たれるように、2つを1つにまとめる操作を指す)
その上で、いくつかの制約がある。
先頭から昇順が続く範囲しか $X_1$ にできない
以下のような時に、3を最初に置くことはできない。
Y: 1 2 4 5 [3] 4 6 ...
3を最初に置いた後に5を挿入したとすると、その5をわざわざ前に持ってこないと この $Y$ は作れないが、$f(X)$ を作る操作に違反する。
上記の例なら、先頭の4つ 1,2,4,5 が、$X_1$ となり得る範囲となる。
置く順序の制約
もし、長さ $n$ と $m$ の2列を単純にマージするなら、 場合の数は ${}_{n+m}C_{n}$ で求められるが、そう単純でもない。
前に置かれるべき数が、誤って後に置かれることは基本的にないが、
後に置かれるべき数は、それ以前に自身より小さい値が前に置かれていないと、前に置かれてしまう。
そうなるとより小さい $f(X)$ が作れるような、数え上げの対象ではない $X$ となってしまう。
以下の2通りの場合に注意する。(①は、ちゃんと考えれば②にまとめられるかもしれないが、分けて考えた方がわかりやすい)
- ①同じ要素が連続している箇所を先頭とする場合
- ②後に置かれるべき数の列の中で、これまでより小さい値が出てくる場合
今、$i=6,X_1=5$ を先頭に持ってくるとき、どうなるか考える。
i: 1 2 3 4 5 6 7 8 9 10 11 Y: 1 2 2 3 5 [5] 5 3 4 4 2
$X_2$ 以降は、このような2列のマージとなる。
- 前に置かれる 5→3→2→2→1
- 後に置かれる 5→3→4→4→2
次に来るのはいずれでも $5$ だが、$5$ が来ると、$f(X)$ の構築方法から考えるとこれは前に置かれることになる。
よって、$X_2$ には、前に置かれる方の5しか来てはいけないことになる。
次も同様で、(最終的に $i=5,6$ に収まるべき)'55' がある状態に(最終的に $i=7$ に来るべき)'5'が来たら、 これは前の方に置かれてしまうのでダメ。ここも前に置かれる方の3しか来れない。
暫定S: 3 5 5 残り列 前に置かれる 2→2→1 後に置かれる 5→3→4→4→2
$S$ の先頭が3になってはじめて、これ以降の5は後に置くべきとなったので、 $X_4$ には前に置かれる'2'も後に置かれるべき'5'も採用できる。
①の制約は、「同じ要素が連続している箇所を先頭とする場合は、その中の末尾以外は、自身より前の、より小さい値が1個置かれるまでは、前にしか置けない」という制約となる。
これにより、たとえば 1233[355555]566… という並びでは、 「ある数字の連続箇所の末尾 (3)」と「次の数字の連続箇所の末尾以外 (55555)」において、 それを先頭とした場合に実質的に考慮すべき「前に置かれるべき数の列」が同一となる。 (3→3→2→1)
また特に、$Y$ の先頭要素が連続していた場合は、その中の末尾のみ、先頭とすることができる。
Y: 1111112233... ~~~~~ 先頭にはできない
例に戻って、続けて 5 が置かれた場合の続きを考える。
暫定S: 3 5 5 5 残り列 前に置かれる 2→2→1 後に置かれる 3→4→4→2
ここでもまた、次に後に置かれるべき'3'が来てしまうと前に置かれてしまうので、'2'が先に置かれる必要がある。
同様に、(しばらく進めて)後に置かれるべき列の最後の'2'も、前に置かれるべき'1'の後に置かれる必要がある。
これが②の制約で、「後に置かれるべき値が置かれるときには、先に、より小さい値が前に置かれていないといけない」となる。
ただし、いくつかの要所さえクリアすれば、要所以外は必然的に条件を満たすことが多い。
たとえば後に置かれるべき2つの'4'は、その前に既に'3'が置かれているので、 先頭は2以下となっていることがわかっているため、勝手に条件はクリアしている。
要所となり得るのは、「後に置かれるべき列」の中でも 「これまでに出てきたどの値より小さい値がはじめて出てきた時(狭義単調減少)」なので、 特に値の範囲が1~9である本問題においては、たかだか7個である。
制約の列挙方法としては、例えば、以下のようにすればよい。
$Y$ の中で昇順が保たれる範囲を $Y_{Asc}$、それ以降を $Y_{NotAsc}$ とする。
$Y_{NotAsc}$ の先頭から累積minを取りながら、累積minを更新する要素 $Y_j$ を探す。
$Y_j$ に対し、$Y_j-1$ 以下の要素が $Y_{Asc}$ 中で最後に出てくるのが $Y_i$ だったとすると、
「$Y_j$ が置かれる前に $Y_i$ が置かれなくてはいけない」という制約が見つけられる。
ただし、それより前に見つかった制約と $Y_i$ が同じであれば、無視してよい。
また、$Y_{NotAsc}$ の中に $Y_1$ より小さい値が出てきたら、
そいつを前に置かれることが阻止できないので、そのような $Y$ が $f(X)$ となるような $X$ は0個となる。
(これは最初に確認して例外処理してしまうのが、混乱しなくてよい)
先ほどからの例において、前後に置かれるべき列に②の制約を追加すると以下のようになる。
前に置かれる 2→2→1 ↓ ↘ 後に置かれる 3→4→4→2
具体的な数え上げ方法
先頭を固定して、マージするべき前後の列と制約も定まった。これをマージする方法の数を数え上げたい。
やりたいことはトポロジカルソートの数え上げではあるが、そんなの多項式時間では無理なので、 「ベースは2列のマージ」であることを利用することになる。
経路数え上げに言い換えるのがわかりやすい。
前\後 - 3 4 4 2 - 1 | | 2 | 2 | 1
左上から右か下に進み、右下までの経路数が答えだが、「前の'2'に進む前に後の'3'に立ち入ってはいけない」「前の'1'に進む前に後の'2'に立ち入ってはいけない」という制約は、上記のような壁で表現できる。
愚直には1マスずつ埋めていくとできるが、$N \le 2 \times 10^5$ なので、$O(N^2)$ は無理。
しかもこれ、あくまで先頭を固定した場合なので、先頭毎にこれだけかかる。
複数の“ある要素を先頭とした場合の数”を、ある程度まとめて計算できれば嬉しい。
そこで、「どこを先頭にしたって、列の末尾の部分や、そこにかかる制約は同じになる」ことに着目して、逆から考える。
i: 1 2 3 4 5 6 7 8 9 10 11 Y: 1 2 2 3 5 5 5 3 4 4 2 i=6 を先頭とした場合にマージしたい列 前: 2→2→1 ↓ `---↓ 後: 5→3→4→4→2 i=3 を先頭とした場合にマージしたい列 前: 2→1 `----------------↓ 後: 3→5→5→5→3→4→4→2 それぞれ長さは違うが、末尾から見たときの並びと、制約の張られる位置は同じ →逆からDPすれば、複数の場合を一度に考えられる
末尾からとした場合、各 $Y_i$ を先頭とした場合の答えがDP配列のどこに現れるかが異なってくる。
答えとなり得る箇所を全て合計すると、全体の答えとなる。
逆にした場合のDPと、各要素を先頭としたときにどこを拾うべきかを示したのが、以下となる。
制約の壁は横になる。
i 11 10 9 8 7 6 5 4 3 2 1 i 前\後 - 2 4 4 3 5 5 5 3 2 2 1 0 - 1 (2) (1) 1 1 ~~~ 2 2 (2) 3 2 ~~~~~~~~~~~~~~~~ (5) (5) (3) 4 3 5 5 6 5 (5)
ここまでの考察から、拾うべき位置は以下のようになることがわかる。
- 基本的には、$i$ を先頭とするなら、前の列は $i-1$、後の列は $i+1$ から始まるので、その斜めのラインに乗っかる
- ただし同じ要素が連続している場合、その中での末尾要素以外は、1つ前の値の高さに揃えられる
拾うべき位置の高さがある程度揃う、というのが重要で、 $Y_{Asc}$ の中で同じ要素が連続している箇所の個数はたかだか9個なので、 9種類の高さの、連続する横範囲の値の合計がわかれば良いということになる。
また都合のいいことに、制約の壁が出現する位置も、性質上、同じ高さに来ることになる。
したがって、同じ要素が連続している箇所はイレギュラーのない綺麗な形となり、畳み込みでまとめて計算できる。
より具体的な方法を示すにあたり、後の列においてindexが逆順になっているのがやりにくいので、
$j=N+1-i$ として昇順に振り直す。
(このように、逆順のindexに変換する関数を $f(i)$ とする)
(i 11 10 9 8 7 6 5 4 3 2 1) j 0 1 2 3 4 5 6 7 8 9 10 11 i 前\後 - 2 4 4 3 5 5 5 3 2 2 1 0 - 1 (2) (1) 1 1 ~~~ 2 2 (2) 3 2 ~~~~~~~~~~~~~~~~ (5) (5) (3) 4 3 5 5 6 5 (5)
- 初期化
- $DP=[1,0,0,0,...]$
- $l=0$: 左からDPが切り詰められる(壁によって防がれる)長さ
- $Y_{Asc}$ で、出てくる種類数を $K$、$i$ 種類目の要素が最後に出てくるindexを $a_i$ とする
- 便宜的に $a_0=0,a_{K+1}=|Y_{Asc}|+1$ を追加する
- 例) $Y_{Asc}=1223555$ なら、$a=[0,1,3,4,7,8]$
- $i=1,...,K$ の順に、
- $d=a_i-a_{i-1}-1$ …(次に求めるべき行と、DPが現在示す行の差分-1)
- $Q=[{}_{d}C_{d},{}_{d+1}C_{d},{}_{d+2}C_{d},...]$
- $Q_k$: 下段に $d$、右段に $k$ だけ移動する経路数
- $DP[l:]$ と $Q$ を畳み込み、新たな $DP[l:]$ とする
- $DP$ の必要な箇所を合計する
- $e=a_{i+1}-a_i$ の時、$f(i)-e~f(i)-1$ の範囲を合計
- $DP$ を切り詰める
- 以降、もう答えとして計上した箇所は不要。$DP=DP[:f(i)-e]$
- 「$Y_{ai}$ を置くまで $Y_j$ を置いてはいけない」制約が設定されていれば、$l=f(j)$ とする
畳み込み、答えの範囲を合計する処理は、1回あたり $O(N \log{N})$、 それがたかだか9回なので、十分高速となる。