ABC129 - Tallfallの日記

やりたいことはすぐ見えるけれども、実装の方針で結構難度が変わりそうな問題でしたね。
自分は一往復する感じで行を見ていきました。転置して同じ処理をするとコピペができて楽ですね。
.split('#')を使って実装してる人がいて（本質的にはランレングス圧縮）賢いなと思いました（こなみ）
AtCoderはかなりpythonに優しいのでpypyで書くと通ります。
汎用的なこととして、二次元grid系の問題がTLEしそうだなと思ったら

PyPyを使う（前提）
文字列をやめる（.find()や.split()を効果的に多用してない限りかなり効くし実装も楽になりがち）
一次元に書き直す（効くけど実装がすこし大変）

あたりをしとくといいと思います。

提出: Submission #5846943 - AtCoder Beginner Contest 129

E - Sum Equals Xor

a^bは（ここで＾はbitwiseOR）繰り上がりのない足し算だというのは典型で、
制約から桁dpっぽいのも典型で
区間の分割も典型でした。イメージとしては
$[0, 12345]$ を
$[0, 10000),[10000,12000),[12000,12300),[12300, 12340),[12340,12345]$ に分割するみたいな感じです。
典型の詰め合わせで面白かったです。全体的にここまで遅かったです、反省。

提出: Submission #5850684 - AtCoder Beginner Contest 129

F - Takahashi's Basics in Education and Learning

制約からLに対して $O(\log{L}) か O(1)$ で解くべきなのはそんな気がします。
$s[i$ ]の桁が一定の区間をまとめて処理すると楽そうだなぁとは思ってたのですが、式をぐりぐりしていると
分数を用いた表式が出てきてこれは解けたなとか思ってました。まぁ法と分母が互いに素とは限らなかったので逆元が使えないので駄目でした。残念。

さて、s[i]までに対するこの問題の答えをans[i]とします。ここでs[i+1]の桁数をkとすると
この時、ans[i+1] = ans[i]*10**k + s[i+1]
が成り立ちます。この視点がコンテスト中には足りませんでした。ここで固定されたkについてまとめて考えて(単調性からこれは区間になる)10進表記でk桁になる要素がp個あるとすると、
ans, T の初期値を適切に考えるとして
ans $\to$ 10**k*ans + T
T $\to$ T + B
という変換をp回してやれば良いことになります。
これは
$\begin{pmatrix} ans \\ T \\ 1 \end{pmatrix} \gets \begin{pmatrix} 10^{k} & 1 & 0 \\ 0 & 1 & B \\ 0 & 0 & 1\end{pmatrix}^{p}\begin{pmatrix} ans \\ T \\ 1 \end{pmatrix}$
を計算することに他ならず、行列累乗で $O(N^{3}\log(p))$ で求まります（Nは行列のサイズ = 3）。実装は案外軽いですね。
同桁長の列挙でバグらせて2WAしました。

提出: Submission #5861678 - AtCoder Beginner Contest 129