はじめに
今回は、2026年8月8日に開催されたAtCoder Beginner Contest 470の問題を、Shrike-Liteで実装できそうかという視点から眺めてみます。
今回は実装しません。また、各問題の効率的な解法を詳しく説明する記事でもありません。
まずは、
- C++やPythonなら、どのような実装を考えるか
- それをFPGAへ持ち込むと、何が問題になるか
- Shrike-Liteのリソースで扱えそうか
というところを考えてみます。
今回は、演算回路そのものよりも「どれだけの状態をFPGA内部へ保持しなければならないか」が重要になりそうです。
A - Fizz
1からNまで順番に、
- 3の倍数なら
Fizz - それ以外なら数値そのもの
を出力する問題です。
制約はN ≤ 100です。
愚直に考える
C++ / Pythonなら、1からNまでループして、
i % 3 == 0
を判定すれば終わりです。
FPGAで考える
3の倍数判定のために、わざわざ除算回路を用意する必要はありません。
0 → 1 → 2 → 0 → ...
と循環する2bit程度の状態を持っておけば、現在の値が3の倍数かどうかを判定できます。
演算回路だけを見るなら、非常に小さく実装できそうです。
一方、この問題では答えを1個返すのではなく、最大100行を順番に出力する必要があります。
FPGA側で「Fizzか数値か」を判定するのは簡単ですが、その後の文字列出力まで含めると、計算そのものより入出力処理のほうが目立ってしまいそうです。
- FPGA処理向け度：高
- データサイズ許容度：高
- Shrike-Lite実装難易度：低
- 題材としての面白さ：低め
実装は簡単そうですが、Shrike-Liteを使う意味はあまり大きくなさそうです。
B - Monocolor
N個のボールがあり、それぞれ色1からNのいずれかで塗られています。
1回の操作で1個のボールを好きな色へ変更できます。
すべてのボールを同じ色にするために必要な最小操作回数を求める問題です。
制約はN ≤ 100です。
愚直に考える
最も多く使われている色を残し、それ以外のボールをその色へ変更すればよさそうです。
そこで、色ごとの個数を数えます。
count[color]++
最後に最大値を求め、
N - max_count
とすれば答えになります。
FPGAで考える
この方法はFPGAにも比較的素直に持ち込めそうです。
色は最大100種類なので、色ごとに7bit程度のカウンタを用意すれば十分です。
必要な容量は単純計算で、
100 × 7bit = 700bit
程度です。
Shrike-LiteならDistributed RAMを利用するのがよさそうですね。
入力された色に対応するカウンタを1増やし、その値が現在の最大値を超えたらmax_countも更新します。
色を受信
↓
count[color]を読む
↓
+1
↓
書き戻す
↓
max_countと比較
という小さなFSMで処理できそうです。
入力を保存せずにストリーム処理できるため、Shrike-Liteにはかなり扱いやすそうです。
- FPGA処理向け度：高
- データサイズ許容度：高
- 実装可能性：高
- Shrike-Lite実装難易度：低〜中
今回の問題の中では、最も素直な実装候補に見えます。
C - Inc, Dec, Xor
長さNの整数列Aに対して、
1 x : A[x]を1増やす
2 : 0より大きいすべてのA[i]を1減らす
というクエリを処理し、毎回すべての要素のXORを求める問題です。
N, Q ≤ 5×10^5です。
FPGAで考える
種類2のクエリで全要素を毎回走査する方法では間に合いませんが、XORそのものは差分更新できます。
変更前をold、変更後をnewとすれば、
xor_value ^= old
xor_value ^= new
とすればよく、さらに現在0より大きい要素だけを覚えておけば、処理対象も減らせそうです。
演算内容だけなら、比較的小さなFSMへ落とせそうです。
FPGAで困ること
問題は、最大50万要素の状態をどこへ置くかです。
A[i]と非ゼロ要素の添字を19bitで保持すると、単純計算で、
A[] 約1.2MB
非ゼロ添字列 約1.2MB
-----------------------
合計 約2.4MB
程度の作業メモリが必要になります。
メモリ圧縮をする方法もありそうですが、少なくとも各A[i]の個別情報を持つ必要があるはずです。
1要素あたり1bitまで情報量を圧縮できたと仮定しても500kbit = 62.5kBのメモリ空間が要求されます。
どちらにしても、Shrike-LiteのFPGAでは、この量のデータを保持できません。
- FPGA処理向け度：演算だけなら高
- データサイズ許容度：低
- 実装可能性：最大制約では厳しい
- Shrike-Lite実装難易度：メモリ容量でほぼ見送り
計算量を工夫して減らしても、最後は**「50万要素の状態をどこへ置くのか」**という物理的なメモリ容量の問題が残ります。
演算器ではなく、メモリに負ける問題になりそうです。
D - Inverse and Swap
1からNまでの順列Pが与えられます。
次の2種類のクエリを処理します。
1 x y : P[x]とP[y]を交換する
2 : Pを逆置換へ置き換える
N, Q ≤ 5×10^5です。
愚直に考える
種類1のswapは簡単ですが、種類2で逆置換を作り直すには、
Pinv[P[i]] = i
として全要素を走査する必要があります。
種類2のクエリが来るたびに最大50万要素を処理するのは重そうです。
FPGAで考える
最初からP[]とPinv[]の両方を保持しておけば、種類1では両方の対応する要素を更新し、種類2ではどちらを現在のPとして扱うかを切り替えるだけで済みます。
最大50万要素すべてを変換する操作を、1bit程度の状態変更へ置き換えられるわけです。
これはかなりFPGAらしい考え方です。
ただし、順列の各要素には最大19bit必要です。
500,000 × 19bit × 2
≒ 19Mbit
≒ 2.4MB
PとPinvを両方保持するには約2.4MB必要となり、Shrike-Liteには入りません。
保持する要素を減らして複数回のストリーム走査を行う事もできますが、その場合は2秒の壁が立ちはだかりそうです。
- FPGA処理向け度：考え方としては高
- データサイズ許容度：低
- 実装可能性：最大制約では厳しい
- Shrike-Lite実装難易度：メモリ容量で見送り
**「回路は簡単なのにRAMがない」**という問題です。
外部RAMを持つ、もう少しメモリリッチなFPGAボードなら事情がかなり変わりそうです。
E - Concentration
神経衰弱のようなゲームで、最適に行動した場合の期待スコアを求める問題です。
N, L ≤ 200です。
公式解説では、ゲームの状態をまとめたDPによりO(LN^2)で期待値を計算します。
確率・期待値の計算に加えて、多数のDP状態を保持する必要があります。
固定小数点などを使えばFPGAで計算できないわけではありませんが、Shrike-Liteで取り組む題材としてはかなり重そうです。
見送りでよさそうです。
F - Googol Swaps
長さ最大20万の文字列について、指定された位置同士のswapをちょうど10^100回行った後に作れる文字列の種類数を求めます。
答えは998244353を法として求めます。
公式解説ではグラフの連結成分を管理し、各成分内の文字の並べ替えを数え上げます。そのためにDSUや階乗・逆元を使った剰余演算が必要になります。
最大20万要素の状態管理と32bit級のモジュラー演算が見えた時点で、Shrike-Liteではかなり厳しそうです。
見送り決定です。
G - ΣШX
長さ最大30万の非負整数列について、すべての部分区間のmexを合計する問題です。
部分区間の数だけでも非常に多く、もちろん愚直な全列挙では処理できません。
効率的に解くには、各値の出現位置などを大規模に管理しながら区間を処理する必要がありそうです。
Shrike-Liteでは入力データを保持するだけでも厳しく、今回ここから深追いするメリットは小さそうです。
見送り決定です。
今回のまとめ & 独り言
今回はABC470のAからGまでを、Shrike-Liteで実装できそうかという視点から眺めました。
| 問題 | FPGAへ持ち込んだ印象 | 今後 |
|---|---|---|
| A | 回路は非常に簡単 | 実装可能だが題材としては軽い |
| B | 小さなヒストグラムで処理できる | 有力な実装候補 |
| C | 演算は小さくできるが巨大な状態表が必要 | メモリ容量で見送り寄り |
| D | Pと逆置換の役割切替は小さな状態で済む | メモリ容量で見送り寄り |
| E | 期待値DPと実数計算が重い | 見送り |
| F | 大規模DSUと剰余演算が必要 | 見送り |
| G | 大規模データ構造が必要 | 見送り |
今回、面白かったのはCとDです。
どちらも、最初に見える巨大な処理そのものは、考え方を変えることでかなり小さな回路へ置き換えられそうです。
しかし最大50万要素を扱うためには、大量の状態をどこかに保持する必要があります。
そうなると、Shrike-Liteでは、RAMに入らない、という別の壁が現れます。
FPGAでAtCoder問題を考えていると、ソフトウェアでは単に「配列」と書いていたものが、実際にはどれだけの物理メモリを必要とするのかを強く意識させられます。
前回：
Shrike-LiteでAtCoder問題を解く(29)：ABC469A／B - 4bitパラレル通信を使ってみる