2024年夏休み交流戦・練習編1
2024年夏休み交流戦・練習編1
A - 🐓
AtCoder - abc079_d
問題文
各頂点のコストが与えられ、それを1に変換するのに必要な最小コストを求める。
解法
すべての数を1にするには、直接1に変換するか、別の数に変換してからさらに変換する方法がある。
これは$floyd$アルゴリズムによる最短経路探索と似ているため、$floyd$を適用できる。
コード
#include<bits/stdc++.h&g ...
8月5日 02:59 投稿
2025 XCPC浙江省競技プログラミングコンテスト FLM問題解説
F. Challenge NPC III
多起点最短経路と第二最短経路問題。
同じ色の頂点に対してBFSを実行し、各経路の起点を維持します。同じ色の頂点から自身への経路が最短であるため、最終的に第二最短経路がkより小さいかを判定すれば十分です。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n, m, k;
cin >> ...
8月1日 18:35 投稿
アルゴリズムの応用とデータ構造
差分配列差分配列は、区間更新や多次元の範囲操作に効率的に対処するために使用されます。
一維差分
一連の値を変更する際、差分配列を使用して効率よく計算できます。
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n;
int a[n + 2], diff[n + 2];
for (int i = 1; i > a[i];
diff[i] = a[i] - a[i - 1];
...
7月22日 05:10 投稿
グラフ理論における第二最短経路
前提知識
グラフの表現方法、最短経路探索アルゴリズム、幅優先探索(BFS)の理解が必要です。
第二最短経路の分類
一般第二経路（同一辺の重複利用可能）
単純第二経路（同一辺の重複利用不可）
厳密/非厳密第二経路（最短経路と等価/非等価）
一般第二経路
配列の最大値・次大値探索と類似した手法を用います。各頂点について最短距離と第二短距離を同時に管理します。 ...
5月14日 18:44 投稿