A. Digits Sequence Dividing

ABCの中で一番難しい．CodeforcesのA問題では殆どの場合に適用できる最適解（端を取ったり中央を取ったりソートしたり2の倍数だったり）＋コーナーケースの処理みたいなのを割と見る気がしていて，今回もそれ． 解答例

左を1桁だけ残して2つの数に分割すると，$n_i \ge 3$であれば必ず条件が達成できる（右のほうが桁が多くなるので必ず右のほうが大きい）．$n_i = 2$のときは左$\lt$右であれば条件に合うが，それ以外，すなわち左$\ge$右のとき不適．このとき他に分割する方法もないので無理だと分かる．

B. Digital root

解答例

一見難しそうに見えるが$S(x)$と$x$の関係を表にしてみれば一目瞭然という感じ：

 1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27
28 29 30 31 32 33 34 35 36
37 38 39 40 ..

すると求めるべき「$S(m)=x$となる$k$番目の$m$」は表の$x$列目の上から$k$番目の数．従って$m = x + 9 \times (k-1)$．

おまけ

"Digital root"で検索するとwikipediaの記事が出てきて，計算式まで載っている：$S(n) = n - 9 \lfloor {\frac {n-1}{9}} \rfloor = 1 + (n-1) \% 9$．editorialにはここからでも求められると書いてある：$S(m) = x = 1 + (m-1)\%9$において$m-1=9u+v$と表示すると$x-1 = v$であるから$m = 9u + x$となり，これは$u$番目（0-indexed）の数であることから$k$（1-indexed）番目は$m=9(k-1)+x$．

C. Brutality

CodeforcesのC問題の難易度の基準がわからない． 解答例

同じボタンを$k$回連続で押してしまうと駄目ということは，同じボタンの連続部分についてはその中の$k$個しか選べないということ．逆に他のボタンの部分や同じボタンでも何か挟んだ位置のものについては気にしなくてよい^[1]．従って各ボタンの連続部分を独立に考え，その中の最大$k$個を取ればよい．単純にソートしても間に合った．

D. Compression

数学に明るくないので$\lceil x \rceil$が切り上げか切り捨てか分からなくなったが右クリック→Show Math As→TeX Commandsしたら分かりやすくなった．切り上げなのは1-indexedのため．AC数が少なかったが，落ち着いて見たら特に難しくなかった． 解答例

要するに行列を同じサイズの正方形のピースに分割したとき各ピースの中身がすべて0かすべて1であるようなサイズの最大値を求めたい．2次元累積和を取りさえすれば，ある範囲内がすべて1であるか，すべて0であるか，1と0が混ざっているかが$O(1)$で分かる．サイズを固定したとき，各ピースに対してこれを試して前2つであれば問題なく圧縮可能，でなければ失敗．あとはピースのサイズを試していけばよい．候補は$n$の約数なので$O(\sqrt{n})$で求まり，これを大きい順に試す．

計算量解析をせずにだいたい調和級数のあれの二乗だから間に合うんじゃないかなで投げてしまった．累積和づくりに$O(n^2)$，約数生成に$O(\sqrt{n})$であり，これらは間に合う．最後の約数を順に試すところの最悪計算量を考えると$O(1^2 + ... + \frac{n}{d^2} + ... + \frac{n}{2^2} + n ^ 2)$ $= O(n^2 (\frac {1} {n^2} + ... + \frac{1}{d^2} + ... + \frac {1} {2^2} + 1))$（$d$は$n$の約数）となり，括弧部分は有名な$\sum_{k=1}^{\infty} {\frac{1}{k^2}} = \frac{\pi^2}{6}$で上から抑えられる．従って$O(n^2)$．

一回$n$の約数を二分探索してしまったがどう考えても単調ではない^[2]．そんなこんなで2WAほど．

別解

editorialは理解できなかったものの（なんでその言い換えが……？），これと同じくgcdを用いる解法が浮かんだので試してみた．

1または0の1種類からなる部分行列であってこれ以上大きくできないもの^[3]をブロックと呼んでみる．各ブロック$i$を長方形$[px_i,px_i+bx_i-1] \times [py_i, py_i+by_i-1]$と表現する^[4]．分割によってできる正方形$(u,v)$は$[ux, (u+1)x-1] \times [vx, (v+1)x-1]$．

いま各ブロックは分割でできた正方形を並べて作られるから，長方形の左上および右下座標について$px_i=ux,$ $py_i=vx,$ $px_i+bx_i=(s+1)x,$ $py_i+by_i=(t+1)x$と表現でき，ここから$px_i,py_i,bx_i,by_i$はすべて$x$で割り切れることが分かる．逆にこの条件下で各ブロックは正方形$(px_i/x,py_i/x),...,((px_i+bx_i)/x-1,(py_i+by_i)/x-1)$だけから成り題意を満たすから，$px_i,py_i,bx_i,by_i$を割り切る数が$x$の候補となる．求める値は$x$の最大値であるから，これらのgcdを取ればよい．

さらに「$bx_i \equiv by_i \equiv 0 \Rightarrow px_i \equiv py_i \equiv 0 \pmod x$」を示す：$px_i$は$0$，またはブロック$i$の左隣にあるブロック$j$の右下x座標+1$= px_j+bx_j-1+1$ $= px_j+bx_j \equiv px_j \pmod x$であり，ここから再帰的に$px_i \equiv 0$が示せる．$py_i \equiv 0$も同様．以上から $x = \gcd \{ \gcd \{bx_i\}, \gcd \{by_i\} \}$^[5]．

肝心なのは$bx_i, by_i$の求め方．ただのDFSだと長方形にならず失敗することに注意．ここでは始点を$(x,y)$としたときまず$y$方向に異なる要素にぶつかるまで掘り進める．ここを$(x,y+d_x)$とする．以降は同様にして$d_{x+i}$を計算していき，$d \neq d_{x+i}$となったら長方形$[x,x+i-1] \times [y,y+d_x]$を切り出すとよさそう．これなら必ず長方形になる． 解答例

提出コードは$O(n^2)$のはずだが重複して数える部分もあったりするからか累積和のコードよりだいぶ重い（実装も重かった）．元の行列の要素を持つ配列matに対する取得，および訪れた要素かを格納する配列visitedに対する更新はそれぞれ区間の和や区間に対する加算で書けるはずなのでSegment Treeを使えたりするだろうか（未調査）．

サンプルを作るのが意外と大変だったので，DFSで失敗する例を置いておく^[6]．

---

1. 離れた位置の同じボタンについて：最大値を得たいという条件から，例えばaaabbaaのような配置のときにbを1つも選ばない理由は無い．よって左右の部分にあるaは絶対に連続せず，独立に考えられる． ↩︎

2. 分割が2の倍数のものばかり試しており気付けなかったが，たとえば次の行列ではサイズ3で分割できるものの2では不可能：

   111000111000
   111000111000
   111000111000
   000111000111
   000111000111
   000111000111
   111000111000
   111000111000
   111000111000
   000111000111
   000111000111
   000111000111
   

   ↩︎

3. 気持ち的には自然に長方形に分けたもの． ↩︎

4. 左上の座標が$(x,y) = (px_i,py_i)$，大きさが$($幅, 高さ$) = (bx_i,by_i)$ということ． ↩︎

5. 今思うと実装でどうせ$px_i,py_i$が求まるので別に$bx_i,by_i$だけの条件にする必要は無かった． ↩︎

6. 12
   E00
   E00
   E00
   1C7
   1C7
   1C7
   E00
   E00
   E00
   1C7
   1C7
   1C7
   

   ↩︎