気象道場の「勝ち方」、教えます

皆さんは、気象道場というものをご存じでしょうか？

ひとことで言うと 競技天気予報 です。多分世界初。

主に「試合」と呼ばれるゲームについて、基本的には以下を行います。

• ある日およびある時点での、1つまたは(地理的に近い)複数のアメダス地点における何らかの観測値を予報する。
  • 予報するものの種類として以下のような項目がある。
    • 3時間程度ごとの数個のアメダス地点、あるいは特定の時刻における複数のアメダス地点における以下の測定値
      • 気温
      • 降水量
      • 風速
    • 特定の1日の以下の測定値
      • 最高気温
      • 最低気温
      • 降水量
      • 最大風速
  • ひとつの試合は、概ね 16-24 個程度の測定値の予報が求められる。
• 実際に測定が完了した後、予報の精度において判定が下る。
  • 一本 (得点率 $100$ %)
  • 技有 (得点率 $[50,100)$ %)
  • 有効 (得点率 $(0,50)$ %)
  • 無効 (得点率 $0$ %)
• ゲーム全体における得点の総和の多寡を競う。

(主に「演武」と呼ばれるゲームにおいて、例外もあります)

私は、 2026/08/11 時点において(幸運にも)レーティング全一を達成することができています。

しかし、気象の知識で無双している訳ではなく、どちらかというとメタ的な要素に勝因があると思うので、ここに私なりの攻略法を書き留めておきます。

おことわり

本記事の現在の版は、 2026/08/11 時点の情報をもとに執筆されています。

本記事は以下の理解を前提とします。

• 中学および高校で習う理科の基本的な知識
• 高校および大学の教養課程で習う統計の基本的な知識

逆に、これだけの知識があれば、十分に気象道場の上位勢を狙うことができると筆者は考えております。是非ご参加ください！

また、記事中の各所にて、(有識者に怒られてしまいそうなほど)非常に単純化した数理モデルの導入を行います。ご了承ください。

予報資料を活用せよ

気象道場では予報資料が配布(将来的には販売)されます。これを利用しない点はありません。予報資料には ここで説明されている GSM, MSM の予報が存在します。これらをベースにすることで大外しすることはあまりなく、逆にこれらが大きく外れればコンテストの難易度自体が非常に高くなり多くの参加者が大きく予報を外す難しい回になります。なので、基本的にはここにある数値予報を参考にすれば十分です。

得点計算を掌握せよ

どのような予報をするとどのような得点が得られるかをざっくりと把握しておくことは、どう予報を出すとどのシナリオをケアできるかを判断するのに重要です。いい機会なので GPT 5.6 Sol に調査してもらいました。

要素	配点	得点式 ($d$ を誤差とする)
気温	$\displaystyle 200$ (固定)	$\displaystyle \lfloor 200 e^{-1.25d^2} \rfloor$
風速	$\displaystyle P$	過小予報: $\displaystyle \lfloor P e^{-d^2} \rfloor$ 過大予報: $\displaystyle \lfloor P e^{-d^2/4} \rfloor$
降水量	$\displaystyle P$	過小予報: $\displaystyle \lfloor P e^{-d^2/q} \rfloor$ 過大予報: $\displaystyle \lfloor P e^{-d^2/(4q)} \rfloor$

観測値によって風速では $P$ が、降水量では $P$ に加えて $q$ も変動します。

気温については誤差の絶対値に得点が依存し、風速・降水量については過大誤差は過小誤差の半分として扱われます。また、得点率のグラフから、風速・降水量は思った値よりほんの少しだけ大きく予報する方が得点期待値は高くなります。

気温

概ね ±0.4℃ 程度の範囲であれば満点の 8 割を回収できます(その程度の誤差には寛容と考えるとよいでしょう)。そこから ±1℃ に至るまでに急激に得点が下がり、誤差 1.2℃ を超えた領域ではほぼ点数が入らないと捉えてよいでしょう。

風速

過大誤差が過小誤差の半分として扱われます。

風速は絶対誤差に得点が依存します。

過小は 0.5m/s 、過大は 1.0m/s 程度外しても 8 割程度の得点が来るので、特に穏やかな日では稼ぎ頭になります。

降水量(前1時間)

過大誤差が過小誤差の半分として扱われます。

