競技プログラミングで活用できるアルゴリズムのテクニック
高速乗算の実装
以下の実装は誤差が発生せず高速に動作します。
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 投稿
アルゴリズム実践トレーニングカリキュラム
配列操作編
二分探索と要素削除
二分探索：境界条件の2つの実装方法に注意。rightの定義、if条件と境界更新ロジックが重要。
左閉右閉左閉右開
rightの定義len(arr) - 1len(arr)
ループ条件while left <= right:while left < right:
境界更新right = mid - 1right = mid
class Solution:
def binary_search(self, arr: List[int], target: int) -> int:
...
6月26日 18:36 投稿
Codeforces Round 999 合併部門における競技プログラミング問題の解説
A - 数列の並べ替えとスコア最適化
長さ n の整数列 a が与えられる。初期値が 0 の変数 s に対して、a の要素を順に加算する。s が偶数になった場合、ポイントを 1 加算した上で s を 2 で割った余り（つまり s % 2）に更新する。この操作を繰り返す中で、得られるポイントの合計を最大化するために、a の要素をどのように並び替えるべきか。
重要な観察として、奇数の個 ...
6月22日 18:23 投稿
第14回 藍橋杯 C/C++ Bグループ 省大会 競技課題の解説と実装
1. 日付統計 (Date Statistics)
8桁の数値が並んだ100個のデータから、2023年に存在する有効な日付（YYYYMMDD形式）がいくつ作れるかをカウントする問題です。部分列として抽出する必要があるため、全探索や動的計画法でアプローチします。このコードは計算済みの結果を出力する例です。
#include <iostream>
int main() {
// 探索アルゴリズムによって算出され ...
6月9日 22:20 投稿
AtCoder Beginner Contest 366 の問題解説と実装
はじめに
今回のコンテストでは問題Eに大部分の時間を費やすことになり、残り15分でようやく正解にたどり着くという危ない場面でした。緑色レベルの問題にも苦戦するようでは、まだまだ実力不足を感じます。
A - Election 2
高橋君と青木君のどちらかが過半数の票を獲得したかどうかを判定するシンプルな問題です。
#include <iostream>
using namespace std; ...
6月4日 17:22 投稿
競技プログラミング問題精選: 考察技法と実装(ICPC/APIO/NOI対策)
P6880 JOI 2020 Final オリンピックバス
有向グラフが与えられる。辺を通るコスト \(C_i\)、1本の辺を反転させるコストを \(D_i\) とする。頂点 \(1\) から \(n\) へ、さらに \(n\) から \(1\) へ移動するとき、辺の反転を高々1回まで許したときの最小コスト和を求めよ。
全ての辺に対して反転を試すのは非効率なので、影響を解析する。\(f(s,t)\) を元のグラフでの \(s\) ...
6月3日 16:05 投稿
循環配列における次の大きな要素の検出と「雨水を貯める」問題のアルゴリズム解説
503. 循環配列における次の大きな要素 II (Next Greater Element II)
循環配列（最後の要素の次が最初の要素となる配列）が与えられた場合、各要素に対して「次に大きい要素」を見つける問題です。要素xの次に大きい要素とは、配列を巡回順で走査した際、xの後に現れる最初のxより大きな数値を指します。そのような数値が存在しない場合は-1を出力します。
解法アプロー ...
5月16日 17:53 投稿
ICPC 2018 横浜大会における主要アルゴリズムの解説
2018年に開催されたICPCアジア地区予選横浜大会の出題問題より、いくつかの典型的な実装手法とアルゴリズムの考え方を解説します。
1. 文字列と数値の混合ソート
文字列中に含まれる数値とアルファベットを個別に識別し、辞書順および数値の大きさに基づいた比較を行う問題です。主なロジックは以下の通りです。
両文字列が完全に一致する場合は対象外とする。
...
5月16日 06:48 投稿