コンテスト後のツイート
AtCoder Beginner Contest 436 Fが解けずひどい順位に。
— titia (@titia_til) December 13, 2025
C setで管理。
D 01BFS。たくさん行き先がある場合を慎重にケア。
E 連結成分に分け、その中で入れ替える。
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。久しぶりにこのライブラリを使う機会と出会った。
形式的べき級数にもっと慣れないとダメですね。
0 件のコメント:
コメントを投稿