Shrike-LiteでAtCoder問題を解く(21)：ABC468B - Corridor Watch

Last updated at 2026-07-29Posted at 2026-07-28

はじめに

前々回は、ABC468の各問題をShrike-Liteで実装できそうかという視点から眺めました。

その中でB問題については、100マス分の監視状態をそのまま保持すると、ガードマンを受信するたびに多数のFFを書き換える回路が必要になりそうです。

そこで、次の問いを残していました。

100マスそれぞれの監視状態を、本当に保持する必要があるのでしょうか。

今回は、この問いを回収します。

問題

ABC468B - Corridor Watch

横一列にM個のマスがあります。

文字列Sのi文字目がGなら、その位置にガードマンがいます。ガードマンから距離D以内のマスは監視されます。

監視されていないマスの個数を求めます。

制約は次のとおりです。

1 ≤ M ≤ 100
0 ≤ D < M
Sの長さはM
Sの各文字は'.'または'G'

愚直に実装する場合

C++やPythonなら、長さMの配列を用意し、最初はすべてのマスを「監視されていない」としておけばよさそうです。

ガードマンを見つけるたびに、

[i-D, i+D]

の範囲を監視済みへ書き換えます。

Mは最大100なので、この方法でも十分に高速です。

しかし、同じ処理をFPGAへそのまま持ち込むと、少し様子が変わります。

100bitの監視状態をFFで保持し、ガードマンの位置に応じて複数のbitを書き換える場合、多数の条件分岐やMUXが必要になりそうです。

BRAMへ保存して1マスずつ更新する方法もありますが、その場合は同じ配列を何度も読み書きするFSMが必要そうです。

問題の制約は小さいのに、回路はあまり素直ではありません。

そこで今回は、各マスの状態を保存しない方法を考えます。

監視区間を左からまとめる

FPGA内部では、マスの位置を0始まりで扱うことにします。

各ガードマンの監視距離は、全員同じDです。

そこで、左から文字列を読んでいくと、ガードマンの監視区間も左から順番に現れます。

この性質を利用して、次の値だけを保持します。

position       現在処理している位置
left           ここまでに処理を終えた範囲の右端の次
answer_count   すでに確定した未監視マス数

初期値は、

position     = 0
left         = 0
answer_count = 0

です。

位置positionにガードマンがいる場合、その監視区間は半開区間で、

[max(0, position-D), min(M, position+D+1))

と表せます。

現在のleftより監視区間の左端が右にあるなら、その間はどのガードマンにも監視されません。

式で書けば、

left < position - D

を判定すればよいのですが、position < Dのときに負数が現れます。

そこで、同値な条件へ変形します。

left + D < position

この条件が成立した場合、監視されていない隙間の長さは、

position - (left + D)

です。

したがって、

answer_count += position - (left + D)

とします。

その後、このガードマンの監視区間の右端の次までleftを進めます。

left = min(M, max(left, position + D + 1))

文字列をすべて処理した後、末尾に残った未監視区間を加えます。

answer_count += M - left

各マスの監視状態を保存する必要はありません。

左から一方通行で処理しながら、監視区間を順番に統合するストリーム処理になりました。

公式サンプル1で確認する

公式サンプル1は次の入力です。

M = 7
D = 1
S = .G...GG

最初のガードマンは位置1にいます。

left + D = 0 + 1 = 1
position = 1

left + D < positionは成立しないため、手前に未監視の隙間はありません。

このガードマンは位置0から2まで監視するので、leftを3へ進めます。

left = 3

次のガードマンは位置5です。

left + D = 3 + 1 = 4
position = 5

今回は、

4 < 5

が成立します。

位置3の1マスは監視されていないため、

answer_count += 5 - 4

として1を加えます。

その後、監視区間の右端の次までleftを進めます。

left = 7

最後の位置6にもガードマンがいますが、すでにleft=7なので新しい隙間はありません。

末尾にも未監視区間は残らず、答えは1になります。

SPI通信仕様

RP2040側では、文字列を次の値へ置き換えます。

'.' → 0x00
'G' → 0x01

RP2040側では、監視区間の計算や事前集計は行いません。

今回の通信順序は次のとおりです。

順番	MOSI	内容
1	`0xFF`	SPI RESET
2	`0x00`	RESET ACK確認
3	`0xFE`	START
4	`M`	START ACK確認とM送信
5	`D`	D送信
6	`S[0]`～`S[M-1]`	`.`または`G`を`M` byteのバーストで送信
7	`0x00`	回答受信

SPIクロックは4MHzです。

FPGAからの回答は1byteです。

bit 7   VALID
bit 6:0 ANSWER

答えは最大100なので、7bitに収まります。

FPGA側の構成

FSMは次の6状態です。

WAIT_START
WAIT_M
WAIT_D
RECEIVE_S
PREPARE_REPLY
DONE

主なレジスタは次のとおりです。

m_reg
d_reg
position
left
answer_count

文字列全体を保存するメモリや、100bitの監視状態はありません。

AIに実装を依頼する

今回も、先に通信仕様とアルゴリズムを決めてから、AIへVerilogとMicroPythonのコード実装を依頼しました。

主な条件は次のとおりです。

100bitの監視状態を作らない
文字列全体を保存しない
left + D < positionで隙間を判定する
区間演算は明示的にビット幅を拡張する
最後の文字を反映してから回答を作る
既存のspi_target.vは変更しない
SystemVerilogは使用しない

完成したコードについて、通信仕様やアルゴリズムが意図どおりに実装されていることを確認します。

完全なソースコードはGitHubへ掲載します。

第21回コード全文

