Namaran

Code daily. Without assist.

2026-11-03

token_bucket.cpp

struct TokenBucket {
    long long capacity;
    long long rate;
    long long tokens;
    long long last;
};

bool try_acquire(TokenBucket& b, long long now) {
}

トークンバケットは、処理1回ごとにトークンを1つ使わせ、トークンが無いときは処理を断ることで、一定時間あたりの処理の回数を抑える仕組みです。TokenBucket は、ためておけるトークンの上限 capacity、1秒あたりに補充するトークンの数 rate、いまのトークンの数 tokens、最後に補充を計算した時刻 last を持ちます。時刻 now にトークンを1つ取り出す try_acquire を書いてください。まず last から now までの秒数に応じてトークンを補充しますが、capacity を超える分は捨てます。補充後にトークンが1つ以上あれば1つ減らして true を、無ければ false を返します。時刻は秒単位の整数で、now は last 以上とします。例では、バケットを {capacity, rate, tokens, last} と書きます。

入力例 1

b = {3, 1, 0, 0}
try_acquire(b, 2)

出力例 1

true
b = {3, 1, 1, 2}

入力例 2

b = {3, 1, 0, 0}
try_acquire(b, 100)

出力例 2

true
b = {3, 1, 2, 100}

入力例 3

b = {3, 2, 0, 5}
try_acquire(b, 5)

出力例 3

false
b = {3, 2, 0, 5}
Reference
bool try_acquire(TokenBucket& b, long long now) {
    b.tokens = std::min(b.capacity, b.tokens + (now - b.last) * b.rate);
    b.last = now;
    if (b.tokens == 0)
        return false;
    --b.tokens;
    return true;
}

補充する数は、経過した秒数 now - b.last に b.rate を掛けたものです。それを今のトークンに足した値と b.capacity の小さいほうを std::min で選ぶので、上限を超えた分は捨てられます。入力例 2 は 100 秒使われなかったバケットで、足すだけなら 100 個たまりますが、上限で 3 個に抑えられ、1つ使って 2 個が残ります。この上限が、しばらく空いたあとに一度に通せる処理の数を決めます。上限が無いと、長く使われなかったバケットはその間の分をまとめて通してしまい、一定時間あたりの回数を抑える役目を果たせません。

補充を計算したら、b.last を now に進めます。進めないと、次の呼び出しで同じ時間の分をもう一度補充してしまいます。トークンが無くて断るときも補充の計算は済んでいるので、b.last は進めたままでかまいません。入力例 3 は経過時間が 0 秒なので補充は無く、false を返します。

std::min は2つの引数が同じ型でないとテンプレート引数を推論できないので、メンバをすべて long long にそろえてあります。掲載したのは参考実装で、唯一の正解ではありません。