AtCoderコンテスト328の問題解説
A: 閾値以下の合計
数値リストから指定された閾値以下の要素の合計を算出します。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int num, threshold;
cin >> num >> threshold;
vector<int> values(num);
int total = 0;
for (int &val : values) {
cin >> val;
if (val days[i];
int base = i ...
6月25日 22:30 投稿
Codeforces 近況コンテストにおける高度なアルゴリズム技法と実装パターン
区間交差関係に基づく最小全域木構築
与えられた区間集合において、交差する区間同士を結ぶ辺の重みを権重の差とし、生成されるグラフの最小全域木を求める問題。辺を全列挙すると計算量が爆発するため、幾何学的性質と貪欲戦略を組み合わせる。権重が小さい区間から順にアクティブな集合に追加し、各区間の挿入・削除タイミング（スライン法）において、権重でソートされ ...
6月24日 18:37 投稿
グラフアルゴリズムの実装と応用
グラフの冗長接続検出
無向グラフにおいて、ツリー構造を維持しながら冗長な接続を特定する方法について説明します。
Union-Findによる冗長接続の検出
#include <iostream>
#include <vector>
using namespace std;
class UnionFind {
private:
vector<int> parent;
public:
UnionFind(int n) : parent(n + 1) {
for (int i = 0; i &l ...
6月19日 19:16 投稿
グラフ理論のアルゴリズム実装ノート
1. 隣接行列を用いたDFS（再帰実装）
class GraphStructure {
public:
GraphStructure(int nodes);
void addConnection(int src, int dst);
void traverseDFS(int startNode);
private:
int nodeCount;
vector<vector<int>> adjacencyMatrix;
vector<bool> visitedFlags;
void dfsRecursive(int current);
};
GraphStruc ...
6月15日 20:13 投稿
農場ネットワークの最小全域木問題
問題概要
ジョン農場主が町長に選出されました！彼の選挙公約の一つは、町全体にインターネットを導入し、すべての農場を接続することです。もちろん、彼はあなたの助けが必要です。
ジョンはすでに自身の農場に高速ネットワーク回線を設置済みであり、これを他の農場と共有したいと考えています。費用を最小限に抑えるため、すべての農場を接続する最短の光ファイバーを ...
6月14日 18:40 投稿
Kruskal再構築木の学習メモ
前提知識
Kruskal最小/最大全域木アルゴリズム、ダブリング（Binary Lifting）の知識を前提とします。
Kruskal再構築木を構築すると、最小全域木上の2点間のパスの最大重み、および重み ≤ w の辺のみを通って到達可能な点の集合を O(log N) で求めることができます。
近年の競技プログラミングでは出題頻度は控えめですが、該当する問題に遭遇した際に非常に強力なツ ...
5月19日 05:15 投稿