競技プログラミングとヒューリスティック最適化

atcoder を中心とした競技プログラミングの取り組み。明確な最適解アルゴリズムが存在する問題（DP・グラフ・数論）と、最適解が NP困難で近似・発見的解法を競う マラソン／ヒューリスティック (AHC) に大別される。

ヒューリスティック (AtCoder Heuristic Contest)

スコア最大化を狙う長時間コンテスト。代表的な探索戦略:

• 山登り法 (hill climbing) — 現状態を少し変えてスコアが上がる方向へ遷移
• ビームサーチ — 有望な部分解を幅優先で複数保持
• 例: AHC013（同種端子を結線、領域分割＋移動）、AHC014（端点に点を作り矩形を作る、線分の交差判定が必要）。実装力＝複雑な処理を捌くスタミナが鍵で、幾何ライブラリの整備が課題に挙がる。
• CODINGAME（コドゲ）— コードを書いてゲーム AI を競う常設コンペ。

古典アルゴリズム題

• DP — 部分和・ナップサック、半分全列挙、桁 DP など
• 最小費用流、ゼータ／メビウス変換、バタフライ演算
• ハルヒ問題（最小超置換問題） — 全順列を含む最短文字列。著者に「Anonymous 4chan poster」が名を連ねる逸話で有名
• 瓶パッキング問題 (BPP) — First-Fit, Bottom-Left などの近似。半径一定なら超球充填＝符号理論に接続

関連: atcoder / segment-tree / knapsack-dp / _moc-algorithm