競技プログラミングで活用できるアルゴリズムのテクニック
高速乗算の実装
以下の実装は誤差が発生せず高速に動作します。
long long multiply(long long x, long long y, long long mod) {
long long c = static_cast<long long>(static_cast<long double>(x) * y / mod + 0.5);
c = x * y - c * mod;
if (c < 0) c += mod;
if (c >= mod) c -= mod;
return c;
}
貪欲法の応用
線分関 ...
6月30日 00:09 投稿
2023 年度 HDU マルチスクールコンテスト ラウンド 5 完全解答
本稿では、2023 年に開催された HDU 主催の大学生向け競技プログラミング大会（マルチスクール）第 5 回の各問に対するアルゴリズム解説と参考実装を示します。
A. タイフーン接近距離
問題概要
n 個の点によって構成される折線があり、q 回のクエリにおいて指定された座標からこの折線までの最短距離を計算する必要がある。データサイズは n, q ≤ 10^4 程度である。
解 ...
6月22日 20:42 投稿