（ポエム）2023年の作問
自分が作問し 2023 年に公開された問題を振り返り、 upsolve を勧誘する記事です。
ICPC 2023 国内予選 D 「効率的な問題セット」（原案のみ）
オンラインジャッジ： https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1667&lang=ja
大昔から作問ストックに入っていたのですが機会がないまま放置しており、今回たまたま公開できました（国内予選の少し前に ABC の配点が毎回変わるようになったので、時事ネタとして問題爆破が起きないかヒヤヒヤしていました）。
ちなみに、こちらの問題では の制約で出題していますが、ごく丁寧に書くことで
くらいでも十分高速に解けるはずです（実装量も特に大変なことにはならないはず）。
ICPC 2023 国内予選 E 「改竄された史料」
オンラインジャッジ： https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1668&lang=ja
大昔から作問ストックに入っていたのですが機会がないまま放置しており、今回たまたま公開できました。(2)
元ネタはスフィアの「らくがきDictionary」で、曲名からほぼそのまま作っています。元々は長さ の文字列が
個ある設定でストックしていたのですが、実装が面倒だったり非想定解法と区別するのが難しかったりしたためいつの間にか
になり、辞書感が薄れています。
解法を言われてしまえば素直な DP なのですが、なかなか見えにくいという感想を目にすることが多く、不思議な問題という印象があります。
ICPC 2023 Asia Yokohama I 「Liquid Distribution」
元ネタはスリーズブーケの「Mix shake!!」で、色々と問題設定を考えた中で特に綺麗に解けたものを出題しました。自分は問題を立ててから解けるまで数日以上かかっています。
yukicoder Advent Calendar Contest 2023 V 「Mix shake!!」
上述の「Liquid Distribution」の解法を思いついた日に就寝しようとしたら突然このバージョンでもうまく解けることに気づいたので出題しました。
プログラミングコンテストというよりは数学パズルのような問題ですが、解法を直観的に理解するには高校数学レベルで十分であったり、問題の見た目と想定解のギャップが（主観的に）大きかったり、実は計算量もうまく抑えられていたりと、自分が今まで作問・出題してきたなかでは最も気に入っている問題です。よかったら解説冒頭の想定解も読んでみてください。
DEGwer さんの D 論応援コンテスト C 「binarydigit」
問題設定から作問して、自力では多項式時間には落とせなかったのですが、指数オーダーのなかではかなり高速化できたので、この改善を問うても良いかと考え出題しました。計算量の区別がシビアなので、かなり実行時間制限が厳しめになってしまい、ここで苦しんだ方がいたら申し訳ないです......。
想定解では加算と乗算しか登場しないのと、テストケースハックが少しでもやりづらくなるかと考え mod 合成数で出題したのですが、コンテスト中に heno239 さんから mod 素数のケースで適切に動作する多項式時間解法の提出があり本当にびっくりしました。 mod 合成数で解けるかという点は自分にとって真に問いたいことではないので、この提出は本当は満点（かそれ以上）として評価されてほしいという気持ちもあり、 mod 素数で出題すれば良かったと後悔しました。
twitter.comhttps://t.co/tdWtuBT9bj
— heno (@heno_code) 2023年12月2日
(小さくない)素数の時に通っているコード
O(H^4W^3)
なお本問題で数え上げている対象そのものが OEIS A180985 - OEIS に存在し、 が小さい範囲の答えは載っているようです。
DEGwer さんの D 論応援コンテスト H 「Incomplete Notes」
元ネタは SPR5 の「インコンプリートノーツ」の曲名で、wildcard pattern matching を捻った形で出題しようと考えて作りました。かなり解法ドリブンな問題な気がします。
作問者としてはテストケース作りで苦しみました。愚直な アルゴリズムを枝刈りした解法（や、それを工夫した解法）に対して強く十分複雑なケースがあまり思いつかなかったので、
や
の上限を引き上げることでごまかして（？）います。コンテストではその他様々な解法で解いていただけて興味深かったです。
おわりに
いずれも一捻りある問題だと思っているので、お暇でしたら是非 upsolve してやっていただけると幸いです。また、2024 年以降もどこかしらで問題を出していければと思っており、その際はよろしくお願いします。
atcoder::lazy_segtree に1行書き足すだけの抽象化 Segment Tree Beats
AtCoder Library (ACL) の atcoder::lazy_segtree をもとにした Segment tree beats の抽象化の方法と，そのいくつかの具体的な使用例を紹介します．Segment tree beats は列に対する複雑な更新・取得処理を高速かつオンラインに実現する強力な手法ですが，実装の際に考慮すべきことが複雑でコーディング量も多く，体系立った実装方法の知見も整理されていないと筆者は認識しています．そこで本稿では，ドキュメントを含め極めて整備された ACL のコードをわずかに変更して Segment tree beats として使用する方法を紹介します．この方法では，様々な Segment tree beats の実装の大部分が共通化され，個別の問題に応じた機能は atcoder::lazy_segtree の利用時と同様にクラスや関数として組み込まれます．これにより，無用なデバッグの手間が削減され，コーダーはより本質的なロジックに対して集中できるようになります．その上，元の atcoder::lazy_segtree が持っていた機能はもちろんそのまま引き継がれるので，max_right() や min_left() 関数による効率的な二分探索も可能です．また，コードが問題に依存しない共通部分と問題毎に特殊な部分で完全に分離されるため，ライブラリ化の際の管理も容易です．
本稿は「Segment tree beats の存在は知っているが実装の経験がなく，これからできるだけバグで苦しまずに実装したい」という方を念頭に置いて書かれています．Segment tree beats のオーソドックスな導入は本稿には含まれません．なお，本稿に記載したコードは各種オンラインジャッジへの提出を目的として自由に使用・改変して頂いて構いません *1 が，それに伴う結果に筆者はいかなる責任も負いません．
続きを読むyukicoder No.1303 Inconvenient Kingdom
\(O(N^3) \) 解（執筆時点で Fastest AC）です．
解法
連結グラフの場合だけを考えます（それ以外の場合は連結成分毎に行列木定理を適用することでもともと \( O(N^3) \) で解けるので）．このとき，問題は「 \(N \) 頂点の単純連結無向グラフが与えられる．新たに一辺だけ追加してもよいとき，その全域木の個数を求めよ」となります．
まず，新たに一辺 \((i, j)\) が追加されたグラフについて，この辺を必ず用いるような全域木の個数を考えます．これは， \((i, j)\) 間に重み \(x\) の辺を張り（＝ \((i, j)\) 間に \(x\) 本の多重辺を張り），通常の行列木定理を適用した結果（これは \(x\) の多項式になります）を \(f(x)\) とすると， \(f(x)\) の \(x\) の一次の係数が答になります．
もともと辺が存在しない全ての頂点対 \((i, j)\) に対してこの計算を行っていては，\(O(N^3)\) 等の計算量を要する行列式の計算を \(O(N^2) \) 回繰り返すことになり，到底 TL に間に合いません．しかし，「もともと辺が存在しない頂点対 \( (i, j) \; (i < j)\) 全てについて新たに重み \(x\) の辺を追加する」という操作を行い，このグラフに対して行列木定理を適用することで，あらゆる頂点対 \((i, j)\) に関する先述の問題の答の総和が一挙に得られます（新たに張った辺を複数本使用するような全域木は \(x\) の二次以上の項に寄与するので）．今回は \(x\) の高次の係数には興味ないので \( \mathrm{mod} \, x^2\) の範囲で計算すればよく（例えば \(a + bx\) の逆元は \(a^{-1} + (a^{-2}b)x \) となります），めでたく \(O(N^3)\) で行列木定理における行列式の計算が行えます．
実装例
C++17(1z), 5 ms（追記：掃き出しの実装が誤っていたため修正）
感想
やっていることが 二重数を用いた自動微分の計算 （新たに辺を増やした時，全域木の個数はどれだけ増えるか？）とも解釈できて少し興味深かったです．
yukicoder No.1289 RNG and OR
思考の過程が想定解と違ったので．（追記）答えは合うのですがかなり怪しいところがあるので，正当性の証明（または反例）を募集しています．
解法
長さ \(2^N\) の配列同士の (bitwise) OR convolution: $$ (f \ast g)[i] = \sum_{(j | j') = i} f[j] g[j']$$ を表す演算を \(\ast \) と書くことにする．また，長さ \(2^N\) の配列 \(e[i]\) を， $$ e[i] = \cases{ 1 & $i = 0$ \\ 0 & $i = 1, \ldots, 2^N - 1$ } $$ と定義すると，この \(e\) は演算 \(\ast\) に関して単位元となる（任意の \(f\) について \( e \ast f = f \ast e = f\) が成立）．
また，本問における状態遷移確率を表す長さ \(2^N\) の配列 \(g[i]\) を， $$ g[i] = \frac{A[i]}{\sum_{j=0}^{2^N - 1} A[j]}$$ とおく．ある時点において，それまでに手に入った整数の論理和の値が \(i\) であるような確率が \(f[i]\) であるような配列 \(f\) があったとして，新たにもう一つの整数を手にいれた場合の論理和の値の確率分布は \(f \ast g\) で書ける．先ほど定義した \(e\) は本問の状況における確率分布の初期値となる．
本問で最終的に求めたい値は \(i\) の全ビットが on になるまでの時間の期待値であるが，これは「\(t\) 回ガチャを回し，未だに on になっていないビットが存在する確率」の \(t = 0, 1, \ldots\) に関する総和と言い換えられる．したがって，この値は $$ \sum_{i=0}^{2^N - 2} \left( e[i] + (e \ast g)[i] + (e \ast g \ast g)[i] + (e \ast g \ast g \ast g)[i] + \ldots \right)$$ と書き表せる．とりあえず \(e + (e \ast g) + (e \ast g \ast g) + \ldots \) が収束するものと仮定し（パチンコ）*1，これを \(h\) とおくと，この \(h\) が求められれば本問題は解けたことになる．
\(h\) に関して，$$e + (h \ast g) = h$$ すなわち $$h \ast (e - g) = e$$ が成り立つ．演算 \(\ast\) が「各配列のゼータ変換・2配列の対応する要素同士の要素積・配列のメビウス変換（ゼータ変換の逆変換）」と書けることを考えると，（通常の OR convolution の順序を逆に辿ることで）既知の \(e\) および \(e - g\) から \(h\) が求められる*2．よって本問は解けた．
実装例
World Tour Finals 2019 C1: Triangular Lamps Easy
まず，問題を言い換えて状況を整理する．のランプに加え，最初から
個のランプも点灯しているとみなし，うまい操作によって全てのランプを消灯させられるような
を求めればよい．
ここで，「点灯しているランプのうち最大のy座標」が小さくなるように操作を繰り返すことを考える．
考察として，初期状態で点灯しているランプが1つだけの場合（簡単のため座標とする）を検討する．
手を動かして実験すれば，ちょうど
より上側のランプを全部消灯し終えた時点で，
のランプの点灯・消灯が
に対応していることがわかる．この値はLucasの定理を用いて非常に簡単に求められて，特に
が(2のべき乗)-1のときは全ての値が1になる（伏線）．
任意個のランプが点灯している場合も，線形性より，各ランプからの寄与を計算してxorをとれば，より上側のランプを全て消し終えた段階での
でのランプの点灯状況がわかる．具体的には、初期状態で
個のランプ
が光っていたとして、y座標が
より大きいランプが全て消えている状態になるまでの操作をちょうど終えた段階で、
における点灯状況は
で表される．
のランプを加えた
個のランプに対して点灯しているランプのy座標の最大値を減らしていく操作を続ければ，いずれ全てのランプが消灯するはずであるから，
個のランプに対して操作を繰り返した時の点灯状況は
のランプに対して操作を繰り返した際のそれと一致しなければならない（mod 2で考えているため）．
ここで，Lucasの定理より，十分小さいy座標として例えばをとると，
個のランプに対して計算した
は
をみたす任意の
に関して
, 他の任意の
に関して
になる．直線
上で，
の値が0から1へ変わる地点
を二分探索で求めれば，これが求めたい
である．
