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 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 Beginner Contest 241（Sponsored by Panasonic）

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

C 縦横斜め四方向(8/2)について6マス中4マスが塗られているか調べる。一方向忘れた&端の処理のミスで4WA。
D ordered multiset案件。座標圧縮してBITを使ったため実装に苦労。
E 繰り返し部分を求める。ダブリングも考えたけどよく分からなかった。やや実装難。
F 座標圧縮して01BFS。ほぼ実装問題。

— titia (@titia_til) February 26, 2022

G - Round Robin

　解説AC。

　フローで判定する問題。

　問題文を読んでフローらしさを感じるのは難しいけれど、「iさんがx勝で他の人たちがx勝未満、という状況は可能か？と捉えると、フローを使いたい気持ちにもなるか。

Ex - Card Deck Score

　解説放送を見て、さらに解説も参考にAC。

　形式的ベキ級数には慣れないが、この問題は形式的ベキ級数を用いて立式しようという気持ちになり、立式はできた。

　問題はその後の式変形。部分分数分解を用いた後、さらに

$\frac{1}{1-x}=1+x+x^2+x^3+\dots$

　を用いて変形するところはテクニカルに見えるが、慣れればできるのかなぁ。

　なお、解説放送でBostan–Mori のアルゴリズムの解説もしてくれたのはありがたかった。これで典型90埋まるかも？