はじめに
今回は、2026年8月15日に開催されたAtCoder Beginner Contest 471の問題を、Shrike-Liteで実装できそうかという視点から眺めてみます。
今回も実装は行いません。また、各問題の効率的な解法を詳しく説明する記事でもありません。
まずは、
- C++やPythonなら、どのような処理になりそうか
- それをFPGAへ持ち込むと、何が問題になるか
- Shrike-Liteのリソースで扱えそうか
- Shrike-Liteには入らなくても、FPGAとして面白い回路になりそうか
というところを考えてみます。
なお、すぐに解法が思いつかなかった問題については、AtCoderの公式解説を読んでアルゴリズムを理解したうえで、FPGAへ持ち込むとどうなるかを考えています。
この連載は、競技プログラミングの解法をすべて自力で発見することを目的にはしていません。公式解説の解法を出発点にすることもありますし、そこから「FPGAなら別の解き方もありそうだ」と思いついたら、そちらを試すこともあります。
今回は、Shrike-Liteには到底入りそうにないけれど、FPGAとして考えると面白そうな問題も見つけました。
ではひとつずつ見ていきましょう。
A - Nine or Nein
2つの整数に対して簡単な演算を行い、9になるものがあるかを判定する問題です。
FPGAで考える
必要な演算を並列に実行して、それぞれの結果を比較すればよさそうです。
回路としてはかなり小さく、Shrike-Liteでも問題なく実装できそうです。
題材としては軽めですが、小手調べとしてShrike-Liteに実機実装してみることにします。
B - Survey Tabulation
英字からなる文字列を、大文字と小文字を区別せずに集計し、最も多く現れたものの出現回数を求める問題です。
FPGAで考える
大文字・小文字の正規化そのものは簡単です。
ASCIIコードなら、各文字を比較用の同じ表現へ変換する回路は小さく作れます。
問題は、その後です。
正規化した文字列を保存し、同じ文字列が何回現れたかを管理する必要があります。
比較器を大量に並べて連想メモリのような構成にすることも考えられますが、Shrike-Liteでそこまでやる意味はあまりなさそうです。
RAMへ保存して逐次検索することもできますが、それではFPGAらしい面白さもあまり感じません。
見送りでよさそうです。
C - Cookies and Greedy Takahashi
数直線上にある対象を、現在位置から近いものから順番に処理していく問題です。
効率的に処理するには、まず座標をソートして、負側と正側を原点に近い順に扱えるようにしておくのが素直そうです。
FPGAで考える
ソートが終わった後だけを見ると、かなり単純です。
左側の次候補
↓
距離比較 → 近い方を選択 → pop
↑
右側の次候補
正側・負側の次候補を比較しながら順番に処理できます。
この部分だけなら、小さなFSMにできそうです。
しかし、その前に大量の入力をソートしなければなりません。
ソートはShrike-Liteが得意とする処理ではありませんし、そもそも大量のデータを保持するメモリも必要になるため、実装は見送ります。
仮想的に巨大なFPGAを考えたとしても、普通にソート回路を作るだけでは今回の題材としてあまり面白くなさそうです。
D - Chargers
時系列でデータが追加され、その時点で優先すべき要素を取り出していく問題です。
値を少し変形して持つことで、取り出すべき要素をpriority queueで管理できます。
ソフトウェアならbinary heapを使うのが定番です。
FPGAで考える
しかし、欲しいのはpriority queueとしての振る舞いであって、内部構造がbinary heapである必要はありません。
例えば、値を保持する比較・交換セルを1次元に並べ、新しい値を流しながら優先順位に応じた位置へ移動させる構成も考えられます。
最大ケースをShrike-Lite内部へ保持するのは現実的ではありませんが、仮想的に十分な回路資源を持つFPGA上で、FPGAなりのpriority queueを作ってみるのは面白そうです。
E - Sum of Square of Sum
N個の値からK個を選び、その和を2乗した値について、すべての選び方の総和を求める問題です。
答えは998244353を法として求めます。
最初に問題を見たときは、Shrike-Liteで扱うにはかなり重そうに見えました。
しかし公式解説を読み、そこで説明されている式をよく見ると、様子が変わります。
全入力を保存しなくてもよさそう
公式解説では、K個をランダムに選んだときの期待値へ置き換えることで、
S1 = Σ Ai
S2 = Σ Ai^2
を使って計算できる形に整理しています。
Σ(i≠j) AiAj = S1^2 - S2なので、元の入力列を保存する必要はありません。入力列から集計して保持する値は、大きくこの2つだけです。
Ai
├─→ 加算 ─→ S1
└─→ 2乗 ─→ 加算 ─→ S2
元問題の答えは、この期待値を組合せ数C(N,K)倍すれば求められます。
Nが大きくても、入力はストリーム処理できそうです。
Shrike-Liteで試してみたい
問題になるのは998244353を法とする乗算や組合せ数の計算です。
32bit級の剰余演算はShrike-Liteには決して軽くありません。
それでも、
大量の入力を保存せず、少数の状態だけを更新し続ける
という構造はShrike-Lite向きです。
入るかどうか、間に合うかどうかも含めて、実機で試してみたい問題です。
失敗したら失敗したで、それも結果でしょう。
1120 LUT / 32kB BRAMの狭小FPGAでE問題は解けるのか
なかなかのチャレンジですね。
F - Concat (maximize)
多数の数値文字列から条件に従って要素を選び、さらに並べ替えて最大の数値を作る問題です。
FPGAで考える
またソートです。
しかも今回は1回ではありません。
前半では選ぶ要素を決めるための順序付けが必要になり、後半では文字列A,Bについて、
A + B
B + A
を比較するような特殊な順序で、もう一度並べ替える必要があります。
比較回路そのものは作れそうですが、大量の文字列を保持しながら並べ替える部分がShrike-Liteには重すぎます。
C問題に続いて、
「比較はできる。でもソート全体をやりたくない」
という問題です。
見送りでよさそうです。
G - Caeser Syllables
今回、一番問題文を読み解くのに時間がかかった問題です。
問題文を何とか読み終えた段階では、正直なところ見送り候補でした。
ところが公式の解説ページを見ていると、ユーザー解説としてHBitさんによるSIMD解法が掲載されていました。
512bitのSIMDやCarry Save Adderまで使った、計算機アーキテクチャ好きとしてはかなり興奮するような解法です。
それを見て、
「並列処理が本業のFPGAなら、k方向を全部回路にして、入力方向もさらに並列化できるのでは？」
と思いつきました。
大まかには、各kについて
b_i(k) = V[(A_i + k) mod K]
という0/1列を考え、連続する1の区間数を数える問題と見ることができます。
Kは最大2300です。
FPGAで考える
ある入力A[i]に対するb_i(k)を、全kについて並べたものを、
current[0:K-1]
というbit列として考えます。
ひとつ前のbit列をprevとして保持しておけば、0 → 1となる区間の開始位置は、
current & ~prev
でまとめて求められます。prevを0で初期化すれば、先頭が1の場合も同じ式で数えられます。
ここで、普通ならkをループします。
しかしFPGAなら、
2300個全部並べてしまえばいい
とも考えられます。
k=0 counter
↑
A[i] → 2300bit判定 → k=1 counter
↓
...
↓
k=2299 counter
k方向を完全に空間展開すれば、入力1個あたりの処理を1クロックへ近づけられそうです。
でもShrike-Liteには入らない
もちろん2300本のカウンタや判定回路をShrike-Liteへ入れることはできません。
しかし、この回路はかなり面白そうです。
そこで今回は、「実在するFPGAへ入るかどうか」をいったん忘れることにしました。
スピンアウト：「仮想理想FPGAでAtCoderを解く」
Shrike-LiteでAtCoder問題を解いていると、FPGAで処理したら面白そうなのに、回路資源の都合で見送る問題が結構あります。
そこで、
必要なだけ回路資源を持つ仮想的なFPGAを考えて、Verilog上で専用計算機を作ってしまおう
という別の遊びを始めることにしました。
新しいスピンアウト連載の題名は、
「仮想理想FPGAでAtCoderを解く」
にするつもりです。
実在FPGAへの実装可能性よりも、
FPGAで実装したらカッコいいか
を問題選択の基準にします。
G問題は、この新連載の第1回候補です。
さらに入力方向も並列化してみます。
回路巨大化の上限は、実在FPGAのLUT数ではなく、Icarus Verilogを動かすPCのメモリと実行時間が止めてくれるでしょう。
Shrike-Liteとは正反対の遊びになりそうです。
今回のまとめ & 独り言
今回はABC471のAからGまでを、FPGA目線で眺めました。
| 問題 | FPGAへ持ち込んだ印象 | 今後 |
|---|---|---|
| A | 小さな並列判定回路で済む | Shrike-Liteで実装 |
| B | 文字列の正規化は簡単だが集計が面白くない | 見送り |
| C | ソート後は簡単だがソートが重い | 見送り |
| D | FPGAなりのpriority queueを作れば面白いかも | 仮想理想FPGA候補 |
| E | 少数の状態だけでストリーム処理できる | Shrike-Liteで挑戦 |
| F | またソート | 見送り |
| G |
k方向を大量並列化できて、さらに深追い可能かも |
仮想理想FPGAで挑戦 |
今週はAとEをShrike-Lite実機で試します。
また、Gを第1回、Dをその次の候補として、新しいスピンアウト連載「仮想理想FPGAでAtCoderを解く」でも遊んでみることにします。
同じAtCoderでも、かなり違う景色が見えそうです。
前回：
Shrike-LiteでAtCoder問題を解く(34)：Detour：ABC470D(後編) - 50万クエリ、結局ひとつの変換じゃない？