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 投稿
プログラミング問題解法集
可能な限り簡潔にします。
CF679E
直接代入と修正のタイミングが正しいことがわかりますので、書き方について説明します。区間を良い数に変える操作を「加算」と呼びます。
既に区間代入が行われた区間にUpというマークを付けると、その区間とその子区間は1つの点と見なせます。そのため、修正の複雑さは単点修正と同じになります。
したがって、加算操作は次のように記述 ...
6月21日 23:23 投稿
C++における二分探索木の実装と操作
二分探索木とは
二分探索木（Binary Search Tree: BST）は、以下の条件を満たす二分木構造です：
左部分木に含まれるノードの値は、常に親ノードの値より小さい
右部分木に含まれるノードの値は、常に親ノードの値より大きい
左右の部分木もまた二分探索木を満たす
基本操作
探索（Search）
探索操作は以下のように行われます：
ルートノードから比較を開始します
探索 ...
5月30日 20:39 投稿