異端開発室

100. 島の最大面積 与えられた1（陸地）と0（水）からなる行列において、島の最大面積を計算します。島は水平または垂直方向に隣接する陸地で構成され、周囲が水で囲まれているものとします。 from collections import deque def max_area_of_island(grid): rows, cols = len(grid), len(grid[0]) max_area = 0 for i in range(rows): for j in ...

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

グラフ理論において、無向グラフの構造を分析する重要な概念として関節点、橋、二重連結成分があります。これらの概念はグラフの連結性を評価し、グラフの脆弱性を特定するために不可欠です。 関節点 (Articulation Points) 概要 無向グラフから特定の頂点を削除した後、グラフの連結成分の数が増加する場合、その頂点は関節点と呼ばれます。関節点はグラフの連結性を維 ...

問題概要 ジョン農場主が町長に選出されました！彼の選挙公約の一つは、町全体にインターネットを導入し、すべての農場を接続することです。もちろん、彼はあなたの助けが必要です。 ジョンはすでに自身の農場に高速ネットワーク回線を設置済みであり、これを他の農場と共有したいと考えています。費用を最小限に抑えるため、すべての農場を接続する最短の光ファイバーを ...

L1-1 挨拶出力 解法 指定されたテキストをそのまま出力する。 実装例 #include <iostream> using namespace std; int main() { cout << "ありがとう！\\(>_<)/" << endl; return 0; } L1-2 平均速度計算 実装例 #include <iostream> #include <iomanip> using namespace std; int main() { int distance, time; cin & ...

グラフ理論：K値の最大化問題 - 二分探索とシミュレーションによる解法 問題文 n個の頂点とm辺の単純無向グラフが与えられます。このグラフを完全グラフに補完する必要があります。補完のルールは、あらかじめパラメータKを選び、各ステップで「頂点uとvの間に辺が存在せず、かつ両頂点の次数の和がK以上」である辺のみを追加することです。このルールに従って辺を追加し ...

A. 牛牛吃米粒 入力: 整数 n, k と符号なし整数 s、および k 個の位置 a_i。各ビット位置が制限されていないか検証し、s のビットが立っている位置が禁止領域と重なる場合は "NO"、それ以外は "YES" を出力。 #include <iostream> #include <vector> using namespace std; int main() { unsigned long long s; int n, k; cin >> n >> k; vect ...

文字列連結 2つの文字列を入力として受け取り、連結して出力します。空白を含む可能性があるため、getline関数を使用します。 #include <iostream> #include <string> using namespace std; int main() { string a, b; getline(cin, a); getline(cin, b); cout << a + b; return 0; } 最小差分値 整数配列内の隣接要素間の最小差 ...

基本原理： 深さ優先探索は、開始ノードから出発し、一つの分岐を深く進み続けます。葉ノードまたは進めなくなったノードに到達するまで探索を続けます。 探索が葉ノードまたは進めなくなったノードに到達した場合、未探索の前のノードに戻り、他の分岐の探索を続けます。 既に訪問したノードをマークすることで、同じ経路での重複訪問を避けます。 DFSアルゴリズムのス ...

配列内要素の隣接関係判定 与えられた配列において、特定の2つの要素xとyが隣接しているかどうかを判定する問題です。 #include<iostream> #include<vector> using namespace std; bool checkAdjacent(vector<int>& arr, int target1, int target2) { int n = arr.size(); for(int i = 0; i < n; i++) { if(arr[i] == target1) { ...