−目次
AtCoder Regular Contest 153 B,C,D,E問題メモ
B - Grid Rotations
問題
- H×W のグリッドにそれぞれ文字 Ci,j が書かれている
- Q 回、以下の操作を行う
- ai,bi が与えられる
- グリッドを、ai 行目と ai+1 行目の間の線、bi 列目と bi+1 列目の間の線で十字に分割する
- 分割された4つの長方形領域をそれぞれ180度回転する
- 最終的なグリッドに書かれた文字を出力せよ
- HW≤5×105
- 1≤Q≤2×105
解法
タテヨコは独立に考えていい。
最初の i 行目が最終的に ri 行目、j 列目が cj 列目に移るなら、答えの (ri,cj) のマスにあるのは Ci,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回の操作をまとめると、a1→a2 の順で操作が発生すると (a1−a2)modH だけ転回する。
よって、2個ずつ、いくつ転回したかを追っていって、Q が奇数なら最後の操作だけ愚直にやればよい。
C - ± Increasing Sequence
問題
- −1 または 1 からなる数列 A=(A1,...,AN) が与えられる
- 以下の条件を全て満たす数列 x=(x1,...,xN) を構築できるか判定し、可能なら一例を挙げよ
- |xi|≤1012
- 狭義単調増加、つまり xi<xi+1
- Ai×xi の i=1~N にわたる総和が 0
- 1≤N≤2×105
解法
符号が Ai によって反転されうるため、Aixi の正負が入り交じる。
総和を特定の1つとかある範囲で調整する、ということを考える際、 狭義単調増加は置ける値の範囲が i ごとに変わるため扱いにくくて、できれば広義単調増加で考えたい。
最初に x′=(1,2,3,...,N) と仮決めして、そこからの差分 y を考えると、y は広義単調増加であれば良くなる。
よって、x′ をそのようにした際の Aix′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 が負で、A1=−1 だったとき、y1 は好きなだけ減らせるので、逆に総和は S から好きなだけ増やせることになる。(1012 という制約はあるが、一端無視して)
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 が負で、AN=1 だったとき、yN は好きなだけ増やせるので、同様に S から好きに増やせる。
S が正の時は逆に、A1=1 または AN=−1 なら総和を好きに減らせる。
じゃあ、そうでない時は?
y には、先頭からある範囲までに一定値を減じる、または末尾からある範囲に一定値を加えてもよい。
たとえば S が負(−k)なら、y1~yj に一斉に一定値を減じたとき総和が k 増加してくれればよいので、A1~Aj の総和が負(特に微調整を考えると −1)ならよいことになる。
よって、Ai の先頭or末尾からの累積和を取っていって、
- S が負なら
- ①先頭からの累積和で、総和が −1 になるところ
- ②末尾からの累積和で、総和が +1 になるところ
- いずれかを見つけ、その範囲の y に①なら S を加算、②なら S を減算
- S が正なら
- ③先頭からの累積和で、総和が +1 になるところ
- ④末尾からの累積和で、総和が −1 になるところ
- いずれかを見つけ、その範囲の y に①なら S を減算、②なら S を加算
すれば、調整が可能となる。
(最初に述べた、先頭・末尾の1項だけで調整する操作も、この処理にまとめられる)
S≠0 で、そのような箇所が全く登場しないとき(-1と+1が、良い括弧列となっているとき)は、調整ができず不可能。
で、最後にこれが 1012 を超えないかだが、
- S は、最大 N(N+1)2≤約2×1010 で、±S が yi の範囲
- x′ の最大値は 2×105
- よって x=x′+y の絶対値は 1011 を超えない
ので大丈夫と分かる。
D - Sum of Sum of Digits
問題
- N 個の整数 A1,...,AN がある
- f(x) を、正整数 x の10進表記での各桁の和とする(f(153)=1+5+3=9)
- 非負整数 x を決めたとき、N∑i=1(f(Ai+x)) としてあり得る最小値を求めよ
例
A = ( 4 13 8 6) x=7 とすると、 f( 4+7) = f(11) = 2 f(13+7) = f(20) = 2 f( 8+7) = f(15) = 6 f( 6+7) = f(13) = 4 ~~~ 総和は 14
解法
考察は下の桁から考えた方がわかりやすいように思うが、実装は上の桁から行う。ややこしい。
数列 X に対し、問題で求められる値 (適切な x を加算したときの N∑i=1(f(Xi+x)) の最小値)を、F(X) とする。
すると、下の桁から再帰的に求めるようなアルゴリズムができる。(実際はこのままではTLEだが)
A = (141, 926, 358, 793) とする。 下1桁を考えると、(1,6,8,3) である。 x=0 → 1 + 6 + 8 + 3 + F((14,92,35,79)) x=2 → 3 + 8 + 0 + 5 + F((14,92,36,79)) 358 が 360 に繰り上がっている ~ ~~ x=4 → 5 + 0 + 2 + 7 + F((14,93,36,79)) ~ ~~ x=7 → 8 + 3 + 5 + 0 + F((14,93,36,80)) ~ ~~ x=9 → 0 + 5 + 7 + 2 + F((15,93,36,80)) ~ ~~ 答えは、この5つの場合の中の最小値
x の加算による繰り上がりを反映した上で、各 Ai を10で切り捨て除算したような A′ に対する F(A′) を求める問題に再帰的に縮小できる。
制約的に9回再帰すれば十分であり、その頃には A の値は0か1になっている。
そしたらもう x を足して繰り上げる意味は無いので、F(A)=sum(A) となる。
F() の引数となりうる状態数は、各桁につき「N 個のうちどこかまでが繰り上がった状態」なので、N+1 通り。
Ai の桁数の最大値を K(≤9) とすると、全部で O(KN) となる。
実行制限時間に間に合わせるには、各 F() を求めるのに O(1)~O(K) 程度までなら大丈夫。
しかし、下の桁からの再帰を素直に実装すると、1つの状態の計算に O(N) かかってしまう。これはダメ。
上の例において、例えば F((14,92,35,79)) の結果から F((14,92,36,79)),F((14,93,36,79)),... が順次差分計算できることを利用すれば、ならして O(1) で求められる。
そのような実装は、下の桁からの再帰ではやりにくいので、上の桁から埋めていく。
自分のDPの定義は、あまり説明しやすい実装では無い(もっとわかりやすいDP定義による実装がありそう)が、、、
- DP[i,j]= 以下のように作られた Bi に対し、Bi[j] の下1桁がちょうど繰り上がる場合の F(Bi)
- A を Ak%10i を基準に降順ソートする
- Bi[k]=Ak/10i−1(切り捨て除算)とする
- j=0 の場合は、1つも繰り上がりが発生しない場合の F(Bi)
例 A = (141, 926, 358, 793) DP[2,3]: 100で割ったあまりの 41,26,58,93 を基準に降順ソート → (793, 358, 141, 926) その後、10で割る → B2 = (79, 35, 14, 92) このB2に対し、B2[3]=14 がちょうど繰り上がる(足す数 $x$ の下1桁が6である)前提での F(B2)
同様に B3=(9,7,3,1) である。
DP[3,:] から DP[2,:] を求めるにあたり、B2 と B3 の間で元となった Ai の位置関係 P2 を求めておく。
i 1 2 3 4 B3 9(926) 7(793) 3(358) 1(141) ... B3としての値(元のAiの値) B2 79(793) 35(358) 14(141) 92(926) ... B2としての値(元のAiの値) P2 2 3 4 1 ... B2における、元のAiのB3における位置
DP[3,:] と P2[:] から DP[2,:] を求める。
B2 j xの下1桁 x加算後のB2の下1桁の和 上の桁 ↓ 0 0 20 + F(7,3,1,9) = DP[2,0] 79 1 1 14 + F(8,3,1,9) = DP[2,1] 35 2 5 20 + F(8,4,1,9) = DP[2,2] 14 3 6 14 + F(8,4,2,9) = DP[2,3] 92 4 8 12 + F(8,4,2,10) = DP[2,4] B3 j xの下1桁 x加算後のB3の下1桁の和 上の桁 ↓ 0 0 20 + F(0,0,0,0) = 20 = DP[3,0] 9 1 1 14 + F(1,0,0,0) = 15 = DP[3,1] 7 2 3 12 + F(1,1,0,0) = 14 = DP[3,2] 3 3 7 18 + F(1,1,1,0) = 21 = DP[3,3] 1 4 9 16 + F(1,1,1,1) = 20 = DP[3,4]
「x 加算後の B2 の下1桁の和」は、、、
- まず素の状態で B2 の下1桁の総和を取る(9+5+4+2=20)。これが j=0 のとき。
- j=1 のとき、x の下1桁は1のため、N 個の数に1が足され、うち j=1 個が繰り上がる(桁和が10減る)
- → j=0 の時の差分から、20+1∗N−1∗10=14
- j=2 のとき、x の下1桁は5のため、N 個の数に5が足され、うち j=2 個が繰り上がる
- → j=0 の時の差分から、20+5∗N−2∗10=20
- j=3 のとき、x の下1桁は6のため、N 個の数に6が足され、うち j=3 個が繰り上がる
- → j=0 の時の差分から、20+6∗N−3∗10=14
、、、としていくと、O(N) で全体を求められる。
DP[3,:] と P2[:] から DP[2,:] を求める際も、似たような差分計算ができる。
- まず、DP[2,0] を求める際に必要となる F(7,3,1,9)=min(DP[3,:])=14 である。
- DP[2,1] を求める際に必要となる F(8,3,1,9) は、、、
- B3 における P2[1]=2 番目の項が1増える (9,7,3,1) → (9,8,3,1)
- 差分を考えると、
- 1つの項が1増えたため、DP[3,:] から各項が 1 ずつ増える
- B3 の値が1増えた DP[3,2] だけは、N 減る
- ※ x 加算後の下1桁の和の更新方法を考えれば、こうなることがわかる
- これによって、初期状態より DP[3,2] が小さくなったら、最適な min(DP[3,:]) が更新される
- DP[2,2] を求める際に必要となる F(8,4,1,9) は、、、
- B3 における P2[2]=3 番目の項が1増える (9,8,3,1) → (9,8,4,1)
- 差分を考えると、
- 初期から2つの項が1増えたため、DP[3,:] にとっては各項が 1 ずつ増える
- B3 の値が1増えた DP[3,3] だけは、N 減る
- これによって、b+2 より DP[3,3] が小さくなったら、最適な min(DP[3,:]) が更新される
…としていくと、こちらもならして O(N) で DP[2,:] を埋められる。
例: DP[2,0]で必要な F(7,3,1,9): DP[3,:] = (20, 15, 14, 21, 20) → F(7,3,1,9) = min(DP[3,:]) = 14 DP[2,1]で必要な F(8,3,1,9): ・DP[3,:] の各項に1足す ・繰り上がった 7 (元のAi=793)がB3で位置するindex = 2 なので、DP[3,2] からN引く DP'[3,:]= (21, 16, 11, 22, 21) → F(8,3,1,9) = min(DP'[3,:]) = 11 DP[2,2]で必要な F(8,4,1,9): ・DP[3,:] の各項にさらに1足す ・繰り上がった 3 (元のAi=358)がB3で位置するindex = 3 なので、DP[3,3] からN引く DP''[3,:]= (22, 17, 12, 19, 22) → F(8,4,1,9) = min(DP''[3,:]) = 12
E - Deque Minimization
問題
- '1'~'9'からなる文字列 X に対し、以下を考える
- X に以下の操作を行い、文字列 S を得る
- S を空文字列で初期化する
- X1,X2,...,XN の順に、S の先頭または末尾に挿入する(Xi は X の i 文字目)
- この操作により得ることができる S のうち、整数としてみたときに最小のものを f(X) とする
- '1'~'9'からなる文字列 Y が与えられるので、f(X)=Y となるような X の個数を mod998244353 で求めよ
- 1≤|Y|≤200000
解法
f(X) を構成するための操作
X1 はまぁそのまま挿入するとして、最小にするなら下記のようにすればよい。
- Xi (i≥2)を S に挿入するとき、その時点の S の先頭を S1 として、
- S1≥Xi なら、Xi を先頭に挿入
- S1<Xi なら、Xi を末尾に挿入
S1=Xi の場合も本当に先頭でいいのか? と思うが、上記の方針をとる以上、
- 暫定の S が全て同じ文字なら、先頭と末尾どちらに挿入しても変わらない
- 重複を除くため、先頭に挿入することで統一する
- S が全て同じでないなら、どこかではじめて S1 と異なる文字 c が出てくる
- この c は、必ず S1 より大きい
- c が S1 より小さくて、S1 より後に挿入されたなら、先頭に来ているはず
- c が S1 より小さくて、S1 より前に挿入されたなら、S1 の方が後に来ているはず
- よって Xi は先頭に挿入し、S1 が続く長さを長くした方が良い
また、S=11233 を作れるけど、途中段階では敢えて S=32131 みたいにすることで、最終的には 11233 としたときより S を小さくできる、みたいなことは起こらない。
11233 にしようと 32131 にしようと、これ以降、何をどのような順で前・後ろに挿入可能かは全く同条件であり、
(同じ並び)11233(同じ並び) (同じ並び)32131(同じ並び)
なら確実に前者の方が小さい。その時々で最小となるように前・後ろのどちらに挿入するかを決めていってよい。
よって、X が決まっているなら、そこから f(X) を作る操作は意外と単純である。
先頭を固定した場合の数
先頭要素 X1 が Y の何文字目にあたるか(Y がどこから生成されていったか)を固定する。
Yi から生成されたと決め打つと、そこから後は左右に広がっていったことになるので、
- Yi−1→Yi−2→...→Y2→Y1
- Yi+1→Yi+2→...→YN
X2 以降の要素の並び順は、上記のような2つの列をマージしたものに限定される。
(マージ:ここでは、列の中での順序は保たれるように、2つを1つにまとめる操作を指す)
その上で、いくつかの制約がある。
先頭から昇順が続く範囲しか X1 にできない
以下のような時に、3を最初に置くことはできない。
Y: 1 2 4 5 [3] 4 6 ...
3を最初に置いた後に5を挿入したとすると、その5をわざわざ前に持ってこないと この Y は作れないが、f(X) を作る操作に違反する。
上記の例なら、先頭の4つ 1,2,4,5 が、X1 となり得る範囲となる。
置く順序の制約
もし、長さ n と m の2列を単純にマージするなら、 場合の数は n+mCn で求められるが、そう単純でもない。
前に置かれるべき数が、誤って後に置かれることは基本的にないが、
後に置かれるべき数は、それ以前に自身より小さい値が前に置かれていないと、前に置かれてしまう。
そうなるとより小さい f(X) が作れるような、数え上げの対象ではない X となってしまう。
以下の2通りの場合に注意する。(①は、ちゃんと考えれば②にまとめられるかもしれないが、分けて考えた方がわかりやすい)
- ①同じ要素が連続している箇所を先頭とする場合
- ②後に置かれるべき数の列の中で、これまでより小さい値が出てくる場合
今、i=6,X1=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
X2 以降は、このような2列のマージとなる。
- 前に置かれる 5→3→2→2→1
- 後に置かれる 5→3→4→4→2
次に来るのはいずれでも 5 だが、5 が来ると、f(X) の構築方法から考えるとこれは前に置かれることになる。
よって、X2 には、前に置かれる方の5しか来てはいけないことになる。
次も同様で、(最終的に i=5,6 に収まるべき)'55' がある状態に(最終的に i=7 に来るべき)'5'が来たら、 これは前の方に置かれてしまうのでダメ。ここも前に置かれる方の3しか来れない。
暫定S: 3 5 5 残り列 前に置かれる 2→2→1 後に置かれる 5→3→4→4→2
S の先頭が3になってはじめて、これ以降の5は後に置くべきとなったので、 X4 には前に置かれる'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 の中で昇順が保たれる範囲を YAsc、それ以降を YNotAsc とする。
YNotAsc の先頭から累積minを取りながら、累積minを更新する要素 Yj を探す。
Yj に対し、Yj−1 以下の要素が YAsc 中で最後に出てくるのが Yi だったとすると、
「Yj が置かれる前に Yi が置かれなくてはいけない」という制約が見つけられる。
ただし、それより前に見つかった制約と Yi が同じであれば、無視してよい。
また、YNotAsc の中に Y1 より小さい値が出てきたら、
そいつを前に置かれることが阻止できないので、そのような 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≤2×105 なので、O(N2) は無理。
しかもこれ、あくまで先頭を固定した場合なので、先頭毎にこれだけかかる。
複数の“ある要素を先頭とした場合の数”を、ある程度まとめて計算できれば嬉しい。
そこで、「どこを先頭にしたって、列の末尾の部分や、そこにかかる制約は同じになる」ことに着目して、逆から考える。
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すれば、複数の場合を一度に考えられる
末尾からとした場合、各 Yi を先頭とした場合の答えが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つ前の値の高さに揃えられる
拾うべき位置の高さがある程度揃う、というのが重要で、 YAsc の中で同じ要素が連続している箇所の個数はたかだか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が切り詰められる(壁によって防がれる)長さ
- YAsc で、出てくる種類数を K、i 種類目の要素が最後に出てくるindexを ai とする
- 便宜的に a0=0,aK+1=|YAsc|+1 を追加する
- 例) YAsc=1223555 なら、a=[0,1,3,4,7,8]
- i=1,...,K の順に、
- d=ai−ai−1−1 …(次に求めるべき行と、DPが現在示す行の差分-1)
- Q=[dCd,d+1Cd,d+2Cd,...]
- Qk: 下段に d、右段に k だけ移動する経路数
- DP[l:] と Q を畳み込み、新たな DP[l:] とする
- DP の必要な箇所を合計する
- e=ai+1−ai の時、f(i)−e~f(i)−1 の範囲を合計
- DP を切り詰める
- 以降、もう答えとして計上した箇所は不要。DP=DP[:f(i)−e]
- 「Yai を置くまで Yj を置いてはいけない」制約が設定されていれば、l=f(j) とする
畳み込み、答えの範囲を合計する処理は、1回あたり O(NlogN)、 それがたかだか9回なので、十分高速となる。