降水量が少ない時は $q$ がかなり厳しくなります。

なお、アメダスでは降水は 0.5mm 刻みで測定されることに注意してください。

日降水量

過大誤差が過小誤差の半分として扱われます。

前1時間降水量に対し、やや $q$ が緩めです。

成績を安定させるのではなく、1位を狙うべし

気象道場のレーティングシステムには、(競技プログラミングでもよく知られる)パフォーマンスの概念があります。パフォーマンスとは、ざっくり言うとそのコンテスト一度だけで判断した場合のレーティングです。

厳密には違いますが、競技前のレーティングを $r$ 、競技でのレーティングを $p$ とすると、競技後のレーティングは $r+0.2\times(p-r)$ となります。ただし、そのコンテストの平均の50%以上の得点が得られていればレートは減少しないように補正されます(詳細は後述します)。

ここに、コンテスト前のレーティングとパフォーマンスからコンテスト後のレーティングをざっくりと見積もるプロットを掲載します。さらに、パーセンタイルが 90% 以下であればレーティング非減少の補正を受けられると仮定します。

実際は得点偏差による効果やひとつのコンテストで変動するレーティング幅の制限があるため、これに必ずしも従うとは限りません (辛勝だと上昇幅が小さく、大勝だと上昇幅が大きくなります)。

これを見ると、レーティング 2000 でパーセンタイル 35% 以下、 3000 で 14% 以下、 4000 で 4% 以下程度を狙わなければレーティング上昇は見込めないことが分かります。

さらに、極めて上位においてパフォーマンスが急峻に上昇するため、基本的には安定してそこそこ当たる予報よりも、多少失敗しても良いので 1 位を狙いに行く予報が強いことが分かります。

一貫性のある予報をせよ

重要度が高いです。

予報の一貫性とは何でしょうか？例えば、課題地点が以下の位置関係にあったとします。

このとき、 A,B,C 各群の計測値には強い相関があるはずです。

例えば以下のシナリオがあるとしましょう。

• α: 昼間の気温が 25 ℃ 程度で推移する。
• β: 昼間の気温が 25.5 ℃ 程度で推移する。
• γ: 昼間の気温が 26 ℃ 程度で推移する。

各群の内部で異なるシナリオを採択することは、上位を狙うことに繋がりません。

図は以下をプロットしたものです。

• 青: 3 つの予報であって、全てが $\mu=0, \sigma=0.8$ の正規分布に従う場合のパーセンタイルと得点
• 橙: 3 つの予報であって、 $\mu=-0.5,0,0.5, \sigma=0.8$ の正規分布に従う場合のパーセンタイルと得点

どちらも全体で平均(符号付き)誤差 0 の予報ですが、一貫性を持たせることで 30 点程度の積み増しが実現できています。

地理的な情報だけでなく、時間などの他の条件についても、近い項目に対して一貫性を持って一貫したシナリオを採択することで、大勝を作り出すことができます。

オフセットを見抜け

重要度が高いです。

数値予報・世の中に出回っている予報とアメダスの測定値との間には、以下のようなオフセットが入ると考えられます。

• 予報地点とアメダス地点との差によるオフセット
• アメダス地点周辺の環境のオフセット
• 数値結果とアメダスの測定値とのオフセット
• 一定時間ごとの測定値と日最高・最低値とのオフセット
• 「どれだけ風が穏やかでも、最低限このくらいは吹く」というオフセット

このオフセットを定数誤差として近似するだけでも、一気に得点が伸びます。

逆に、このようなオフセットをどうにかして補正しないままだと「最初から負けている」ような予報になってしまいかねません。

図は以下をプロットしたものです。

• 青: 3 つの予報であって、全てが $\mu=0, \sigma=0.8$ の正規分布に従う場合のパーセンタイルと得点
• 橙: 3 つの予報であって、 全てが $\mu=0.5, \sigma=0.8$ の正規分布に従う場合のパーセンタイルと得点

0.5℃ のオフセットを補正し損ねた場合、概ね 50 点程度の損失が発生していることが分かります。

レート減少を恐れず、レート減少をしない

気象道場のレーティング計算式にはこんなことが書かれています。

コンテストにおける自身の得点を $s_i$ 、全体の平均点を $\mu$ としたとき、 $s_i$ が $\mu/2$ 以上あればレートが減少することはないのです！

