はじめに
前回まで、ABC468のAからCまでを題材として、ストリーム処理、Distributed RAM、PLL、桁DPなどを試してきました。
今回は少し立ち止まり、2026年8月1日に開催されたAtCoder Beginner Contest 469の問題を、Shrike-Liteで実装できそうかという視点から眺めてみます。ABC469にはAからGまでの7問が用意されています。
今回は実装しません。また、各問題の効率的な解法を詳しく説明する記事でもありません。
まずは、
- PC上のプログラムなら、どのような実装を考えるか
- それをそのままShrike-Liteへ持ち込むと、何が問題になるか
というところまで考えてみます。
A - Train Car
N両編成の電車で、前からK両目の車両が後ろから何両目かを求める問題です。
制約は1 ≤ K ≤ N ≤ 100です。
愚直に考える
C++ / Pythonなら、答えは、
N - K + 1
です。
入力を受け取ったら、減算と加算を1回ずつ行えば終わります。
FPGAで考える
この問題は、そのまま小さな組み合わせ回路へ置き換えられます。
NとKは最大100なので、どちらも7bitで表せます。
7bitの減算器でN-Kを求め、最後に1を加算すれば答えになります。
入力データも2個だけで、保存する配列や繰り返し処理もありません。
FPGAを使う必要があるかという点は考えないことにしましょう。
- FPGA処理向け度：高
- データサイズ許容度：最適
- Shrike実装難易度：低
良い肩慣らしになりそうですね。
B - Isolated Seats
oとxからなる文字列Sが与えられます。
oは人が座っている椅子、xは空いている椅子を表します。
自分自身と左右の椅子がすべて空いている椅子の個数を求める問題です。端の外側には椅子がないため、空いているものとして扱えます。
制約はN ≤ 100です。
愚直に考える
C++ / Pythonなら、文字列の先頭と末尾へ番兵としてxを追加し、連続する3文字が、
xxx
となる位置を数えればよさそうです。
FPGAで考える
この問題も、そのままストリーム処理へ置き換えられます。
直近の3文字を保持する3bitのシフトレジスタを用意し、1文字受信するたびに1bitずつシフトします。
3bitすべてがxなら、中央の椅子が条件を満たすため、カウンタを1増やします。
先頭と末尾の番兵も、FSMで仮想的にxを1文字ずつ追加すれば対応できます。
入力文字列全体を保存する必要はありません。
- FPGA処理向け度：高
- データサイズ許容度：高
- Shrike実装難易度：低
A問題と同様、素直に実装できそうです。
C - Cantrip
oとxからなる長さNの文字列Sが与えられます。
先頭からk個の袋を受け取った後、持っているoの袋を1個捨て、列の先頭から新しい袋を受け取る操作を、可能な限り繰り返します。
k=1,2,...,Nのそれぞれについて、受け取れる袋の総数を求める問題です。
制約はN ≤ 8×10^5です。答えもN個出力します。
C++ / Pythonで考える
文字列中にxがk個以上あるなら、操作が止まるのはk個目のxを受け取った時点です。
xがk個未満なら、最後まで袋を受け取れます。
したがって、文字列を左から走査し、xの位置を順番に列挙すれば答えを求められます。
FPGAで考える
計算回路だけを見ると、とても簡単です。
20bitの位置カウンタを増やしながら文字列を受信し、xを見つけたら現在位置を回答として出力します。
入力を最後まで読み終えた後は、まだ出力していない回答についてNを繰り返し出力します。
文字列や回答列を保存する必要はありません。
完全なストリーム処理です。
問題は回答の転送量
最大ケースでは、20bitで表せる回答を80万個返す必要があります。
1回答を3byteで返すと、回答データをバイナリでRP2040に返すだけで、
3byte × 800,000 = 2.4MB
になります。
4MHz SPIの転送速度は理論上でも0.5MB/sなので、MISOから回答を返すだけで最低4.8秒かかります。
計算回路がどれだけ速くても、2秒の制限時間には入りません。
計算回路は十分に小さくできそうですが、現行のSPI通信では、回答を返すだけで制限時間を超えてしまいます。
演算は間に合うのに、出力が間に合わない
という問題です。
この問題へ挑戦するには、回路の高速化ではなく、FPGAとRP2040の間で大量のデータをやり取りする方法そのものを考え直す必要がありそうです。
ジャッジをどうするか
80万個の回答をRP2040のメモリへ保存することはできないため、正誤判定も工夫が必要です。
RP2040側で期待値を逐次生成し、FPGAから回答を受信するたびにその場で比較すれば、全回答を保持せずに厳密な照合ができます。
ハッシュや抜き取り検査で済ませるのではなく、80万個すべてを確認できる仕組みを用意したいところです。
- FPGA処理向け度：高
- 入力データサイズ許容度：高
- 出力データサイズ許容度：現行4MHz SPIでは2秒以内の転送不可
- Shrike実装難易度：計算は低、通信と検証はかなり高
今週の主役候補です。
D - The Big Two
N人のプレイヤーについて、M回のトーナメントの決勝進出者A_i, B_iが与えられます。
どのトーナメントでも、xまたはyの少なくとも一方が決勝へ進出しているような2人組(x,y)の個数を求める問題です。
制約はN,M ≤ 2×10^5です。
C++ / Pythonで考える
条件を満たす2人組には、最初のトーナメントの決勝進出者A_1またはB_1の少なくとも一方が必ず含まれます。
そこで、1人目をA_1に固定した場合と、B_1に固定した場合を別々に調べます。
例えばA_1を固定した場合、A_1を含まないトーナメントについては、もう1人がA_iまたはB_iでなければなりません。
候補を各{A_i,B_i}との共通部分へ絞り込めば、最後まで残る候補は最大2人です。
全トーナメントを1回走査すれば答えを求められます。
FPGAで考える
この処理もストリーム処理に向いています。
必要なのは、
-
A_1とB_1 -
A_1を固定した場合の候補 -
B_1を固定した場合の候補 - 各候補のvalidフラグ
- 固定したプレイヤーを含まない組が現れたかを示すフラグ
程度です。最後に、2系統で重複して数えた組があれば除外します。
各プレイヤー番号は最大20万なので18bitで表せます。
入力された組を保存せず、受信するたびに2系統の候補を更新できます。
BRAMも大きな配列も必要ありません。
こちらは入力転送が重い
演算回路は小さくできますが、最大20万組のプレイヤー番号をFPGAへ渡す必要があります。
プレイヤー番号を18bitで隙間なく詰めても、入力データは、
18bit × 2人 × 200,000組 = 7.2Mbit
です。
4MHz SPIでは、データ本体だけで約1.8秒かかります。
byte単位の転送データパッケージや制御情報を加えると、2秒以内へ収めるのは難しそうです。
C問題がMISO側の大量出力問題なら、D問題はMOSI側の大量入力問題です。
こちらも演算回路ではなく、現行SPIの転送速度が実装可能性を左右します。
- FPGA処理向け度：高
- データサイズ許容度：SPIでは低
- FPGA実装向けアルゴリズム：ストリーム処理向き
- Shrike実装難易度：中
通信帯域の問題を解決できれば、C問題の次に実装候補として残しておきたい問題です。
E - Pro Exam Eligibility
oとxからなる長さNの文字列について、oをK個以上含む区間の中から、勝率が最大になる区間を求める問題です。
制約はN ≤ 10^6です。
原問題では、答えとなる勝率を二分探索し、文字列を繰り返し走査して条件を満たす区間が存在するかを判定します。
最大100万文字の再走査や途中結果の保持が必要になるため、そのままShrike-Liteへ持ち込むのは難しそうです。
一方、入力数を内蔵メモリへ収まる範囲まで減らし、あえて全区間を調べる方法なら実装できるかもしれません。
2秒以内に処理できる最大Nを実機で探す題材にすると面白そうですが、今回は見送ります。
- FPGA処理向け度：原問題のままでは低
- データサイズ許容度：低
- 入力数を減らした場合の実装可能性：ありそう
F - GCD Maximum Spanning Tree
数列Aの各要素を頂点とし、2頂点間の辺の重みを2要素のGCDとした完全グラフについて、最大全域木の辺の重みの合計を求める問題です。
制約はN ≤ 2×10^5、A_i ≤ 10^6です。
効率的に解くには、最大100万までの値を参照する表と、最大20万頂点の連結状態を管理する作業領域が必要になります。
演算器よりも、大容量メモリとランダムアクセスが主役になる問題です。
Shrike-Liteの内蔵メモリには収まりません。
- FPGA処理向け度：低
- データサイズ許容度：低
- Shrike実装難易度：非常に高
見送り決定です。
G - K-nacci Operations
非常に大きなNについて、再帰的に作られる操作列を文字列Tへ適用した結果を求める問題です。
制約はK ≤ 100、N ≤ 10^18で、初期文字列とTの長さも最大20万規模です。
巨大な操作列をそのまま生成できないため、PC上でも操作を小さな状態へ圧縮し、大きく先の状態まで飛ばす必要があります。
Shrike-Liteでは、そのための多数の状態や途中結果に加え、最大20万文字のTも扱わなければなりません。
小さな演算器を順番に使い回すだけでは済まず、大容量メモリが中心になるため見送りです。
- FPGA処理向け度：低
- データサイズ許容度：低
- Shrike実装難易度：非常に高
今回のまとめ & 独り言
今回はABC469のAからGまでを、Shrike-Liteで実装できそうかという視点から眺めました。
| 問題 | FPGAへ持ち込んだ印象 | 今後 |
|---|---|---|
| A | 小さな減算・加算回路だけで終わる | 素直に実装できる |
| B | 3bitシフトレジスタでストリーム処理できる | 素直に実装できる |
| C | 計算は簡単だが、80万回答の返却が重い | 通信帯域拡大の検討が必須 |
| D | 少数候補の絞り込みでストリーム処理できる | C問題同様に通信帯域が課題 |
| E | 原問題の効率解法はShrikeのメモリ規模に合わない | 見送り方向 |
| F | 大容量の作業領域とランダムアクセスが必要 | 見送り |
| G | 多数の状態と巨大文字列を扱う必要がある | 見送り |
Aは小さな組み合わせ回路、Bは3bitシフトレジスタを使ったストリーム回路へ素直に置き換えられるでしょう。
しかし、Cでは回答転送だけで2秒を超え、Dでも入力転送だけで制限時間の大半を使います。
これまでのように演算回路を工夫するだけでは解決できず、FPGAとRP2040の間の通信方法から考え直す必要があります。
そしてC問題では、80万個の回答を返すだけでなく、それらをRP2040側で全件照合する仕組みまで必要になりそうです。
RP2040側で期待値を計算して照合するなら、その答えをそのまま使えばよいのではないか、という疑問もあります。
それでもFPGAを使います。
次回以降は、C問題へ挑戦するために、現行SPIのボトルネックをどう解消するか検討する予定です。
お楽しみに。
前回：
Shrike-LiteでAtCoder問題を解く(25)：ABC468C - Between P and Q（桁DPで加算器を使い回す）