異端開発室

T1: 等比数列の合計計算 数列$ \sum_{i=1}^n x^i $を効率的に求めます。この問題ではx進法の特性を利用した新しいアプローチを採用しました。 変数Pを$x^1 + x^2 + ... + x^n$と定義すると、x進法で表現する際は連続する1の並びになります。この性質を活かし、$Q = x^{m+1}$のx進法表現から$Q-1$を導出し、$(x-1)$で割ることで最終的な合計値を得ます。 以下に数式を示し ...

E - 数字の和で割り切れる数 この問題では、与えられた正整数 \(N\) 以下の自然数のうち、その桁の和で割った余りが 0 となる数を求める必要があります。 通常の桁 DP では、剰余を状態として維持するのは容易ですが、今回のように「剰元の基準（桁の和）」自体が変化する場合、直接的な DP では困難になります。そこで、桁の和（モジュロ）を先に見積もるアプローチを取 ...

F. Challenge NPC III 多起点最短経路と第二最短経路問題。 同じ色の頂点に対してBFSを実行し、各経路の起点を維持します。同じ色の頂点から自身への経路が最短であるため、最終的に第二最短経路がkより小さいかを判定すれば十分です。 #include <bits/stdc++.h> using namespace std; using i64 = long long; void solve() { int n, m, k; cin >> ...

华为 OD 机试：亲子游戏 问题描述 母親と赤ちゃんが参加する親子ゲームがあります。N×N の2次元グリッドマップ上で、母親と赤ちゃん的位置を决めます。各セルには異なる数のキャンディーが入っており、一部のセルには障害物があります。 ゲームルールは、母親が最短時間で赤ちゃんの位置に到達する必要があります（各单位時間には1マスだけ移动できます）。道沿いのすべて ...

素集合データ構造 (Union-Find) 素集合データ構造（Disjoint Set Union, DSU）は、要素がどのグループに属するかを管理し、グループの統合と判定を効率的に行うための木構造ベースのデータ構造です。 主要な操作 find: ある要素がどのグループ（代表元）に属するかを特定する。 unite: 二つのグループを一つに統合する。 経路圧縮の実装 検索時に再帰的に親を辿り、直 ...

問題A: ゲームの点数計算 木青チームと高橋チームの点数をそれぞれ計算し、木青チームの総得点が高橋チームより1点多くなるようにします。 コード例 #include <iostream> #include <vector> int main() { int score_gq = 0, score_mq = 0; int input; // 木青チームの9つの点数を入力 for (int i = 0; i < 9; ++i) { std::cin >> i ...

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

問題 2612. 最小反転操作回数 整数 n と、範囲 [0, n - 1] 内の整数 p が与えられます。これらは、長さが n でインデックスが 0 から始まる配列 arr を表します。この配列では、インデックス p の位置だけが 1 で、他のすべての要素は 0 です。 同時に、整数配列 banned も与えられます。この配列には、配列内のいくつかの位置が含まれています。banned の第 i 個 ...

問題概要 n×nのサイズの迷路があり、各セルには0または1が書かれています。現在位置が0の場合、上下左右の隣接する4つのセルのうち1のセルに移動できます。同様に、現在位置が1の場合は、隣接する0のセルに移動可能です。この迷路に対して、指定された開始位置から移動可能なセルの総数（開始位置を含む）を求める問題です。 入力形式 1行目：正整数 n, m（迷路のサイズと ...

幅優先探索（BFS）は、始点から順に隣接ノードを訪問し、各レベルのノードをすべて処理してから次の深さへ進むアルゴリズムです。この手法は、グリッド上の連結領域の数え上げや迷路における最短ステップ数の算出に適しています。 1のブロック数をカウントする例 #include <iostream> #include <queue> using namespace std; const int SIZE = 100; int rows ...