2026-09-04
pick.cpp
#include <cstdint>
#include <span>
int pick(std::span<const std::uint8_t> bytes, int n) {
}
bytes には、0〜255 のどれもが同じ確率で出る乱数のバイトが並んでいます。これを先頭から使い、0 以上 n 未満の整数のどれもが同じ確率で出るように1つ返す pick を書いてください。バイトを n で割った余りを使い、そのままでは余りの出方に偏りが出るバイトは捨てて次のバイトに進みます。捨てるのは偏りをなくすのに要る最小限のバイトだけにします。n は 1〜256 で、bytes には使えるバイトが必ず含まれているものとします。
入力例 1
pick(std::array<std::uint8_t, 2>{255, 7}, 3)
出力例 1
1
入力例 2
pick(std::array<std::uint8_t, 3>{252, 255, 9}, 6)
出力例 2
3
入力例 3
pick(std::array<std::uint8_t, 1>{200}, 1)
出力例 3
0
Reference
int pick(std::span<const std::uint8_t> bytes, int n) {
const int limit = 256 - 256 % n;
for (int b : bytes)
if (b < limit)
return b % n;
std::unreachable();
}
256 を n で割った余り 256 % n が、どの余りにも均等には配れないバイトの数です。limit = 256 - 256 % n は n の倍数なので、0〜limit - 1 のバイトなら、余り 0〜n - 1 のそれぞれにちょうど limit / n 個ずつ対応します。limit 以上のバイトが出たら捨てて、次のバイトを見ます。例1では limit が 255 なので 255 だけを捨て、7 % 3 の 1 を返します。
捨てずに b % n を返すと、n が 3 のときは余り 0 に 86 個、1 と 2 に 85 個ずつのバイトが対応し、0 だけがわずかに出やすくなります。
掲載したのは参考実装で、唯一の正解ではありません。ループを抜けるのは使えるバイトが尽きたときだけで、問題の前提ではそこに来ないので std::unreachable() を置いています。実際のコードでは、足りなくなったら乱数源からバイトを読み足します。標準ライブラリで済ませるなら、std::uniform_int_distribution が偏りのない範囲変換をしてくれます。