P4175 [CTSC2008]ネットワーク管理 解説
問題概要
ノード数が $ n $ の木が与えられ、各ノードには重み $ w_i $ が割り当てられている。$ q $ 個の操作を行う：
0 u v：ノード $ u $ の重みを $ v $ に変更する。
k u v：ノード $ u $ から $ v $ へのパス上の重みの第 $ k $ 番目の大きい値を求める。パス上にノードが $ k $ 個未満ある場合、invalid request! を出力する。
制約
$ 1 \le n, q \le 8 \cdot 10 ...
8月20日 16:41 投稿
ツリーの重軽分解：長子優先によるパス操作の高速化
セグメント木は、配列上の区間和や最大値などの情報を効率的に管理するためのデータ構造であり、クエリや更新を \(O(\log n)\) で処理できる。しかし、問題が「配列」ではなく「木構造」に拡張され、任意の2ノード間のパス上の情報を維持・操作したい場合、単純にセグメント木を適用することはできない。
木上のパスを線形構造に変換するアイデア
木は分岐構造を持つため ...
8月19日 04:01 投稿
2022 ICPC アジア西安地区大会 問題解説と実装アプローチ
C. Clone Ranran
本問題は、自身のクローンを作成する時間と、問題を作成する時間のバランスを取って最小の総時間を求めるものです。
クローンを作成する回数を全探索します。クローンを作成するたびに人数は2倍になるため、対数オーダーの探索で済みます。各ステップにおいて、必要な問題数を現在の人数で割ったもの（切り上げ）を作成時間に乗算し、クローン作成時間と合 ...
8月18日 14:40 投稿
等比数列の効率的計算と木構造処理
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)$で割ることで最終的な合計値を得ます。
以下に数式を示し ...
8月15日 17:07 投稿
2025 XCPC浙江省競技プログラミングコンテスト FLM問題解説
F. Challenge NPC III
多起点最短経路と第二最短経路問題。
同じ色の頂点に対してBFSを実行し、各経路の起点を維持します。同じ色の頂点から自身への経路が最短であるため、最終的に第二最短経路がkより小さいかを判定すれば十分です。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n, m, k;
cin >> ...
8月1日 18:35 投稿
二分探索木の検証アルゴリズム
問題概要
二分探索木の妥当性を判定する問題です。与えられた二分木のルートノードから、その木が二分探索木の条件を満たしているかどうかを確認します。
二分探索木の定義：
任意のノードの左部分木に含まれる値は、そのノードの値より小さい
任意のノードの右部分木に含まれる値は、そのノードの値より大きい
左右の部分木もそれぞれ二分探索木である
実行例
例1：
...
7月16日 16:02 投稿
木の直径を求める2つの主要アプローチ
木の直径（Tree Diameter）とは、木構造グラフにおいて最も離れた2つのノード間の距離を指します。この計算には、主に深さ優先探索（DFS）を2回行う方法と、動的計画法（DP）を用いる方法の2つが広く知られています。本記事では、それぞれのアルゴリズムの原理と実装手法について解説します。
DFSによる2回の探索アプローチ
この手法は非常に直感的で、計算量も効率的です ...
7月14日 23:27 投稿
重み付き木の分割処理
木構造の分割処理
基本概念
木の分割処理：木構造を複数の非交差チェーンに分割する手法で、主に重み付きチェーン分割を用いる。以下の操作をサポート：
ノードxからノードyまでの最短経路上の全ノードの値の更新
ノードxからノードyまでの最短経路上の全ノード値の合計取得
ノードxとその部分木の値の更新
ノードxとその部分木の値の合計取得
重み付き子ノード：ノ ...
7月11日 23:30 投稿
牛客週間コンテスト 第5回
牛客週間コンテスト 第5回
A-游游の文字変換
#include <iostream>
#include <string>
using namespace std;
int main() {
string input;
cin >> input;
for (size_t i = 0; i < input.length(); ++i) {
char current = input[i];
if (current >= 'A' && current < 'Z') {
input[i] = cu ...
7月1日 00:04 投稿
Pythonにおける木構造の実装と応用
Pythonにおける木構造の実装と応用
木構造の基本概念
木構造は階層的な関係を模倣するデータ構造で、各要素はノードと呼ばれます。木の各ノードはゼロ個以上の子ノードを持つことができますが、各ノードは親ノードを一つしか持たない、という特徴があります。ルートノードだけは親ノードを持たない例外です。木構造の重要な特性は、循環がないことです。つまり、あるノー ...
6月24日 16:08 投稿