はじめに
今回は、2026年8月22日に開催されたAtCoder Beginner Contest 472のAからGまでを、Shrike-Liteや仮想理想FPGAを中心に眺めてみます。
これまでのInterlude回では、
- ソフトウェアではどのような処理になりそうか
- それをFPGAへ持ち込むと何が問題になるか
- Shrike-Liteのリソースで扱えそうか
- Shrike-Liteには入らなくても、FPGAとして面白そうか
という視点で各問題を見てきました。
今回は、少しだけ手を広げます。
別記事でABC471Gの実装を検討して気づいたのが、
遊び道具はFPGAだけではない
という、当たり前のことです。
CPU、AVXなどのSIMD命令、GPU。
同じ問題でも、計算の形によって得意な計算機はかなり違います。
そこで今回からは、主役はこれまで通りShrike-Liteと仮想理想FPGAのまま、
「この問題、どの計算機に食わせると面白い？」
という視点も少し加えてみます。
なお、今回も各問題の効率的な解法を詳しく説明する記事ではありません。
すぐに解法が思いつかなかった問題については公式解説などを読み、処理の形だけ理解したうえで、計算機アーキテクチャとの相性を考えます。
では、ひとつずつ見ていきましょう。
A - A
英大文字からなる文字列Sについて、A以外の文字をすべて.へ置き換える問題です。
Shrike-Liteで考える
これはかなりShrike-Lite向きです。
FPGA側では、
入力文字 == 'A'
├─ Yes → 'A'
└─ No → '.'
とすればよく、1文字受信したら1文字返すストリーム処理にできます。
標準入力をSPIへ渡す部分はRP2040側に任せます。
SPIの1byte遅延も、そのままパイプラインとして利用できそうです。
回路はほとんど比較器と選択回路だけです。
小手調べとして実機で試してみたい問題です。
他の計算機では
CPUなら一瞬です。
AVXや仮想理想FPGAなら複数文字をまとめて処理できますが、最大100文字しかありません。
GPUを持ち出すほどではありません。
小さなストリーム変換器としてShrike-Liteで遊ぶのが一番似合う問題
でしょう。
B - Break a Stick
1本の棒がN個の部分に分かれており、どこか1箇所の切れ込みで折ったとき、左右の長さの差を最小にする問題です。
Nは最大100です。
Shrike-Liteで考える
これも十分入りそうです。
Aと違うのは、入力を受け取った瞬間には答えを確定できないことです。
棒全体の長さは、最後のL_iを受信するまで分かりません。
そこで入力中は、
total += L_i
L_iを保存
としておき、入力終了後に各切れ目を順番に確認します。
L_iは最大10^5なので17bit、100個保存しても1700bit程度です。
全長も24bitあれば足ります。
99箇所の切れ目を1クロックに1個ずつ処理しても、100クロック程度です。
無理に並列化する必要はありません。
他の計算機では
CPUなら当然簡単です。
AVX、GPU、仮想理想FPGAで頑張ることもできますが、問題が小さすぎます。
Shrike-Liteの中で素直に処理するくらいがちょうどよい
と思います。
AとBは今回のShrike-Lite実装候補です。
C - On a Diet
毎日のおやつについて、直近M日間で実際に食べたカロリーの合計を見ながら、その日のおやつを食べるか決める問題です。
Shrike-Liteで考える
演算自体は簡単です。
加減算と比較だけなので、1入力/clockのストリーム処理にできそうです。
問題はメモリです。
M日前に何を食べたか覚えておく必要があり、最大では20万要素分の履歴が必要です。
30bit程度の値を20万個持つと、約750KiBになります。
Shrike-Liteには入りません。
さらに入力だけでも最大約6Mbitあり、SPI通信もかなり厳しくなります。
並列計算向きか
こちらも微妙です。
その日の判定結果が次の日以降の状態を変えるため、処理に強い逐次依存があります。
要素数は多いのですが、
「全部の要素を同時に計算する」
という形にはしにくい問題です。
大きなメモリを持つ普通のCPUで順番に処理するのが素直でしょう。
見送ります。
D - Bomber Mad
最大50万マスのグリッドを探索する問題です。
公式解説では多始点BFSで処理できます。
計算機目線で見ると、各マスの状態を読みながら探索範囲を広げていく、かなり素直な処理です。
計算機アーキテクチャ目線では
Shrike-Liteでは、まずグリッド全体の状態を保持するだけでも厳しいです。
GPUなら、同じBFS深さにいるマスを大量のthreadへ配ることはできます。
ただし各threadの仕事は、隣接マスの状態を読んで、必要なら更新することです。
大量の演算器を使うというより、
共有されたグリッド状態をメモリから読み書きする
ことが中心になります。
AVXやFPGAも、不規則な探索先を追いかける処理にはあまり向きません。
並列化は可能ですが、今回は普通にCPUでBFSするのが一番安心そうです。
見送ります。
E - Odd Cycle
無向グラフから奇数長の閉路を探す問題です。
公式解説を読むと、二部グラフ判定を利用して解けます。
計算機アーキテクチャ目線では
処理の中心はグラフ探索です。
隣接リストを読み、訪問済みか確認し、色や親頂点を更新していきます。
次に読む場所がデータ依存になるため、メモリアクセスはかなり不規則です。
Shrike-Liteにはそもそもグラフを保持するメモリがありません。
GPUで探索を並列化することはできますが、Dと同様に共有状態へのアクセスが中心になります。
AVXやFPGAにもあまり嬉しい形ではありません。
普通にCPUで
「やった、二部グラフ判定だ！」
と喜びを感じながら解くのがおススメです。
F - Centroid of a Slice
凸多角形を切り分けたときの重心を、多数のクエリについて求める問題です。
最初に問題を見たときは、
そもそも多角形の重心ってどうやって求めるんだ？
というところからでした。
公式解説を読むと、多角形を三角形へ分け、面積と一次モーメントを累積しておけば、各クエリを高速に処理できるようです。
ここでは解法そのものより、変形後の計算の形に注目します。
並列計算向きの形になっている
各辺について必要になるのは、座標から作る64bit級の整数積和です。
そして、
各辺の計算は互いに独立
です。
さらにクエリも最大20万個あり、それぞれ独立に処理できます。
これはC、D、Eとはかなり違います。
Shrike-Liteには重すぎますが、
- AVXなら複数の辺をまとめて積和演算
- GPUなら多数のクエリをthreadへ分配
- 仮想理想FPGAなら乗算器や加算器を大量配置
と、それぞれ並列化する余地があります。
公式解法がすでにO(N+Q)なので、CPUでも十分高速です。
しかし、
CPUで速く処理できる形まで整理した結果、むしろ並列計算機が好きそうな処理になった
というところが面白い問題です。
今後の記事候補にします。
G - Cascading Grid
最大30×30のグリッドに対して、ある操作を繰り返し、最終状態の得点を最大化する問題です。
問題文自体は分かりやすいのですが、効率的な解法は思いつきませんでした。
公式解説には最大流による解法があります。
また、ユーザー解説としてseekworserさんのbitmask DPを使う方法も掲載されています。
今回はこの解法が計算機アーキテクチャ的に面白そうです。
行間は逐次、行内は大量並列
この解法を読むと、下の行から上の行へと順にDPを行っています。
面白いのは、1行の状態の表し方です。
1行の幅は最大30ですが、1行の中で#で区切られた+/-の連続セクション数は最大15です。
同じセクション内のマスは操作によってまとめて#になるため、各セクションについて
「元の+/-のまま」／「#に置き換えられた」
を1bitで表せます。
ということは、1行の状態を最大15bitのbitsetで表せます。
行の状態数は最大で、
2^15 = 32768状態
です。
行間の依存関係を処理しながら、この32768状態それぞれの最大スコアをDPで上の行へ順次伝搬させていくような計算ですね。
また、さらに興味深いのは、DPを更新する際に、どうやって最大値を見つけ出すか、という処理の部分です。
状態間の対応を効率よく処理するためにゼータ変換が使われており、その1段の中には大量の独立した比較があります。
ここが面白いところです。
Shrike-Liteには厳しい一方で、
AVXなら複数のDP状態のmax演算をまとめて処理
GPUなら多数のmaskをthreadへ分配
仮想理想FPGAなら比較器を大量に並列配置
などの、並列処理構成が考えられます。
例えば最大15bitなら、ゼータ変換の1段で最大16384組の比較が生じます。
この部分の実装を、
16384個の比較器をどーん
にしてみるという、仮想理想FPGAらしい遊び方ができそうです。
Fと並んで、大型並列機で試してみたい問題です。
今回のまとめ & 独り言
ABC472を、ざっくり計算機アーキテクチャごとに並べると次のようになりました。
| 問題 | Shrike-Lite | 仮想理想FPGA | AVX | GPU | CPU | 印象 |
|---|---|---|---|---|---|---|
| A | ◎ | △ | △ | × | ◎ | 小さなストリーム変換器 |
| B | ◎ | △ | △ | × | ◎ | 小規模な保持＋逐次比較 |
| C | × | ○ | ×〜△ | △ | ◎ | 大きな履歴と強い逐次依存 |
| D | × | △ | △ | ○ | ◎ | BFS。共有状態アクセス中心 |
| E | × | △ | △ | △ | ◎ | グラフ探索。CPUが素直 |
| F | × | ◎ | ◎ | ○〜◎ | ◎ | 独立した整数積和と多数のクエリ |
| G | × | ◎ | ◎ | ◎ | ◎ | bitmask DP。段内に大量の並列max |
AとBはShrike-Liteで実装してみます。
C、D、Eは今回は見送ります。
この3問は、
- 前の状態を見て次を決める
- キューや隣接リストをたどる
- 次に読むメモリ位置がデータ次第で変わる
といった、汎用CPUの柔軟さが生きる問題に見えます。
一方、FとGは少し違いました。
競技プログラミングの解法によって元問題を整理した結果、
F：大量の独立した積和演算
G：大量の独立したmax演算
という、並列計算機が好きそうな形が現れます。
これまでShrike-Liteでは、後半問題は早い段階で見送りにすることが多かったのですが、別の計算機まで視野を広げると、むしろ後半に面白い題材が埋まっていることがあります。
とはいえ、主役は今まで通り、
Shrike-LiteとFPGA
です。
CPU、AVX、GPUは、その周辺に増えた新しい遊び道具として眺めてみます。
今週はまずAとBをShrike-Liteで試します。
FとGは、Shrike-Liteへの実装が終わってから、改めて考えましょう。
前回：
Shrike-LiteでAtCoder問題を解く(38) ABC471E（後編） - 結局Shrike-Liteには入りませんでした
次回：
ABC472AのShrike-Lite実装（予定）