区間演算の実装を確認する

今回のアルゴリズムの中心部分です。

// 8bit同士の加算結果を確実に保持し、式評価幅による桁落ちを避けるため、
// 区間演算は加算前に9bitへ拡張する。
wire [8:0] left_plus_d_ext =
    {1'b0, left} + {1'b0, d_reg};
wire [8:0] position_ext = {1'b0, position};

// position - Dを作らず、left + D < positionで負数を避けて隙間を判定する。
wire       has_gap = left_plus_d_ext < position_ext;
wire [8:0] gap_ext = position_ext - left_plus_d_ext;

M、D、position、leftは8bitレジスタです。

値そのものは8bitに収まりますが、Verilogの式評価幅による桁落ちを避けるため、加算前に9bitへ拡張しています。

監視区間の右端は、次のように計算します。

// ガードの監視区間の右端の次までleftを進め、Mを超える場合はMへ丸める。
wire [8:0] right_exclusive_ext =
    position_ext + {1'b0, d_reg} + 9'd1;
wire [7:0] right_clamped =
    (right_exclusive_ext >= {1'b0, m_reg})
        ? m_reg
        : right_exclusive_ext[7:0];
wire [7:0] left_after_guard =
    (right_clamped > left) ? right_clamped : left;

これで、

left = min(M, max(left, position + D + 1))

を実装できていますね。

1文字を受信する処理を確認する

文字列受信中は、0x01だけをGとして扱います。

RECEIVE_S: begin
    if (rx_data_strobe) begin
        // 0x01を'G'として扱い、それ以外のデータ値は'.'として扱う。
        if (rx_data == 8'h01) begin
            left <= left_after_guard;
            if (has_gap)
                answer_count <= answer_after_guard_ext[7:0];
        end

        position <= position_next_ext[7:0];
        tx_data  <= 8'h00;

        if (position_next_ext >= {1'b0, m_reg})
            state <= PREPARE_REPLY;
    end
end

.の場合はpositionだけを進めます。

Gの場合だけ、未監視の隙間を加算し、leftを監視区間の右側へ進めます。

ここも問題はありません。

最後の文字を処理してから回答を作る処理を確認する

最後の文字がGだった場合、その文字によってleftとanswer_countが更新されます。

同じクロックで回答まで作ると、ノンブロッキング代入前の古い値を参照する可能性があります。

そこで、最後の文字を受信した後にPREPARE_REPLYを1クロック挟みます。

PREPARE_REPLY: begin
    // 最後の文字に対するleftとanswer_countの更新を反映してから、
    // PREPARE_REPLYで末尾の未監視区間を加えて回答を作成する。
    tx_data <= {1'b1, final_answer_ext[6:0]};
    state   <= DONE;
end

最終回答は、

answer_count + (M - left)

です。

SPIは4MHz、FPGA内部クロックは50MHzなので、返信準備に1クロックを追加しても、次のSPIバイトが届くまでに処理は完了します。追加のNOPなどは不要です。

コード全体に問題がないことを確認できたら、ForgeFPGA Workshopで合成とBitstream生成を行い、Shrike-Liteの実機テストへ進みます。

合成結果

ForgeFPGA Workshopで合成と配置配線を行いました。

リソース使用量

CLB使用率は31.43%でした。

Timing Summary

WNS = +1.640ns
TNS = 0ns

項目	結果
制約周期	20.000ns
達成可能周期	18.359ns
達成可能周波数	54.469MHz

50MHz制約を満たしました。

クリティカルパスのロジックは9段です。

50MHz制約を満たしたので、このまま実機試験へ進めます。

実機で動作確認する

Shrike-Liteへabc468b.binを書き込み、16ケースを実行しました。

[shrike_fpga] flashing: abc468b.bin
[shrike_flash] FPGA programming done.
CONFIG BITSTREAM=abc468b.bin SPI_BAUDRATE=4000000

公式サンプル1の結果です。

NAME=official_sample_1
M=7
D=1
S=.G...GG
RX=0x81
VALID=1
RESULT=1
EXPECT=1
RESET_ACK_RX=0x5A
START_ACK_RX=0xA5
PRE_REPLY_OK=1
PASS
TIME_US=1230

最後の文字がGのケースもPASSしました。

NAME=final_character_guard
M=10
D=1
S=..G......G
RX=0x85
VALID=1
RESULT=5
EXPECT=5
RESET_ACK_RX=0x5A
START_ACK_RX=0xA5
PRE_REPLY_OK=1
PASS
TIME_US=1614

最大長M=100のケースです。

NAME=maximum_m_100
M=100
D=9
S=G.........G.........G.........G.........G.........G.........G.........G.........G.........G.........
RX=0x80
VALID=1
RESULT=0
EXPECT=0
RESET_ACK_RX=0x5A
START_ACK_RX=0xA5
PRE_REPLY_OK=1
PASS
TIME_US=4825

実行したケースは次のとおりです。

テスト	確認内容	結果
公式サンプル1～3	基本動作	PASS
`M=1`、`.`	最小入力・未監視	PASS
`M=1`、`G`	最小入力・監視済み	PASS
全`.`	ガードマンなし	PASS
全`G`	全マス監視	PASS
`D=0`	ガードマン自身だけ監視	PASS
先頭だけ`G`	左端処理	PASS
末尾だけ`G`	右端処理	PASS
離れた複数の`G`	複数の隙間	PASS
監視区間の重複	二重計上防止	PASS
監視区間の接触	隙間0	PASS
1マスの隙間	境界処理	PASS
最後の文字が`G`	最終更新の反映	PASS
`M=100`	最大入力長	PASS