ブログにも解説を載せるのは，2026/08 中くらいにします．ちょっと管理や，自分のための検索資産としていまいちなので．
カテゴリページ → https://maspypy.com/category/codeforces
のお知らせも見てください．
A. Creating Abbreviations
すべてのクエリ文字の小文字版が入力文字列の先頭として登場しているかチェック．
B. Gigantomachy
読解でやられまくり．
結局，各プレイヤごとに何回攻撃されると終了かが独立に計算できるので，それを比較するだけです．
C. Spying on the Beaver
bottom up に木 dp をします．
いま見ている点を通った場合に現在区別できていない行先を求めます．
$2$ 方向以上あるならそのうち $1$ 方向以外にはカメラを置いて区別します．
D. Bermuda Rectangle
いや，座標軸に平行くらい書いておいてくれ，clar したけど修正はされませんでした．
二分探索と累積和でできるやつですが，少し面倒だったので
これで処理しました．
E. Busy Beaver
基本的には， $(i,l),\ldots,(i,r)$ をまとめて処理して得できるならやる．ということを繰り返します．
$i$ に対して $l$ は次に可能な選択肢． $r$ ははじめて得できるところまでで区切ります．なので，各時点では $O(N)$ 個の候補があって，そのようなもののうち現在の所持金で行えるものを行いながら所持金を増やしていきます．
これ以上それが行えなくなったら，ひとつの目標に専念して高さを極力増やします．
データ構造や二分探索類は不要で，各 $(i,l)$ から必要な情報が出てくるところまで愚直にシミュレーション，というのを同じ $(i,l)$ について複数回やったりしないようにすれば計算量は大丈夫です．
F2. Beaver’s Jumping Track (Hard Version)
$x\leq 10$ に注目して，左から右に向かって dp することを考えると，min-plus 半環上の行列積という形になります．
状態設計は例えば，
- $(i,x)$： $i$ 番目の区間に入った時点で， $i$ 番目の区間の座標 $[0,x]$ のどこかに着地できる状態
のようにして，各区間には遷移 $(i,x)\to (i+1,y)$ のコストを持たせます．
この状態設計で答を得るのもうまいことできて， $(L,0)\to (R+1,X-1)$ のコストが求めるものになります． $y=X-1$ にするには直前に飛び上がる必要があるため．これで，
- $O(NX^3+Q\log N X^3)$
- $O(NX^3+Q\log N X^2)$：求値の際に行列行列積ではなく行列ベクトル積を利用
などになってどちらにせよ F1 は AC 可能だと思います．
F2 は $Q$ が小さいことに注目して，次のようにしました．
- 変更がくる点，クエリがくる点で座圧する
- 座圧した区間ひとつひとつをセグメント木にのせる基本単位とする
これで時間空間ともに削減になります．まず，空間を確認すると， $O(NX^2)$ から $O(QX^2)$ になっています．
次に時間を確認します．クエリの方は上述のテクニックで $O(Q\log Q X^3)$ や $O(Q\log Q X^2)$ になって，そもそも前者でも十分小さいです．構築にかかる時間をチェックします．
座圧区間に対する行列を求める際に，各 $i$ に対する行列をかけていってしまうとダメです．ここは， $(i,x)\to (i+1,y)$ の遷移をすべて考えるのではなく，固定した $x$ については $O(1)$ 個の意味のある遷移だけを計算するようにします．各初期値からこのような dp を行っていって，構築も $O(NX^2)$ になります．
（疎行列というのとは違いますが，単一区間に対応する行列はベクトルに対して $O(X)$ 時間でかけられるということに対応します．）
