競技プログラミングにおけるグラフ理論・組合せ数学・動的計画法の応用テクニック
弦なし閉路の検出と辺グラフ変換
長さ4以上の弦なし閉路を検出する問題では、頂点ベースの探索ではなく辺をノードとする線グラフへの変換が有効である。有向辺 $(u \to v)$ と $(v \to w)$ の間に、辺 $(u, w)$ が存在しない場合にのみ有向辺を張る。この変換により、元のグラフにおける三角形は新グラフで閉路を形成しなくなる。新グラフ上でDFSを実行し、最も深い返祖辺 ...
9月14日 12:35 投稿
AtCoder Beginner Contest 266 問題A-G 解説
A - Middle Letter
奇数長の文字列が与えられるので、その中央の文字を出力します。
#include <iostream>
#include <string>
#include <vector>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::string input_str;
std::cin >> input_str;
// 0-indexedなので、長さLの文字列の中央は L/2
...
9月13日 12:05 投稿
強連通成分を利用したギフト再分配問題の解法
この問題は、各人が持っているギフトを特定のルールに基づいて交換し、最終的に各人がどのギフトを受け取れるかを決定するものです。
各人は、自分自身と、自分より左側にいる人たちのギフトを受け取ることができます。具体的には、各行の初期ギフト配置において、そのギフトを右隣のギフトと結びつける一方向のエッジを考えます。
このグラフ構造において、各ノード（人） ...
9月12日 03:37 投稿
グリッド迷路での最適経路探索
問題概要
n×m のグリッドからなる迷路を考えます。各セル (i, j) には方向指示 di,j と重み vi,j が設定されています。プレイヤーは初期位置 (sx, sy) から左足で踏み込み、その時点で vsx,sy を加算し、セルの重みを -vsx,sy に反転させます。
その後、各ステップで以下の選択肢があります：
ゲームを終了し、現在のスコアを最終スコアとする
現在のセルの方向指示に従 ...
8月31日 20:47 投稿
Dijkstra法の簡潔実装：配列ベースの優先度付き探索
重み付き有向グラフにおいて、特定の始点から各頂点への最短距離を求める単一始点最短経路問題。ここでは、隣接行列を入力とし、優先度付きキューを用いたDijkstra法の実装を示す。構造体を使わず、配列とペアのみで構成する。
入力仕様
1行目に頂点数 n と始点番号 s を指定する。続く n 行の各行に n 個の整数を並べ、隣接行列を表現する。行列の要素が正の整数の場合、 ...
8月15日 12:41 投稿
eJOI競技プログラミング問題解説
eJOI（European Junior Olympiad in Informatics）の過去問から、いくつかの問題を解説します。
eJOI2017 A - Magic
問題概要
長さ\(n\)の文字列\(a\)が与えられ、使用される文字の種類数を\(|\Sigma|\)とします。部分文字列が「魔法的」であるとは、その部分文字列内に全ての種類の文字が少なくとも1回含まれ、かつ全ての種類の文字の出現回数が等しいことを意味します。 ...
8月1日 00:11 投稿
Dijkstra法による最短経路探索
Dijkstra法はグラフ理論において単一始点最短経路問題を解決するための代表的なアルゴリズムです。非負重み付きグラフの最短経路計算に特化したこのアルゴリズムは、貪欲法の一種として分類されます。
アルゴリズム概要
適用範囲: 非負重み付き有向グラフ/無向グラフにおける最短経路探索
計算量: 隣接行列実装の場合O(V²)、優先度付きキュー使用でO((E+V)logV)
特徴 ...
7月21日 01:28 投稿
SMU Summer 2024 Contest Round 5
SMU Summer 2024 Contest Round 5
ロボット高橋君
思考プロセス
重み (W_i) でソートし、前後の 1 と 0 の個数を計算します。答えはおおよそ (\max(ans,pre_i+suf_{i+1})) の形式になります。
ソート後、(W_i = W_{i+1}) の場合、i と i+1 の間で分割できないため特別な処理が必要です。
コード
#include <iostream>
#include <vector>
#include <algorithm ...
7月20日 17:48 投稿
AtCoderコンテスト445の解法解説
D - チョコレートの再構築
この問題は比較的単純な実装問題です。チョコレートの配置を再構築するアルゴリズムを示します。
struct Chocolate {
int height;
int width;
int id;
};
bool compareWidth(const Chocolate &a, const Chocolate &b) {
return a.width > b.width;
}
bool compareHeight(const Chocolate &a, const Chocolate &b) {
ret ...
7月17日 20:13 投稿
アカウントのメールアドレスを統合するUnion-Findアプローチ
問題概要
複数のアカウント情報が「名前, メール1, メール2, …」という形式で与えられる。同一人物のアカウントは少なくとも1つのメールアドレスが共通しているため、それらを1つにまとめて返却せよ。
Union-Findを用いた解法
「共通のメールアドレスを持つアカウントは同一人物」という条件は、「同一要素を含む集合をすべて結合」というUnion-Findの典型的な利用シーン ...
7月16日 21:36 投稿