この条件に抵触してしまうのは毎回数人程度、良い時だと 0 人である場合すらあります。理由は以下の通りです。

• 明らかな晴れの日の予報項目に降水量が含まれる場合、予報 0mm 実測 0mm である場合、 50*(降水量の回数) 点がほぼ無条件に得られる。この項目だけでも $\mu/2$ と比較して 25*(降水量の回数) 点だけマージンが得られます。
• 現在の得点計算において、風速の採点が甘い。よほどのことが無い限り、どの予報に従ってどのシナリオを採択しても、ほぼほぼ技有以上の判定を得ることができ、ここでも $\mu/2$ に対して確実なマージンが得られます。
• 多くの参加者の予報および世間に出回っている予報が GSM あるいは MSM ベースなので、そこからあまりにも外れた予報をしてかつシナリオも大外しするということが起こらない限り、 $\mu/2$ 点より低い得点を得ることは滅多にない。今のところ、数値予報に従順な予報を出すという行為の期待値が $\mu$ 点あると考えて構いません。

なので、本当に極めて攻めた予報を行わない限りはこの条件を恐れず、レートが非減少だと考えて勇敢に試合に臨んで良いのです！

ひとつ注意点として、ある項目を空欄で予報してしまうとそこに値 0 が入ってしまい、本当に大変なことになります。うっかり空欄をたくさん作ってしまうとえげつないくらいレートが下がると思います。なので、全項目をしっかりと予報しましょう。

よりよい初期条件を知った上で、直前に予報せよ

物理現象というものは、往々にして初期条件に鋭敏です。8月10日の値を予報する場合でも、8/8の夜に予報する場合と8/9の夜に予報する場合とでは、知ることのできる初期条件に大きな差があります。

特に、翌日3時や翌朝の予報を当てることが要求されている場合、前々日から予報すると30時間程度先を当てる必要がありますが締め切り直前に予報すると3-9時間程度先を当てるだけで済みます。これだけでも当てやすさは段違いです。

どれだけ早くても締め切りの2-3時間程度前まで待ってから精査を始めると良いでしょう。精査に時間をかけすぎて不完全な状態での解答提出が発生しないようにご注意を。

万が一、早期に解答を提出することに成績上でのインセンティブが発生する場合は話が変わってきます。そのようになった場合、知見が溜まってきた頃にここを改筆します。

AIを活用せよ(省エネ編)

AIを活用するのもよいでしょう。

例えば、数値モデルと実況値とのプロットを作成させることで、現在の状況を視覚的に捉えることができます。これだけでもシナリオの採択が相当行いやすいのではないでしょうか？

おまけ: このプロットを見て 3,6,...,24 時の実測値を予報してみてください。反転テキストで正解を書きます。

正解【0.4, 0.4, 1.5, 2.5, 2.9, 1.7, 0.9, 0.8】

また、予報を行うに際して注意すべき現象があるかどうかも AI に調査させることができます。どの項目に不確実性が入るとか、どのようなシナリオがありうるか複数提示してもらうとかができます。

AIを活用せよ(議論編)

AI で省エネができるのであれば、 AI と議論だって出来ます。私は以下のような活用法をしています。

• まず、 AI にも同じ予報資料を渡した上で予報してもらう。(予報 A とします)
• 予報 A を見ることなく自分でも予報を作成する。(予報 M とします)
• 予報 A と予報 M との差を項目ごとに比較する。... ★
  • 予報 A と予報 M が近いものについて、予報 M を採択する。
  • 予報 A と予報 M が離れているものについては、以下の作業を行う。
    • もし予報 M を正当化できる強い根拠があるのであれば、予報 M を採択する。
    • そうでないなら、予報 A を受けた上で自身の予報を精査し、予報 M' とする。また、 AI に対してもその項目の予報の精査を依頼し、予報 A' とする。
    • その後、改めて予報 A' と M' を比較する(★に戻る)。基本的には、 A' および M' を作った時点で M' を採択できるほど品質が向上するが、これでも合わず正当化も出来ない場合、その項目について深い精査をやり直す。 

