titiaのノート: AtCoder Regular Contest 160

2023年5月16日火曜日

　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が取れませんでした。

　自力AC。

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

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

　解説AC。

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

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

　また、

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

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