競技プログラミングで活用できるアルゴリズムのテクニック
高速乗算の実装
以下の実装は誤差が発生せず高速に動作します。
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 投稿
アルゴリズム競プロ実装解説：括弧最適一致・グラフ着色・Mo法応用・カルテジアン木
括弧列の最適一致（ciphertext）
与えられた文字列には '('、')'、およびワイルドカード '?' が含まれます。目標は '?' を適切な括弧に置き換え、できる限り多くの一致ペアを形成し、一致不能な括弧の最小個数を出力することです。
本問題は貪欲法を段階的に適用することで解けます。まず、既存の '(' と ')' による明確な一致をスタックを用いて処理し、一致した位置はマ ...
5月20日 01:26 投稿