Polynomial Root Finding (Mod 998244353)
乱択を用いない解法です。
問題文
\( \mathbb{F}_{998244353} \)上の次数 \( N \)の多項式 \( f(x) \) が与えられるので、\( f(a) = 0 \) となる\(a \in \mathbb{F}_{998244353}\)を列挙してください。
制約: \( 1 \leq N \leq 4000 \)
解説
以下、特に注釈がなければ数式は\(\mathbb{F}_{998244353}\)上のものとします。
また、
\( p = 998244353 \)、
\( d \) は \( 8 \leq d \leq 23 \) を満たす整数、
\( r \) は \(\mathbb{F}_p\) における原始根とします。
-
\( a=0 \) は別途チェックすることにして、以下\( a \neq 0 \)とします。
\( f_0(x) := f(x) \)
\( i \geq 0 \) に対し \( f_{i+1}(x) \)は\( f_{i+1}(x^2) = f_i(x)f_i(-x) \) を満たす多項式とすると、
\( f_{i+1}(a^2) = 0 \)
\( \Leftrightarrow f_i(a) = 0 または f_i(-a) = 0 \)
が成り立つので、\( f_{i+1}(x) = 0\) の解が列挙できれば \( f_i(x) = 0 \) の解も列挙できそうです。
ここで \( 1 \leq i \leq d \)に対し\( \{ t^{2^i} | t \in \mathbb{F}_{998244353}, t \neq 0 \} = \{ 1, r^{2^i}, (r^{2^i})^2,..., (r^{2^i})^{(p-1)/2^i-1} \} \) であることを考えると、
\( f_i(x) = 0\) の解として考慮する必要があるのは高々\( \frac{p-1}{2^i} \)個になります。
特に\( i=d \) の時\( \frac{p-1}{2^d} \)個となり、\(d\)を十分大きくとれば多点評価のアルゴリズムが使えます。(等比数列上の多点評価になります)
\( f_d(x) = 0 \) の解が\( \{ r^{2^dt_0}, r^{2^dt_1}, ... \}\)と得られた時、
\( f_{d-1}(x) = 0 \) の解の候補は\( \{ (r^{2^{d-1}})^{t_0}, -(r^{2^{d-1}})^{t_0}=r^{2^{d-1}t_0+(p-1)/2}, (r^{2^d})^{t_1}, -(r^{2^{d-1}})^{t_1}=r^{2^{d-1}t_1+(p-1)/2}... \}\)
を考えればよいので、これらに対し\(f_{d-1}\)を多点評価して0にならないものを除去し、以下\( i=d-2, d-3, ..., 1, 0 \) と計算していけばよいです。(こっちは通常の多点評価になります)
\( f_i \)の次数はすべて\(N\)なので解は常に\(N\)個以下であり、考慮する解の候補の数は常に \( 2N \)で抑えられます。
計算量は、
- \(f_1,...,f_d\)を計算するのに\(\mathit{O}(dN\log N)\)
- \( f_d(x) \) 上の多点評価が \(\mathit{O}( (N+ \frac{p-1}{2^d} ) \log (N+\frac{p-1}{2^d} ) ) \)
- \( f_i(x) \) ( \( 0 \leq i \leq d-1 \)) 上の多点評価が \(\mathit{O}( dN \log ^2N ) \)
であり、全体で \(\mathit{O}( (N+ \frac{p-1}{2^d} ) \log (N+\frac{p-1}{2^d} ) + dN \log ^2N) \)となります。
私の提出では\( d=12 \)としています。(3番目の多点評価が重いのでなるべくこっちの回数を減らしたほうが良さそうです)
提出
https://judge.yosupo.jp/submission/274540 (ACLのconvolution使用、329ms)
現在のFastestは217 msで、更新を狙ってみたのですが、断念しました。
高速な自前convolutionを用意するか多点評価まわりの定数倍改善をするといけそうな気がします。
追記(2025/3/24)
\( f_{i+1}(x^2) = f_i(x)f_i(-x) \) の部分はBostan-Moriのアルゴリズム(https://qiita.com/ryuhe1/items/da5acbcce4ac1911f47a)に出てくるものでそこから思いついた解法なのですが、改めてリンク先の記事を読むと、\( \mathbb{R} \)上の多項式に対し同様の変形をして解を求めるGraeffe法(https://en.wikipedia.org/wiki/Graeffe%27s_method)というアルゴリズムが紹介されていました。
Graeffe法では解を2乗、4乗、...としていくことで解同士を「分離」し、近似解を求めていますが、この記事で説明したように、\(\mathbb{F}_p\) 上の多項式で同様の操作を行うと、解自体の候補が1/2倍、1/4倍、...とどんどん絞られていくことになります。(p-1が2で割れる回数だけ繰り返せます)
というわけで、先行研究の調査不足で車輪の再発明をしてしまっていたようです。一応(競プロ的手法に特化した)後半部分はオリジナリティがあると思っているのですが、ちゃんと調べられていないので、論文など情報を知っている方は教えていただけると助かります。
競技プログラミングの練習法
AtCoder赤の自分が考える効率の良い練習法を紹介します。
効率の良い、といっても決して「楽な方法」ではないことはあらかじめ申し上げておきます。
私はAtCoderとProjectEulerぐらいしかやっていないので以下ではAtCoderの問題を使った方法を紹介しますが、別のサイトを使用する場合でも基本的に考えは変わりません。
無駄に長くなったので急いでいる人は最後のまとめだけ読んでください。
解く問題を選ぶ
AtCoder Problemsを利用して適当に問題を選びます。
このときなるべく機械的な方法で問題を選んだほうが良いです。(ABCの青diff以下をを新しい順に埋める、Recommendationで1番目に出てきたものを解く、等)
なぜそうするのかというと、苦手な種類の問題を避ける言い訳を作らないようにするためです。
得意を伸ばすよりも苦手をなくすことのほうが実力は上がりやすいです。 *1
加えて、問題の解法を知らないまっさらな状態で問題に取り組める利点もあります。
ただし、解説AC前提で自分の実力を大幅に超えた問題に取り組むのはあまりおすすめしません。*2
1問の解説を理解するための壁が多すぎると、内容を追うだけになり、どこが重要なのかが不明瞭になるからです。
1問につき1つのテクニックを覚える・復習する、という感覚で取り組めるぐらいの難易度帯にとどめておくのがいいでしょう。
問題を解く
選んだ問題をコンテスト時と同様に解いてみます。
本番のコンテスト時と違って時間のプレッシャーがないので、やや丁寧目に取り組むのがよいでしょう。(解法の証明をしてから実装する、提出前にコーナーケースを確認する、綺麗な実装を心がける、等)
普段から丁寧に解く癖をつけておくと、コンテスト時の焦りの中でもミスに気づきやすくなります。
自力で解けた場合
おめでとうございます。早く次の問題にいきたいところですが、以下の点を確認しましょう。
- 解説・別解を読む。
自分の解法よりもずっと簡潔な想定解があるかもしれません。ただし、「レベルの高すぎるユーザー解説」は適当に流してかまいません。 - 実装や場合分けで苦労した部分は他の人の実装を見てみる。
たとえ自力でACしたとしても、面倒な実装方針を選んでしまっていた、というのは十分反省点たりえます。
公式解説の実装例、もしくは「同じ言語+提出が早い順」で何個かチェックして読みやすいものをピックアップすれば十分でしょう。
解けない場合
諦めて解説を開きます。
どれぐらい考えてから解説を見るのが良いか？という所が悩ましいですが、私は「もう何も思いつかないだろうと思ったら」解説を開きます。時間にすると大体長くて1時間ぐらいで、本当になんの手立てもなければ30分以内に開くこともよくあります。
個人的な感覚ですが、集中力が持続している間に解説を見てしまったほうがより記憶に定着するような気もしています。
解けなかった問題の反省
解説を読むときは「どこまで解けて、どこでつまづいたか」をチェックしましょう。
例えば「DPで解くという予想は立ったが、何をキーに置けばよいかわからなかった」「決め打ち二分探索にする発想がまったく頭になかった」「式変形を間違えていてサンプルが合わなかったため、正しい解法なのに諦めてしまった」など、自分が解けなかった理由を言語化して明確にすることが重要です。
ただ、ここで「自分が全く知らないテクニックだった」という場合はあまり悲観する必要がありません。知らないものはどうしようもないので、覚えるだけです。
むしろ反省すべきなのは「過去に見たテクニックが思い出せなかった」「過去の自分と同じミスをした」という場合です。テクニックが使える問題の特徴やミスの原因を必ず明確にしておきましょう。
自分はこのような反省すべき問題を記事にまとめて、Ratedの直前に見返していました。
当然ですが、解説を読むだけでなく必ず実装・提出してACを得ておきましょう。
方針だけ理解したつもりになって重要な部分を見落としている危険があるためです。
苦手な問題を見返す
先ほど述べましたが、自分は解けなかった問題をメモにまとめて定期的に見返していました。
まず問題文を読んで、解法のざっくりとした流れが即座に頭に浮かぶかを確認します。基本的に「もう一度解く」ということはしません。
一度解いた問題なので解法はすぐに思い出せなければなりません。思い出せないようであれば再び解説を読む、もしくは自分のACコードを見るなどして解法を再確認します。
とはいえここには時間をかけず、短いスパンで全体を一周するのを繰り返したほうが(多分)良いです。
解法を抽象化する(レベル高め)
問題のレベルが上がると、1つのアルゴリズムやテクニックで解決する問題が少なくなり、アドホックな解法ばかりに思えてきます。
そのような場合でも、本当に他の問題に応用できないか？ という視点で解法を考察することが重要です。
たとえば「この問題において、解法のDPで計算量が削減できるのは状態数が十分少ないから」ということが言えると、そこから「状態数が少ないのは問題に特殊な制約があるから」「ということは同じような制約がある問題には同様の解法が使えるのではないか」「別の形の制約だったらどうなるか」「前に解いた問題と似ているかもしれない」と考察を深めていくことができます。
テクニックは抽象化することで応用できるようになるので、このような作業は非常に重要です。
ただし、これは十分に解法の引き出しがある状態でないと難しい練習法です。解いてない問題があるうちは、基本的にはたくさん問題を解くことを優先したほうが良いでしょう。
その他のトピック
ライブラリ整備について
重要な点として、持っているライブラリの個数は実力とは無関係です。「必要になったら作る」「同じ実装を何度もやっていると感じたら作る」ぐらいの感覚でいいと思います。
もちろんライブラリ整備自体が楽しくなってそれを目的とするのは否定しません。虚無埋め(簡単ですぐに解ける問題を大量に解くこと)について
タイピング練習に使えたり、ABC361-Bのような穴になりやすい問題もあったりするので、言うほど無駄ではないと思います。座学(問題を解かずに勉強すること)について
個人的な感覚では、必要性が薄いです。基本的にはアルゴリズムやデータ構造は問題の解説で出会った時に覚えれば十分で、「どういう問題なら使えるのか？」をセットで習得できていないと意味がないです。バーチャルコンテスト(本番を想定して、過去のコンテストと同じ問題セット・制限時間で解くこと)について
私はほとんどやったことがありません。本番と同じ緊張感で取り組めるならよいが、後半の時間を持て余すぐらいならさっさと解説を見たほうが無駄がないと思います。
まとめ
- 解けた問題よりも解けなかった問題の振り返り・反省に力を入れる
- 初めて学んだ知識よりも2回以上見た知識をきちんと定着させる
- そのために解法やテクニックはなるべく抽象化・一般化して覚える
参考になれば幸いです。
AHCに取り組む上で心がけていること
先日のAHC032でHeuristc橙を達成した記念の記事です。 この記事では自分がAHCに参加するときに心がけていることを記します。参考になれば幸いです。
問題文をよく確認する
条件を読み間違えたまま考察し始めると悲惨なので、問題文は入念に読むことを心がけています。
また、アルゴのコンテストより時間に余裕があるので、それ以外の要素もしっかり確認します。
- ストーリー
問題のイメージを把握するために重要です。
- 制約
制約を確認しないと部分的に全探索するような解法を見逃す可能性があります。
- スコア計算方法
スコアの計算式から最適なパラメータが計算できることがあります。
- 入力生成方法
テストケースの特徴が解法の本質的な部分に関係していることもあります。
ビジュアライザを活用する
解を出力するプログラムが書けたら、とりあえずビジュアライザに突っ込んでみるのが良いです。
利点の1つとして、まずバグが発見しやすくなります。「山登り法を実装したはずなのに解が悪化している」「そもそも制約に反した解を出力している」といったことにすぐ気づけます。
もう1つの大きい利点が、「自分の解法の悪い部分・改善すべき部分を見つけやすくする」という点です。
例えばビジュアライザが明らかに無駄な動きをしている場合、そのような無駄が生まれない美しい解法に到れるのが理想ですが、次善策として強引に無駄を無くす処理を最後に加えたり、ペナルティを重めに課すようにするだけでもスコアが良くなります。
「最終的な解の理想形」をイメージする
これは結構重要で、ここを正確にイメージできるかどうかが最終的な順位にかなり関わってきます。 ヒューリスティックコンテストは多くの場合最適解を求めるのが困難ですが、「最適解はどうなっているか」を雰囲気だけでもイメージできると、そこから使用するアルゴリズムを逆算できます。
例えばAHC032の場合、最適解は「全てのマスで高得点(90%~95%以上？)」が1つのイメージとなります。 その場合、例えば山登り法や焼きなまし法で、「最適解に近い解」から「より良い解」への遷移を具体的に求めたり、乱択で発見することが困難であるという予想が立てられるでしょう。 一方で「1マスだけ最適な値になるスタンプを押して、そこはもう変化させない」という戦略をとれば、少なくとも81マスのうち49マスについては高得点をとれそうです。
また、スコアの上界を求めるのも1つの有効な戦略です。
例えばAHC027では、各マスを訪れる回数を√dに比例させ、かつ等間隔で訪れるものが理論上最適な解であることがわかります。これに近いものを貪欲的に求めたものを初期解として焼きなましなどで改善する手法が有効でした。
なお、この戦略は「理想的な解」のイメージを間違えてしまった場合の修正が難しいというデメリットがあり、特に操作の自由度が高い長期コンの場合に起こりがちです。
私はAHC025で、「最適解では全てのアイテムに対する重さの比がほぼ完全に求まるはずだ」という思い込みから抜け出せず、最後まで良いスコアをとれませんでした。
解を決め打って解く
具体的な解法に近いテクニックですが、「ランダムに最終形を決め打ってそれを達成する手順を求める」を時間の許す限りひたすら繰り返す、という解法が有効なことがあります。(例：AHC011)
アルゴが得意な人が手を付けやすい解法であると思います。
解法を決め打たない、考察の幅を狭めすぎない
例えば「問題文では3種類の操作が与えられているが、効果が薄そうだから操作3は使わなくてよい」などと決めつけて一度考察を始めてしまうと、実際は操作3が必要であってもなかなか原点に立ち返って一から考察することが難しくなります。
とはいえ実践するのは難しく、十分注意していないとコンテスト中の焦りも相まって楽で単純な解法に固執してしまいがちです。
また、アルゴコンでもそうですが、問題を考察する時には「何のアルゴリズムを使うか」から考えてはいけません。 問題に向き合い確実・着実なアルゴリズムを考え、それを改良するという手順で考察するべきです。
パラメータ調整は最後までとっておく
正直これは正しいのかどうかわかりません。適当すぎるパラメータではアルゴリズムの良さも判定できないような気もします。
ただ、パラメータ調整で簡単にスコアが上がるのが楽しいあまりそれに時間を使ってしまうのは当然注意が必要です。
あとがき
とりあえず短期コン1桁順位、長期コン1ページ目を目標としてこれからも頑張ります。