特に AI の予報と自分の予報が大幅に異なる場合、自分が何かを誤解している可能性があります。そのような項目について納得の行くまで AI に質問を投げかけたり AI と議論を試みたりしてもよいですし、どうしても納得できない場合は自身の予報を貫くと良いでしょう。

打席に立ち続けよ

ここまで散々御託を並べてきましたが、結局のところ最も大事なのはこれです。

各コンテストにおいて得られるレーティングの期待値が正である以上、とにかく試合にしっかりと出続けて、バットを振り続けることが最も強いです。

ある時は連続で停滞してモチベーションが下がってしまうかもしれません。また、ある時はレート減少を喰らってしまうかもしれません。だとしても、懲りることなくリングに登り続け、ひたすらに闘うことが最も単純で、最も強い戦術です。

ひたむきに挑み続ける姿勢こそが、最も実を結びます。

どうでしょうか。実際はもう少し無意識化で行っていることがあると思いますが、自分が行っている方法をなるべく詳しく言語化してみました。皆様の成績向上の役に立てたのなら幸いです。

Zhily and Cycle (CFR1097-D1D)

Problem - D - Codeforces

長さ $n$ の数列 $a$ が与えられる。

以下の条件を満たす長さ $n$ の有向サイクルグラフが存在するか判定し、あるならひとつ構築せよ。

• 頂点集合が $1,2,\dots,n$
• 頂点 $u$ の次の頂点を $succ_{u}$ と表記する。このとき、 $succ_{i} \ge a_i$ が全ての $i$ について成り立つ。

「サイクルを取る」必要性が問題を見えにくくしているので、以下のように言い換えてみる。

長さ $n$ の順列 $s$ であって、 $s_i \ge a_i$ が全ての $i$ について成り立つようなものを求めよ。 ... ★

これなら自明で、 $a_i$ 昇順にソートして貪欲に取ればok。

この解法が駄目な場合は、 $s$ を $succ$ とみなしてサイクルを成していない場合である。なので、 $s$ を少しいじってサイクルを成すようにしたい。

そこで、 $i=2,3,\dots,n$ について以下を行うことを考える。

• 現在 $i-1$ と $i$ が異なるサイクルにあるとき、このふたつのサイクルをマージしたい。
  • $s_u={i-1}$ なる $u$ 、 $s_v=i$ なる $v$ に着目する。
  • これを $s_u=i, s_v=i-1$ と書き換えることによって解決したい。
  • このとき、問題文中の条件を満たさなくなる恐れがあるのは $s_v$ のみである。
    • $s_v-1 \ge a_v$ であれば swap を行っても許される。
    • $i$ を昇順に回しているため、この危険が発生するのは各要素について高々一度である。

実は、この改変を行った結果合法な解が得られている、またその時に限り答えは Yes である。

略証:

★の問題に解が無い時は本問題にも明らかに解が無いため、そのような場合を排除する。

上記の swap が棄却されない時、明らかに必ずサイクルが得られる。

上記の swap が棄却された時を考える。

swap が棄却される時、その $v$ について $s_v=a_v=i$ を満たしている。なので、 $s_w=j$ ($1 \le j < i$) なる頂点 $w$ の集合 $W$ について、 $W$ に含まれる頂点の行き先の集合を $\{1,2,\dots,i-1\}$ としなければいけないことが分かる。ところが、棄却された swap は $W$ 中から要素をひとつ取り出して行き先を $i$ にすることを意味するので 、この点でのマージを受理させることはどのような実行可能解についてもできないことが分かる。

すると、改変の結果がマージを行えるだけ行った、あらゆる実行可能解についての最善の結果となっていることが分かるため、証明が完了した。

https://codeforces.com/contest/2223/submission/373781723

なんか複雑に考えすぎてしまって正当性が見えなくなってしまっていたなぁという気持ち。難しい。

Rainbow Branch (CFR1064-D1E)

https://codeforces.com/contest/2165/problem/E

$N$ 頂点の木が与えられる。

$k=1,2,\dots,N-1$ について、以下の問題に答えよ。

• 木の各辺を色 $1,2,\dots,k$ で塗り分けることを考える。ただし、全ての色を少なくとも $1$ 度は使わなければならない。
• $f(u,v) = $ $u$ から $v$ へのパス上に塗られた色の種類数と定義する。
• 塗り分けの 不便さ を $\displaystyle \max_{1 \le u,v \le N} f(u,v)$ と定義する。
• 達成可能な不便さの 最小値 を求めよ。

