競技プログラミング問題集の解法解説
問題一覧
A: StringGame (考察)
B: SequenceGame (貪欲法+二分探索)
C: 猫の世話 (幾何学、考察)
D: 数列H (数学)
E: キャンディーH (考察)
F: エンコーディング1.0 (動的計画法)
G: エンコーディング2.0 (深さ優先探索)
H: 迷路 (幅優先探索+二点探索)
I: レーティング (考察+優先度付きキュー)
J: 文字列変換 (総当り)
K: 新ゲーム! (計算幾何学+最短経路)
A: StringGa ...
8月7日 07:18 投稿
二分木の非再帰的走査
前順走査
前順走査では、ノードの値を「根 → 左の子 → 右の子」の順に処理します。
再帰的な実装
public void traverse(Node node) {
if (node == null) {
return;
}
System.out.println(node.value);
traverse(node.left);
traverse(node.right);
}
非再帰的な実装
非再帰では、スタックを使用してノードを管理します。根ノードを最初に処理 ...
8月4日 15:22 投稿
C言語でXOR演算子を使って、古き良きXORリストを実装する方法
XORリストの基本概念
XORリストは、各ノードが前後のノードのアドレスをXOR演算子を使って1つのポインタフィールドに格納する特別な連結リストです。これにより、通常の双方向リストで必要な2つのポインタ（前と次）の代わりに、1つのポインタフィールドで済むため、メモリ使用量を削減できます。
この手法の鍵となるのは、XOR演算子の性質です。AとBがポインタ（アドレス ...
8月4日 11:12 投稿
Pythonプログラミング基礎：制御構造、ファイル操作、データ型の変換と実践例
条件分岐とブール値の取り扱い
Pythonでは真偽値を表すためにTrueとFalse（英字の大文字始まる）を使用します。条件判断はif～elif～else構文で実現され、コードブロックの区切りはインデント（半角スペースまたはタブ）によって明示的に定義されます。
# ブール値の初期化
is_connected = True
if is_connected:
print("接続状態が有効です")
elif not is_connected: ...
8月4日 09:21 投稿
Javaプログラミングの実践的学習と課題解決
はじめに
本記事では、主に以下の重要な概念と技術について取り扱います。
クラスとオブジェクトの基本概念、コンストラクタ、アクセス修飾子、メンバ変数。
文字列入力と出力の処理方法、文字列の分割、結合、変換操作。
ループ、条件文、配列、リスト。
今回の課題は主にPTAの第7回問題セットと期末試験で構成されており、主に「成績管理システム2」と「3」、および一部 ...
8月3日 09:43 投稿
トライ木（Trie木）の基礎と応用
基本概念
トライ木（Trie木）は文字列に関連するデータ構造で、辞書木または接頭辞木とも呼ばれます。その主な思想は「空間で時間を換える」ことです。大量の文字列を統計、ソート、または保存するために使用できます。検索する文字列をsとすると、トライ木の単一クエリの複雑度はO(|s|)です。
01トライ木は、XOR関連問題を扱うデータ構造のバリエーションです。複数の数 ...
8月3日 03:10 投稿
PythonでTrie（接頭辞木）を実装する
問題 208：Trie（接頭辞木）の実装
Trie（トライ、発音は「トライ」に近い）または接頭辞木は、文字列のデータセットを効率的に保存および検索するための木構造データ構造です。このデータ構造は、オートコンプリートやスペルチェックなど、多くの応用シーンで使用されます。
以下の操作をサポートする Trie クラスを実装してください。
Trie() - 接頭辞木オブジェク ...
8月1日 06:51 投稿
eJOI競技プログラミング問題解説
eJOI（European Junior Olympiad in Informatics）の過去問から、いくつかの問題を解説します。
eJOI2017 A - Magic
問題概要
長さ\(n\)の文字列\(a\)が与えられ、使用される文字の種類数を\(|\Sigma|\)とします。部分文字列が「魔法的」であるとは、その部分文字列内に全ての種類の文字が少なくとも1回含まれ、かつ全ての種類の文字の出現回数が等しいことを意味します。 ...
8月1日 00:11 投稿
線形リストの基礎と実装：配列とリンクリストの比較
2.1 線形リストの定義と基本操作
2.1.1 線形リストの定義
線形リストとは、同一データ型を持つn個のデータ要素からなる有限の順序付き集合である。nを表の長さと呼び、n=0のとき空の線形リストとなる。線形リストをLとすると、一般的にL=(a1, a2, ..., an)と表される。
ここでa1は唯一の「最初」のデータ要素（先頭要素）、anは「最後」のデータ要素（末尾要素）である。 ...
7月31日 02:50 投稿
アルゴリズム学習ノート：C/C++基礎と基本的なアルゴリズム
1 C/C++の基礎知識
1.1 無限大の定義（INF）
整数型の無限大を表す定数の定義方法：
const int INF = 0x3f3f3f3f;
1.2 scanf関数の使い方
一般的なデータ型のscanfフォーマット指定子：
データ型フォーマット指定子
int%d
long long%lld
float%f
double%lf
char%c
文字列（char配列）%s
1.3 実用的な出力フォーマット
1.3.1 %md
%mdは、int型変数がm桁に満たない ...
7月30日 08:28 投稿