AtCoder Beginner Contest 436

　Eまで。Fが解けずダメでした。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 436 Fが解けずひどい順位に。
C setで管理。
D 01BFS。たくさん行き先がある場合を慎重にケア。
E 連結成分に分け、その中で入れ替える。

— titia (@titia_til) December 13, 2025

F - Starry Landscape Photo

　使う数字の最大値を考えると、それ以下の数字は全て使い、それより大きい数字は消えている。

　なので、使う数字の最大値が大きい順に考えて、一つ一つ消していけばOK。

　コンテスト中は、左端を固定したり、DPを考えたり、使う数字の最小値を考えたりしていた。

　使う数字の最小値を固定する方針にしばらく時間を使った後、最大値を固定する方針も考えたはずなんだけど、なぜか上手くいかない気がしてしまった。

　今見ると、難しく思えないのだが……。なんで解けなかったのか分からない。

G - Linear Inequation

　解説放送を見てAC。

　形式的ベキ級数を使うと聞き、立式まではできたつもりだったのだが、1+x^a+x^(2a)+...をM次の項までで打ち切るなどと考えてしまったのがダメ。

　1+x^a+x^(2a)+...と無限に続くもの同士の積と考えるべき。

　そして、さらに重要なのは、「そのM次以下の係数の和」を、Aに1を付け加えることで、M次の係数と解釈できるようにするところ。全く思いつかなかったが、形式的ベキ級数に慣れている人にとっては典型なのでしょう。

　あとは、Bostan–Mori法を使って処理すればOK。久しぶりにこのライブラリを使う機会と出会った。

　形式的べき級数にもっと慣れないとダメですね。

AtCoder Beginner Contest 352

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 352 Eまで。
A X<Z<Y or Y<Z<X
B 尺取り
C B-aが一番大きいものを最後に。
D SortedSetをお借りしました。
E Cの小さい順に。
F 2-SATで解けそう！　と実装し始めたが上手くいかず終了。あれ、2-SATで解けないの？

— titia (@titia_til) May 4, 2024

 F - Estimate Order

　解説AC。

　重み付きUnion-findで連結成分ごとにまとめた後、bit DPする。bit DP部分をDFSっぽくやって高速化した。

　コンテスト中もまずbit DPできないか考えたはずなのだが上手くいかない気がし、2-SATでいけると勘違いして突き進んでしまった。「どれか一つが真」って条件は2-SATで表せないですね。

　色々ひどかったけど、2-SATの復習は多少できたかもしれない。

G - Socks 3

　解説AC。

・前半の、期待値を場合の数に置き換えるパート

・後半の、場合の数を多項式の積で表し、形式的べき級数で計算するパート

　どちらも典型なのだが、身に着いていない。

　どちらかというと、後者は問題演習を積めば身に着く気がするので、前者の方がより身に着けたい内容か。期待値を、「i回以上である確率P_i」の和で表すという方法は覚えておきたい。

yukicoder contest 399

　ABの二完。Cを考えているときに体調が悪くなり撤退。

コンテストへのリンク

No.2394 部分和乗総和

　自力AC。

　しばらく分からなかったが、形式的ベキ級数に思いを馳せたら解けた。

No.2395 区間二次変換一点取得

　自力AC。

　各indexごと独立なので、各indexについて何回クエリが適応されているかだけ見れば良い。

　問題文を理解するのがちょっと難しいけど、理解してしまえばBやCより簡単では。

AtCoder Regular Contest 160

　B一完で青に落ちた。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 160 B一完でダメでした！
A 順番に小さい方から試すんだと思うけどWA
B √Nで分けることはすぐ気付いたけど実装に苦戦。

— titia (@titia_til) May 14, 2023

A - Reverse and Count

　落ち着いたら自力でACできた。

　i番目の数字がxにできるか試すとき、x!=iなら、xにする方法は一通り。

　i=xなら、xにする方法は、L, Rとしてi+1以降の二つを選ぶか、L=Rとするか(*)。

　さて、前者ならそこで答えが求まる。

　後者のとき、Kがその場合の数以下であれば、ANS[i]=iと分かるので、そこを確定させ、次のi+1に移れば良い。

　方針はコンテスト中に立っていたけど、最後まで間違っていたのは(*)の場合の数の計算でした。0-indexなら、i+1+(N-i)*(N-i-1)/2なのですね。L=Rの場合の処理で混乱してしまった。最初にiを足すのを忘れてWAが取れませんでした。

C - Power Up

　自力AC。

　小さい方から合成していき、xがy個あるときは何通りか？　というのを順にDPしていけば良い（高速化に累積和を使う）。

　コンテスト中は問題文は読んだけれど解法は思いつかず、解けそうなAに戻りAに集中していた。Aを飛ばしていればコンテスト中に解けた可能性はあるけど、結果論だからねぇ。

D - Mahjong

　解説AC。

　けんちょんさんの記事を参考にしたが、形式的ベキ級数を導出する部分が理解できず、maspyさんの記事を参考にすることで何とか理解できた。Bostan-Moriのライブラリは作ってあったのだから、形式的ベキ級数に関する理解も深めたい。

　とりあえず、難しい問題は分からなくとも、maspyさんの記事の「例題」の部分はしっかり頭に入れ、使えるようにしておきたい。

　また、

・総和がMなどという条件は形式的ベキ級数を使いやすい

　ことは押さえておきたい。

AtCoder Regular Contest 144

　Cまで三完だが、遅かったためレートを下げた。解いている最中はそれほど遅い気がしなかったのに、順位は悪かったので、（自分では分からなかったが）体調が悪かったのかもしれない。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 144 Cまで
A 5以上は繰り上がるから使っちゃダメ
B 二分探索
C iより大きいか小さいかで実験したら規則が見えた
D 実験したらhttps://t.co/CqXGwDE88Sが出てきた。これを使って形式的ベキ級数でいけるのか？　と思ったが慣れてないため分からず終了。

— titia (@titia_til) July 16, 2022

D - AND OR Equation

　解説ACだが、今見返すとチャンスはあった。

　実験してoeis（これやこれなどが出てくる）と見比べれば${(1+x)}^N/{(1-x)}^{(N+2)}$の$K$次の係数と分かる。

・${(1+x)}^N$は、二項定理を使って展開

・${(1-x)}^{(N+2)}$は、$1/(1-x)=1+x+x^2+x^3+...$とできることを利用すると重複組み合わせにより二項係数になる

　を利用すれば求められる。

　ただし、二項係数を求めるとき、Kが998244353に近い値のときは気をつけて計算しなくてはいけない。（コンテスト中に、ここの処理まで上手くできた可能性はかなり低そう……）

　コンテスト中、形式的冪級数で表すところまではできていて、その後は多少技巧的ではあるが自分で思いつける変形だった。

　特に一番目、二項定理を使おうとも考えなかったのはひどい。形式的冪級数を使うならここは押さえねば。

AtCoder Beginner Contest 159

　Eまでは比較的早かったけど、Fが解けなかった。

コンテストへのリンク

F - Knapsack for All Segments

　maspyさんの解説（形式的べき級数を使った方法）が分かりやすい。公式解説動画もこの方法を使っていた。

　この問題に出会うまで形式的べき級数に関して勉強する気はあまり起きなかったけれど、この問題に出会ったことで勉強する機運が高まった。（maspyさんの記事は一応読みました）

　しかし、その後に出た類題を解けなかった（訂正：一応時間内にACはしていました。すごく時間がかかったし、形式的べき級数を思いつきませんでしたが）のを見ると、理解が足りていなかったようだ……。