$3 \le N \le 3 \times 10^5$

公式解説ベースで、自分が分からないところを補間しながらまとめます。

取り扱いやすいように、本問題の key と value を入れ替える。即ち、不便さが $l$ 以内となるような塗り分けで最大何色使えるかを考える。

まず、次の主張を確認します。

最適な塗り分けにおいて、各色の辺だけ見た時、色ごとに $1$ つの連結成分を成す。

色 $c$ に非連結な複数の成分があったとします。このとき、最も「外側」(厳密には、色 $c$ で補助木を考えた時の葉にあたる成分) の連結成分 $X$ に対して次が成り立ちます。

• 連結成分 $X$ から他の色 $c$ の連結成分 $Y$ に向かう時に最初に通る辺の色を $d$ とする。このとき、 $X$ 全体を色 $d$ で塗っても不便さは大きくならない。

以下の図だと、丸を付けた色 $1$ の連結成分全体を色 $4$ で塗ることに相当します。

丸を付けられた方の色 $1$ の連結成分が $X$ 、そうでない色 $1$ の連結成分が $Y$ です。

• 元から $X$ も $Y$ も通らないパス
  • 何も起こらない。
• 元から $Y$ のみを通るパス
  • 何も起こらない。
• 元から $X$ のみを通るパス
  • $Y$ を根と考える。
  • $X$ の子から $X$ に入り、 $X$ の子に向かって出ていく場合
    
    • この場合、パス中で $X$ が唯一の色 $1$ の連結成分である。
    • この場合、色 $1$ の役割が色 $4$ に変わるだけなので、この塗り替えで不便さは大きくならない。
  • $X$ の親から $X$ に入り、 $X$ の子に向かって出ていく場合
    • この場合、 $X$ に入る時に色 $4$ の辺を通ることになるので、この塗り替えで不便さは大きくならない。
• 元から $X$ も $Y$ も通るパス
  • $X,Y$ 間の移動において色 $4$ の辺を通ることになるので、この塗り替えで不便さは大きくならない。

この塗り替えを繰り返していくことで、各色が $1$ つの連結成分を成すまで変形していけるので、題意が示されました。

ところで、この問題では、木の直径のようなものを訊いています。なので、木の中心のような量を考えることが筋良です。参考 類題

不便さの最大値を $d$ と置く。このとき、実際に $d$ を達成するパスに着目することで、以下が発見できます。これ以降、これらを 核 と呼びます。

• $d$ が奇数であるとき、核は辺である。
  • 核から全ての葉に向かう際に通る色の種類数が $(d-1)/2$ 以下である。
• $d$ が偶数であるとき、核は頂点である。
  • 核から全ての葉に向かう際に通る色の種類数が $d/2$ 以下である。

引用: 公式解説の図

この核を使って、次の事項を証明します。

• 核からの色数の条件を満たす塗り分けを考える。
• ある葉から核に向かうパスについて、色が $a-b-c-c-d-e-\dots$ のようになっている(葉から辿って行って、色の境界が葉から始めて連続で発生していない)部分がある。この時、このパスの色を $a-b-c-d-d-e-\dots$ のように変更して使える色数が減ることはない。
• より端的には、色の境界を核から葉の方向に押しても損しない。

この図を見てもらうとわかりやすいが、部分木中の数字はその部分木で残り使える色の種類数を表す。確かに、境界を葉に向かって押した場合が押さなかった場合の上位互換となっていることが分かる。

あとは、部分木中で新たに適切に新色を導入すれば得できる。

これを、このような操作ができる限り繰り返せば良いことになる。

ここまでの議論をまとめると、

• 核は存在せざるを得ない。
• 核があるとき、色の境界を核から葉に向かって押せるだけ押すのが最適である。

ここから、許されている不便さの最大値 $d$ の偶奇別に、以下の最適な構築ができる。

