異端開発室

eJOI（European Junior Olympiad in Informatics）の過去問から、いくつかの問題を解説します。 eJOI2017 A - Magic 問題概要 長さ\(n\)の文字列\(a\)が与えられ、使用される文字の種類数を\(|\Sigma|\)とします。部分文字列が「魔法的」であるとは、その部分文字列内に全ての種類の文字が少なくとも1回含まれ、かつ全ての種類の文字の出現回数が等しいことを意味します。 ...

Dijkstra法はグラフ理論において単一始点最短経路問題を解決するための代表的なアルゴリズムです。非負重み付きグラフの最短経路計算に特化したこのアルゴリズムは、貪欲法の一種として分類されます。 アルゴリズム概要 適用範囲: 非負重み付き有向グラフ/無向グラフにおける最短経路探索 計算量: 隣接行列実装の場合O(V²)、優先度付きキュー使用でO((E+V)logV) 特徴 ...

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 ...

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 ...

問題概要 複数のアカウント情報が「名前, メール1, メール2, …」という形式で与えられる。同一人物のアカウントは少なくとも1つのメールアドレスが共通しているため、それらを1つにまとめて返却せよ。 Union-Findを用いた解法 「共通のメールアドレスを持つアカウントは同一人物」という条件は、「同一要素を含む集合をすべて結合」というUnion-Findの典型的な利用シーン ...

木の直径（Tree Diameter）とは、木構造グラフにおいて最も離れた2つのノード間の距離を指します。この計算には、主に深さ優先探索（DFS）を2回行う方法と、動的計画法（DP）を用いる方法の2つが広く知られています。本記事では、それぞれのアルゴリズムの原理と実装手法について解説します。 DFSによる2回の探索アプローチ この手法は非常に直感的で、計算量も効率的です ...

説明 石切りバサミは一般的なジャンケンゲームです：石はハサミを勝ち、ハサミは布を勝ち、布は石を勝ちます。二人が同じ手を出した場合、勝敗はありません。『ライフ・オブ・ザ・ビーチ』第2シーズン第8話で登場したアップグレード版のジャンケンゲームでは、この伝統的なジャンケンゲームに二つの新しいジェスチャーが追加されました： スポック：『スターゲート・ドライ ...

基本的な比較計算 二つの整数の積を比較する問題では、直接的な計算を用いる。 #include <iostream> int main() { long long w, x, y, z; std::cin >> w >> x >> y >> z; std::cout numA >> numB; std::cout 1) isCritical[node] = true; } int main() { int cols; cin >> cols; string rowA, rowB; cin >> rowA >> rowB; i ...

ネットワーク最大流問題は、有向グラフ上で容量制限付きの辺を持つネットワークにおいて、ソース（始点）からシンク（終点）へ送ることのできる最大流量を求める古典的な最適化問題である。この問題は二部マッチングや資源配分など多くの応用に利用される。 基本概念 フローネットワーク：ソース s とシンク t を持つ有向グラフ。s からは流出のみ、t へは流入のみが許 ...

区間交差関係に基づく最小全域木構築 与えられた区間集合において、交差する区間同士を結ぶ辺の重みを権重の差とし、生成されるグラフの最小全域木を求める問題。辺を全列挙すると計算量が爆発するため、幾何学的性質と貪欲戦略を組み合わせる。権重が小さい区間から順にアクティブな集合に追加し、各区間の挿入・削除タイミング（スライン法）において、権重でソートされ ...