Shrike-LiteでAtCoder問題を解く(19)：Interlude - ABC468の各問題をFPGA目線で見てみる
はじめに
前回まで、ABC467Cを題材として、SPI転送の高速化、4組パック、Prefix XOR、タイミング違反への対応を進めてきました。
ABC467Cだけで複数回の記事を使い、かなりお腹いっぱいの内容になりました。
今回は少し立ち止まり、2026年7月25日に開催されたAtCoder Beginner Contest 468の問題を、Shrike-Liteで実装できそうかという視点から眺めてみます。ABC468にはAからGまでの7問が用意されています。
今回は実装しません。また、各問題の効率的な解法を詳しく説明する記事でもありません。
まずは、
- C++やPythonなら、どのような実装を考えるか
- それをそのままFPGAへ持ち込むと、何が問題になるか
というところまで考えてみます。
「その実装では困るなら、どう考え直せばよいのか」は、次回以降のお楽しみです。
A - Maximal Value
長さNの整数列について、
A_i < A_{i+1} > A_{i+2}
となる位置の個数を求める問題です。
制約はN ≤ 100、A_i ≤ 100です。
愚直に考える
C++ / Pythonなら、数列を前から順に走査し、連続する3要素を比較すれば終わりです。
A[i] < A[i + 1] && A[i + 1] > A[i + 2]
を満たすたびに、カウンタを1増やします。
FPGAで考える
この問題は、愚直実装の考え方をほぼそのまま回路へ移せそうです。
A_iは最大100なので、各要素は7bitで表せます。
7bitのFFを3個並べ、値を受信するたびに1段ずつシフトすれば、常に直近の3要素を保持できます。
3要素がそろった後は、2個の比較器で条件を判定し、成立したときだけカウンタを加算します。
入力された数列全体を保存する必要もありません。
今回の問題の中では、最も素直にストリーム処理へ置き換えられそうです。
- FPGA処理向け度：高
- データサイズ許容度：高
肩慣らしの題材として、かなり良さそうです。
B - Corridor Watch
横一列に並んだM個のマスにガードマンが配置されています。
ガードマンから距離D以内のマスは監視されます。監視されていないマスの個数を求める問題です。
制約はM ≤ 100です。
愚直に考える
C++ / Pyhtonなら、最大100要素の配列を用意して、最初はすべてのマスを「監視されていない」としておけばよさそうです。
ガードマンを見つけるたびに、その前後Dマスを「監視済み」へ書き換えます。
最後に、監視されていないマスを数えれば答えになります。
制約が小さいため、C++ / Pythonではほとんど何も考えなくても実装できます。
FPGAで困ること
同じことをFPGAで行おうとすると、少し様子が変わります。
100個の1bit FFを用意すること自体は、不可能ではありません。
しかし、ガードマンを1人受信するたびに、位置に応じて最大100個のFFを書き換えようとすると、大量の条件分岐とMUXが必要になります。
BRAMへ保存して1マスずつ書き換える方法も考えられますが、今度は同じ100要素を何度も順番に読み書きするFSMが必要になります。
C++ / Pythonでは単純な二重ループで済む処理が、物理回路ではあまり素直ではありません。
では、100マスそれぞれの監視状態を、本当に保持する必要があるのでしょうか。
この問題は、そこから考え直す必要がありそうです。
- FPGA処理向け度：愚直実装のままでは低
- データサイズ許容度：高
- FPGA実装向けアルゴリズム：ありそう
C - Between P and Q
1からNまでの順列PとQが与えられます。
辞書順でPより大きく、Qより小さい順列の個数を求める問題です。
制約はN ≤ 10です。
愚直に考える
N=10のとき、順列の総数は、
10! = 3,628,800
です。
C++ / Pythonなら全順列を生成し、それぞれをP、Qと比較して条件を満たすものを数える実装でも間に合いそうです。
AtCoderのC問題らしい、制約を利用した全探索です。
FPGAで困ること
FPGAで同じことをする場合、約363万個という回数そのものは、必ずしも致命的ではありません。
50MHzで2秒なら、1億クロックあります。
問題は、次の順列を生成する回路です。
- 現在の順列を保持する
- 次の辞書順の順列を作る
-
Pと比較する -
Qと比較する - 条件を満たせばカウントする
という一連の処理を、回路とFSMで組む必要があります。
C++ / Pythonではライブラリへ任せられる順列生成も、FPGAでは自分で状態遷移として作らなければなりません。
入力は最大でも20要素しかなく、データ量には余裕があります。
それなのに、全順列を生成するための制御回路が相当大きくなりそうです。
では、363万個の順列を実際に生成せず、PとQから条件を満たす順列の個数を直接調べる方法はないのでしょうか。
考えてみましょう。
- FPGA処理向け度：愚直実装のままでは低
- データサイズ許容度：最適
- FPGA実装向けアルゴリズム：ありそう
- Shrike実装難易度：少し高そう、ひょっとするとLUTリソース制約に負ける?
少しアルゴリズム寄りの話になりそうです。
D - Pre-Palindrome
英小文字からなる文字列Sについて、1文字以下を書き換えることで回文にできる部分文字列の個数を求める問題です。
文字列の長さは最大10^4です。
愚直に考える
奇数長と偶数長の中心を順番に選び、左右へ1文字ずつ広げながら比較する方法が考えられます。
左右の文字が異なる回数を数え、不一致が2回になった時点で、その中心についての探索を終了します。
演算内容だけを見ると、
- 左右の文字を読む
- 5bit程度の値を比較する
- 不一致回数を数える
- アドレスを移動する
という単純な処理です。
同じ比較回路を何度も使えるため、FPGAにも向いているように見えます。
FPGAで困ること
問題は、最大1万文字の置き場所です。
英小文字を5bitへ変換しても、文字列全体を保存するには約50kbit必要です。
Shrike-Liteに載っているFPGA SLG47910には、1120 LUT、32kbit BRAM、5kbit Distributed Memoryが搭載されています。
文字列全体を単純に保存するには、内蔵メモリが足りません。
FSMを使って、文字を容量いっぱいまでBRAMへ保存し、覚えきれない部分だけRP2040からの繰り返しストリームで直接処理する方法も考えられます。
さらに、2回目の不一致を見つけた時点で、FPGAからRP2040へ「ここで転送を止めてよい」と通知できれば、不要な通信を減らせそうです。
そのあたりの処理をうまく設計できれば、全く不可能というわけではなさそうです。
しかし、その場合は回文判定よりも、
- BRAMのバンク構成
- 5bitデータの格納方法
- 同じ文字列の範囲再転送
- MISOを使った停止要求
- 転送データパッケージ単位のフロー制御
のほうが大きなテーマになります。
実装を始めると、BRAM設定とMISO要求だけで数回の記事になりそうです。
- FPGA処理向け度：中
- データサイズ許容度：低
- 実装可能性：不可能ではない
- Shrike実装難易度：かなり高、見送り寄り
面白そうですが、今週手を出す問題ではなさそうです。
全文を保持できるメモリリッチなFPGAボードをお持ちの方は、ぜひトライされるといいと思います。
E - Sum of Average
全区間の平均を合計し、998244353を法として答える問題です。Nは最大5×10^5です。
32bit級の剰余乗算、逆元、最大50万要素の処理が必要になりそうです。
分数の32bitモジュラーな時点でShrike-Liteでは見送り必至です。
F - Chmax
最大50万要素の順列を処理する問題です。
入力転送量と作業メモリの時点で、Shrike-Liteには厳しそうです。
現状の4MHz SPIでは、19bit x 50万要素のRP2040 → FPGA転送だけで2秒以上かかります。
さらに50万データの保持はBRAMが32kbitしかないのでできません。見送り決定です。
G - Restricted Permutation
最大N=2000の順列を数え、答えをMod 998244353で求める問題です。
大規模な数え上げと32bitモジュラー演算が見えます。
見送り決定です。
今回のまとめ & 独り言
今回はABC468のAからGまでを、Shrike-Liteで実装できそうかという視点から眺めました。
| 問題 | 愚直実装をFPGAへ移した印象 | 今後 |
|---|---|---|
| A | そのままストリーム処理にできそう | 素直に実装する |
| B | 多数のFF書き換えが重い | ほかの解法を試せばいけそう |
| C | 全順列生成器が大げさ | ほかの解法を試せばいけるかも |
| D | 比較回路は簡単だがデータ保持が難しい | 不可能ではないが、見送り方向 |
| E | 32bitモジュラー演算が重い | 見送り |
| F | データ量と作業メモリが大きい | 見送り |
| G | 数え上げと剰余演算が重い | 見送り |
C++ / Pythonでは簡単なループや配列更新でも、FPGAへ持ち込むと、
- 一度に何個の状態を書き換えるのか
- どれだけのデータを保持するのか
- 同じ回路を何回使い回せるのか
- 乗算、除算、剰余演算が必要か
- 入力データの転送だけで時間を使い切らないか
といった点が問題になります。
特にShrike-LiteのForgeFPGAはリソース制約がとても厳しいので、B問題ですら愚直実装を許してもらえない縛りプレイになりがちです。
もちろんコンテストによってばらつきますが、回答難易度は平均的にはだいたい以下ぐらいかなと感じています。
Shrike-LiteでB問題 ≒ C++ / PythonのD問題
Shrike-LiteでC問題 ≒ C++ / PythonのE問題
B問題なら「何かひとつ工夫すればできる」ぐらい、C問題になると「何かひとつ工夫しても、次にリソース制約やタイミング制約が立ちはだかる」というのが実感です。
逆に、問題の見方を少し変えるだけで、保持する状態や必要な回路を大幅に減らせる場合もあります。
次回以降は、今回検討した問題の中から、実際にShrike-Liteへ実装する問題を選びます。
まずは、最も素直にストリーム処理へ置き換えられそうなA問題から始める予定です。
お楽しみに。
前回：
Shrike-LiteでAtCoder問題を解く(18)：ABC467C - Adjacent Sums (easy)（タイミング違反解消編・後編）