• $d$ が奇数であるとき
  • 核は辺である。
  • 核が存在せざるを得ないので、核から葉に向かって最大 $(d-1)/2$ 色しか使うことが出来ない。
  • このもとで、可能な限り葉に向かって色の境界を押すことを考える。
  • すると、以下の手順で塗り分けることが最適となる。
    • 以下を $(d-1)/2$ 回繰り返す。
      • 現在の木の葉に繋がる辺を異なる色で塗り分ける。その後、それらの葉と辺を取り除く。
    • 残り使えるのはパス当たり $1$ 色なので、残った辺が全て核である。
• $d$ が偶数であるとき
  • 核は頂点である。
  • 核が存在せざるを得ないので、核から葉に向かって最大 $d/2$ 色しか使うことが出来ない。
  • このもとで、可能な限り葉に向かって色の境界を押すことを考える。
  • すると、以下の手順で塗り分けることが最適となる。
    • 以下を $(d/2)-1$ 回繰り返す。
      • 現在の木の葉に繋がる辺を異なる色で塗り分ける。その後、それらの葉と辺を取り除く。
    • 残り使えるのはパス当たり $2$ 色である。
    • なので、残った頂点のうち現時点での次数が最大のものを核とし、その頂点周りの辺およびそこから伸びる連結成分を全て異なる色で塗れば最適である。

引用: 公式解説の図　再掲

https://codeforces.com/contest/2165/submission/349759306

公式解説だけでは解法の正当性が腑に落ちなかったのでメモ。

自力でも葉のレイヤを求めるみたいなことには辿り着けてサンプルは通ってたんだけど、通し切るまでもう一段かかるなぁという印象。

2 h 6 問の 5 問目だから落として許されてるところあるけど、 3 h だったら通したい問題ですね...

FPS 24 題に「ちゃんと」取り組む #4 (fps24-D)

A	B	C	D	E
F	G	H	I	J
K	L	M	N	O
P	Q	R	S	T
U	V	W	X

D - Sequence 2

$M $ 以下の非負整数からなる長さ $N$ の整数列 $A$ であって以下の条件を満たすものを数えよ。 ${\rm mod}$ $998244353$

• $A$ を昇順ソートした列 $B$ について、隣接する要素の偶奇が異なる。

$1 \le N,M \le 2 \times 10^5$

本番解法:

$B$ の要素は明らかに相異なるので、並べ方の自由度が $N!$ ある。このもとで $B$ を数えることにする。

$B_N-B_1$ を $N-1,N+1,N+3,\dots$ と固定。このもとで公差を「 $2$ ずつ配る」ことを考える。これは二項係数で求まる。

最後に $B_1$ の自由度ぶん係数を掛ければ ok。

https://atcoder.jp/contests/fps-24/submissions/70656350

FPS 解は以下の通り。

$B$ を数えて $N!$ 倍するところは同じ。

求めたいものは次のように書ける。

$[x^M] (1+x+x^2+\dots) \times (x+x^3+x^5+\dots)^{N-1} \times (1+x+x^2+\dots)$

$=[x^M] (1+x+x^2+\dots)^2x^{N-1}(1+x^2+x^4+\dots)^{N-1}$

$=[x^{M-N+1}] (1+x+x^2+\dots)^2(1+x^2+x^4+\dots)^{N-1}$ ... ★

$\displaystyle =[x^{M-N+1}] \frac{1}{(1-x)^2} \times \left ( \frac{1}{(1-x^2)} \right ) ^{N-1}$

ここで手が止まってしまって解説を見に行く。分母の因数分解をすれば良いらしいがまだ慣れないなぁ...

$\displaystyle [x^{M-N+1}] \frac{1}{(1-x)^2} \times \left ( \frac{1}{(1-x)(1+x)} \right )^{N-1}$

$\displaystyle =[x^{M-N+1}]  \left ( \frac{1}{(1-x)} \right )^{N+1} \times \left ( \frac{1}{(1+x)} \right )^{N-1}$

ここまで来ると左側の $x^k$ の係数と右側の $x^{M-N+1-k}$ の係数 を組み合わせれば良い。

もっとも、★ の時点で $(1+x+x^2+\dots)^2$ の係数列が明らか (やることもほぼ同じ) なので、考察終了としてしまってもいいかもしれない。

$N=1$ がコーナーケース。

https://atcoder.jp/contests/fps-24/submissions/70854624

これはなんか組み合わせ論的解釈の方が単純に感じたなぁ

FPS 24 題に「ちゃんと」取り組む #3 (fps24-C)

