はじめに
今回は、JPRS Programming Contest 2026#2（AtCoder Beginner Contest 470）B - MonocolorをShrike-Liteで解きます。
問題は、N個のボールそれぞれに色C_iが付いており、すべて同じ色にするために必要な塗り替え回数の最小値を求めるものです。
最も多い色へ他のボールを塗り替えればよいので、色vの個数をcount[v]とすると、答えは次のようになります。
N - max(count[v])
今回の方針
入力は最大でも次の101byteです。
N
C[0]
C[1]
...
C[N-1]
各値は7bitあれば表現できますが、通信では1byteずつ送ります。
この程度の通信量なら、既存の4MHz SPIバースト通信をそのまま使えますね。
FPGA側では、色ごとの個数をDistributed RAMへ保存するのがよさそうです。
各カウント値は0～100なので7bitです。
実際のRAMは、アドレス幅を7bitとして次の構成にしました。
128 × 7bit
使用するのはそのうちのアドレス1～100です。
最後に最大値を探さない
C++ / Pythonなら、すべての入力を受信した後でcount[1]～count[100]を読み出し、最大値を探せば答えを求められます。
ただし、それをFPGAで行うと、最後にもう一度100要素を走査する回路が必要になります。
そこで、今回は各色のカウントを増やした時点で、その値と現在の最大値を比較することにしました。
old_count = count[color]
new_count = old_count + 1
count[color] = new_count
if new_count > max_count:
max_count = new_count
これなら最後の入力を処理し終えた時点でmax_countも確定しています。
あとは、
answer = N - max_count
を計算するだけです。
DistRAMへのread-modify-write
ForgeFPGAのDistRAMは同期readなので、読み出して、その値を増やして、同じアドレスへ書き戻す処理を1クロックへ無理に詰め込みません。
1色につき、次の3状態で処理します。
RMW_READ
RMW_CAPTURE
RMW_WRITE
実装の中心部分は次のようになりました。
RMW_READ: begin
// DistRAMから、この色の現在のカウント値を読み出す。
state <= RMW_CAPTURE;
end
RMW_CAPTURE: begin
// 読み出したカウント値に1を加える。
new_count <= ram_read_data + 7'd1;
state <= RMW_WRITE;
end
RMW_WRITE: begin
// このクロックでwrite-backし、必要なら最大値を更新する。
if (new_count > max_count)
max_count <= new_count;
if (color_is_last)
state <= PREPARE_REPLY;
else
state <= RECEIVE_C;
end
50MHzなら3クロックは約60nsです。
一方、4MHz SPIでは1byteの転送に2µsかかります。
FPGA内部のread-modify-writeは、次の色が到着するまでに十分終わります。
今回は速度を欲張るより、単純な回路を優先しました。
DistRAMの記述
DistRAMの記述には、以前ABC468Bで使用した実装とRenesasのAN-FG-018のサンプルを参考にしました。
RAM本体へRESETを掛けず、writeとreadをそれぞれクロック同期で記述しています。
reg [6:0] mem_ram [127:0];
always @(posedge i_wr_clk) begin
if (i_wr_en)
mem_ram[i_wr_addr] <= i_wr_data;
end
always @(posedge i_rd_clk) begin
if (!i_rst_n)
o_rd_data <= 7'd0;
else if (i_rd_en)
o_rd_data <= mem_ram[i_rd_addr];
end
RAM本体をRESETで一括初期化すると、DistRAMとして推論されなくなる可能性があります。
そこでSTART受信後に、アドレス1～100へ0を順番に書き込みます。
初期化には100クロック必要です。
50MHzでは2µsなので、4MHz SPIでNを1byte受信している間とほぼ同じ時間です。
最後の入力だけ少し注意する
最後の色を受信した時点では、まだ回答は確定していません。
最後の色についても、
read
↓
count+1
↓
write-back
↓
max_count更新
まで完了させる必要があります。
そこでRMW_WRITEの次にPREPARE_REPLYを置き、1クロック後に回答を作ります。
PREPARE_REPLY: begin
// 最後のwrite-backとmax_count更新を反映した次クロックで確定する。
tx_data <= {1'b1, n_reg - max_count};
state <= DONE;
end
nonblocking assignmentで更新したmax_countを同じクロックで回答計算に使わないようにしています。
SPI通信
通信条件はこれまでのSPIテンプレートと同じです。
| 項目 | 設定 |
|---|---|
| SPIクロック | 4MHz |
| CPOL | 0 |
| CPHA | 0 |
| データ幅 | 8bit |
| ビット順 | MSB first |
問題データは、
N + C[0] ... C[N-1]
を1回のCS Lowでまとめて送信します。
最大でも101byteなので、既存の256byteバーストへそのまま収まります。
回答もこれまでと同じ1byte形式です。
bit 7 : VALID
bit 6:0 : ANSWER
処理が終わるまでMicroPython側からNOPを送り、VALID=1になるのを待ちます。
AIに実装を依頼する
今回も、実装はAIへ依頼しました。
主な依頼内容は次のとおりです。
- ABC468BのDistRAM版を参考にする
- Renesas AN-FG-018の実ソースを確認する
- 128×7bitのDistRAMを使う
- DistRAM本体へRESETを掛けない
- 同期readを使ってread-modify-writeする
- 更新後の値で
max_countを逐次更新する - 最後の入力処理後に
N - max_countを返す - AtCoder用SPIテンプレートV3を利用する
実装前に仕様をまとめ、既存のDistRAM実装も参考資料として渡しました。
完全なソースコードはGitHub側へ掲載します。
合成してみる
ForgeFPGA Workshopで合成・配置を行いました。
結果は次のとおりです。
100色分のカウントを持ちながら、CLB使用率は約31%に収まりました。
DistRAMを確認する
Floorplanを見ると、DistRAMは64bit dual-port RAM × 14個として配置されていました。
64bit × 14 = 896bit
今回用意した、
128 × 7bit = 896bit
とちょうど一致します。
100色×7bitで実際に必要なのは700bitですが、7bitアドレスの128要素RAMとして実装したため、物理的には896bitになっています。
狙いどおりFF配列ではなくDistRAMへ入っていることを確認できました。
Timing Analysis
Achievable Frequencyは102.870MHzでした。
50MHz動作には十分な余裕があります。
今回のread-modify-writeは1色あたり数クロック使っていますが、SPIの入力速度に対して内部処理は十分速いため、無理に短縮する必要はなさそうです。
実機試験
最後にShrike-Lite実機で確認します。
MicroPython側ではFPGAへabc470b.binを書き込み、4MHz SPIでテストケースを順番に送信しました。
テストコードでは公式サンプル3件に加え、境界条件や連続更新を確認しています。
主なケースは次のとおりです。
| ケース | N | 期待値 | 結果 |
|---|---|---|---|
| sample1 | 4 | 2 | 2 |
| sample2 | 5 | 0 | 0 |
| sample3 | 9 | 7 | 7 |
| min | 1 | 0 | 0 |
| all_same_max | 100 | 0 | 0 |
| all_different | 100 | 99 | 99 |
| two_colors_equal | 100 | 50 | 50 |
| max_updates_late | 10 | 8 | 8 |
| repeated_consecutive | 8 | 4 | 4 |
| start_reuse_first | 4 | 1 | 1 |
| start_reuse_second | 4 | 3 | 3 |
結果は、すべてPASS、最大ケースでも実行時間は 4ms 程度でした。
ACがとれそうですね。
今回のまとめ
今回はABC470B「Monocolor」をShrike-Liteで実装しました。
4MHz SPIでは、1色のread-modify-writeに数クロック使っても十分余裕があります。
今回も、無理に高速化するより、データを適した場所へ置いて、単純な処理を順番に進める構成がShrike-Liteには合っているようです。
前回：
Shrike-LiteでAtCoder問題を解く(30)：Interlude - ABC470の各問題をFPGA目線で見てみる
次回：
Shrike-LiteでAtCoder問題を解く(32)：Detour：ABC470A - 公式ジャッジにVerilogで参加してみる
今回のコード全文：
第31回コード全文