はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける乱択アルゴリズム問題まとめ

競技プログラミング

乱択アルゴリズム

  • 状態集合の中で正解となるパターン数が非常に多い場合は乱択アルゴリズムが使える
  • 乱択アルゴリズムではないが、乱数を生成してmodを取ることで代入して0を判定可能 これ
  • 質のいい乱数生成器を使う必要がある
    • コードを見れば一意に定まるハッシュを使っている場合は、Hack有りコンテストなら落とされてしまうので注意

問題