A	B	C	D	E
F	G	H	I	J
K	L	M	N	O
P	Q	R	S	T
U	V	W	X

C - Sequence

$M $ 以下の非負整数からなる長さ $N$ の整数列のうち、総和が $S$ であるものの個数 ${\rm mod}$ $998244353$ を求めよ

$1 \le N,M,S \le 2 \times 10^5$

本番解法: さすがに有名問題。 $M $ を超える要素の個数 $k$ を固定して、包除原理。

https://atcoder.jp/contests/fps-24/submissions/70655443

FPS 解法はこんな感じ。

$[x^S] (1+x+\dots+x^M)^N$

$\displaystyle =[x^S] \frac{(1-x^{M+1})^N}{(1-x)^N}$

これを分母と分子に切り分けて扱うことで求める。

分子の $x^k$ につく係数は $k$ が $M+1$ の倍数でないとき $0$ 、 $k$ が $M+1$ の倍数であるとき $l=k/(M+1)$ として $(-1)^l \times C(N,l)$ 。

(分母の影響を受けた結果) $x^S$ につく係数への寄与を求めたいが、これは $(1+x+x^2+\dots)^N$ の $x^{S-k}$ につく係数を考えればよく、 $C(S-k+N-1,S-k)$ 倍として表現される。

組み合わせ論的には $S-k$ 個の区別できない球を $N$ 箱に分ければ ok 。

https://atcoder.jp/contests/fps-24/submissions/70852859

包除通らず導出できるのはすごい楽かもしれない。

初めて公式解説見ずに FPS 解法導出できた。洗脳始まってきてるなぁ

FPS 24 題に「ちゃんと」取り組む #2 (fps24-B)

A	B	C	D	E
F	G	H	I	J
K	L	M	N	O
P	Q	R	S	T
U	V	W	X

B - Tuple of Integers

以下の条件を全て満たす非負整数の組 $(a,b,c,d)$ を数え上げよ。 ${\rm mod}$ $998244353$

• $a+b+c+d=N$
• $a \in \{0,1\}$
• $b \in \{0,1,2\}$
• $c$ は偶数
• $d$ は $3$ の倍数

$0 \le N \le 10^9$

本番解法: $f(x)$ を以下の条件を満たす非負整数の組 $(c,d)$ の個数とする。

• $c+d=x$
• $c$ は偶数
• $d$ は $3$ の倍数

実験エスパーすると次のコードで求まるらしい。

あとは $a,b$ を全通り探索すれば ok 

https://atcoder.jp/contests/fps-24/submissions/70656739

これもまぁオーバーキル気味らしい。実験エスパーも入ってますからね…

欲しいものは次の通り。

$[x^N] (x+1)(x^2+x+1)(1+x^2+x^4+\dots)(1+x^3+x^6+\dots)$

無限和が入っているのでなんとかしようとする。無限等比数列の公式をそのまま使ってよい。

$(1+x^2+x^4+\dots) = \frac{1}{(1-x^2)}=\frac{1}{(1-x)(1+x)}$

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

因数分解して筋良になるかもというのは A問題 でも扱いましたね。

積を計算すると

$[x^N] \frac{(x+1)(x^2+x+1)}{(1-x)(1+x)(1-x)(1+x+x^2)}$

$=[x^N] \frac{1}{(1-x)^2}$

公式解説 ではここから公式を利用していますが、この記事ではもうちょっと詰めてみましょう。

$[x^N] \frac{1}{(1-x)} \times \frac{1}{(1-x)}$

無限和の形に戻して

$[x^N] (1+x+x^2+\dots) \times (1+x+x^2+\dots)$

$x^N$ の項の係数は左から $x^k$ 、右から $x^{N-k}$ を選んだ $(0 \le k \le N)$ パターンの和と一致するので、欲しい値が $N+1$ であることが分かる。 

まぁここから公式解説での公式も直ちに得られますね。

https://atcoder.jp/contests/fps-24/submissions/70717927

B まさかのギャグで仰天。でも FPS 知らないとギャグがギャグであるとも見抜けない可能性があるんだなぁ...

本番解法の $f$ のくだりも FPS で楽に出たりするのかなぁ

