Union-Findアルゴリズムによるグラフの連結成分とその応用
無向グラフにおける連結成分の数え上げ
この問題では、与えられた無向グラフに含まれる連結成分の総数を求める必要があります。Union-Find（素集合データ構造）を用いることで効率的に解決できます。各ノードを初期状態で自身を親とする木として扱い、エッジを通じてノードを結合していきます。パス圧縮により探索効率を高め、最終的なルートノードの数が答えとなります。
...
7月16日 16:06 投稿
2023 年度 HDU マルチスクールコンテスト ラウンド 5 完全解答
本稿では、2023 年に開催された HDU 主催の大学生向け競技プログラミング大会（マルチスクール）第 5 回の各問に対するアルゴリズム解説と参考実装を示します。
A. タイフーン接近距離
問題概要
n 個の点によって構成される折線があり、q 回のクエリにおいて指定された座標からこの折線までの最短距離を計算する必要がある。データサイズは n, q ≤ 10^4 程度である。
解 ...
6月22日 20:42 投稿
競技プログラミングにおけるアルゴリズム実装：SMU Autumn 2023 Round 4 解説
A. Access Denied：パスワードの推測と応答時間解析
この問題は、サーバーからの応答時間を利用してパスワードを推測する対話型の課題です。パスワードの最大長は20文字であり、推測した文字列の長さが正解と異なる場合、応答には5msの遅延が生じます。また、文字ごとの照合には9msの遅延が加算されるという仕組みを利用します。
まず、長さ1から20までの文字列を順次送 ...
6月21日 23:00 投稿
第14回 藍橋杯 C/C++ Bグループ 省大会 競技課題の解説と実装
1. 日付統計 (Date Statistics)
8桁の数値が並んだ100個のデータから、2023年に存在する有効な日付（YYYYMMDD形式）がいくつ作れるかをカウントする問題です。部分列として抽出する必要があるため、全探索や動的計画法でアプローチします。このコードは計算済みの結果を出力する例です。
#include <iostream>
int main() {
// 探索アルゴリズムによって算出され ...
6月9日 22:20 投稿
競技プログラミング問題精選: 考察技法と実装(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 投稿