自分が証明しろと言われると、 $2x+3y=N$ の非負整数解の個数みたいな話になるので $x$ の範囲を求めて $(+3,-2)$ でずらせてどうたらみたいな感じで証明しそう。

最後のところは 1/(1-x^2)(1-x^3) = (1+x^2+x^3+x^4+x^5+x^7)/(1-x^6)^2 からわかると思います

— SSRS (@SSRS_cp) 2025年11月6日

$\frac{1}{(1-x^2)} = \frac{(1+x^2+x^4)}{(1-x^6)}$

$\frac{1}{(1-x^3)} = \frac{(1+x^3)}{(1-x^6)}$

と分母を揃えて分子は分子同士の積で得る、なるほど。慣れればむっちゃ楽そう。

FPS 24 題に「ちゃんと」取り組む #1 (fps24-A)

先日 AtCoder 上で開催された話題の有志コン、 FPS 24 題。

FPS(形式的冪級数) に関する問題を 24 問集めた知の高速道路です。

私も本番参加させて頂き、13完41点という感じでした。

しかしながら、本番では DP、実験エスパー、OEIS、オーバーキルなど種々のズルをしている問題もたくさんあるので、それらと想定解に乖離がある場合や本番で手が届かなかった問題も含めて FPS 24 題で伝えたいことを「ちゃんと」勉強するという本連載を立ち上げました。

1 問 1 記事にする予定のため本連載は 24 回になりそうなもんですが、多分途中何度も逃亡すると思います(ごめんなさい)。また、軽い問題は何問かまとめる可能性もあります。

私は FPS に対して大変疎い(正直、FPS自体かなり競プロじゃないと思ってます)ため、そのような読者にとっては親しみやすい記事になると思います。逆に、 時に厳密さを捨てたり感覚的な理解を伝えたりするので、 FPS に関して深い理解のある方にとっては稚拙な記事になるかもしれません。その場合は優しくご教授頂いたり、誤りを指摘して頂いたり、お帰り頂くなりして頂けると幸いです。

では、始めましょう。

A - Snack

各要素が $1,3,4,6$ である長さ $D$ の数列であって、全要素の和が $N$ であるものはいくつあるか? ${\rm mod}$ $998244353$

$1 \le D \le 2 \times 10^5$

$1 \le N \le 10^6$

本番解法: $(x^1+x^3+x^4+x^6)^D$ を繰り返し二乗法+畳み込みで愚直に計算。時間計算量 $O(N \log^2 N)$ 。

https://atcoder.jp/contests/fps-24/submissions/70656561

なんでこれが $2$ 点の A 問題なんだと一生首を捻っていたが、どうやらオーバーキルらしい。

想定解ベースで再考察すると次の通り。

$(x^1+x^3+x^4+x^6)$ にいい性質がないか探りにかかる。

すると、先ほどの式が因数分解でき、 $x(x^2+1)(x^3+1)$ となる。

欲しいものは $[x^N] (x(x^2+1)(x^3+1))^D$ である。( $[x^k] (x$ の式$)$ で $x$ の $k$ 乗に付く係数を指す)

$[x^N] (x(x^2+1)(x^3+1))^D$

$=[x^{N-D}] (x^2+1)^D(x^3+1)^D$

ここで、何が嬉しいかというと、元々「 $4$ つの和を $D$ 乗する」という扱いにくいものから「 $2$ つの和を $D$ 乗したもの $2$ つの積」というまぁまぁ希望的な形になったことである。

あとは、二項定理を使って $x^2$ が何回かかるかを固定し足し上げればよい。

組み合わせ的解釈を入れると、以下のような感じになる。

以下の行動の部分集合を $D$ ラウンド繰り返す。

• $2$ 円稼ぐ。
• $3$ 円稼ぐ。

$N-D$ 円稼ぐような $D$ ラウンドの過ごし方は何通りか？

こう言われると、　$2$ 円稼ぐのと $3$ 円稼ぐのが独立に扱えているのが嬉しいし、 $2$ 円稼ぐ回数を固定すれば筋良そうに思えるし、現実にそう。この解釈に至るまでに先ほどの式変形を経由している。

https://atcoder.jp/contests/fps-24/submissions/70716720

因数分解を経由して解けるみたいな問題はちょいちょい聞くので、 A からいきなり高度で仰天。先が思いやられる。