PythonでTrie（接頭辞木）を実装する
問題 208：Trie（接頭辞木）の実装
Trie（トライ、発音は「トライ」に近い）または接頭辞木は、文字列のデータセットを効率的に保存および検索するための木構造データ構造です。このデータ構造は、オートコンプリートやスペルチェックなど、多くの応用シーンで使用されます。
以下の操作をサポートする Trie クラスを実装してください。
Trie() - 接頭辞木オブジェク ...
8月1日 06:51 投稿
バックトラック法を用いた組み合わせ合計問題の解法
39. 組み合わせ合計問題（重複選択可）
整数配列candidatesと目標値targetが与えられたとき、配列要素の和がtargetとなる全てのユニークな組み合わせを返します。各要素は無制限に再利用可能です。
入力例: candidates = [2,3,6,7], target = 7
出力例: [[2,2,3],[7]]
解法ポイント:
要素の重複使用を許可するため、再帰呼び出し時にインデックスを進めない
枝刈り処 ...
8月1日 05:05 投稿
eJOI競技プログラミング問題解説
eJOI（European Junior Olympiad in Informatics）の過去問から、いくつかの問題を解説します。
eJOI2017 A - Magic
問題概要
長さ\(n\)の文字列\(a\)が与えられ、使用される文字の種類数を\(|\Sigma|\)とします。部分文字列が「魔法的」であるとは、その部分文字列内に全ての種類の文字が少なくとも1回含まれ、かつ全ての種類の文字の出現回数が等しいことを意味します。 ...
8月1日 00:11 投稿
二つのソート済み配列の中央値を二分探索で求める方法
問題の理解
二つのソート済み配列が与えられた場合、全体の中央値を効率的に見つける必要があります。単純な方法では両方の配列をマージしてから中央値を計算できますが、これではO(m+n)の時間計算量が必要です。より効率的な解法として、二分探索を用いることでO(log(min(m,n)))の時間計算量で解くことができます。
アルゴリズムの考え方
二つの配列から、左半分の要素数 ...
7月31日 01:06 投稿
動的計画法の基礎：バックパック問題の完全解説
動的計画法の基礎：バックパック問題の完全解説
バックパック問題は動的計画法（DP）の最も古典的で基礎的な問題の一つです。多くのアルゴリズム学習者の「必修科目」とも言えるこの問題は、見た目は単純（バックパックに荷物を詰めて価値を最大化する）ですが、01バックパック、完全バックパック、多重バックパックなど多くのバリエーションに派生し、DPの核心思想が体系 ...
7月30日 16:50 投稿
C++スネークゲームにおける衝突判定と成長処理の実装
スネークゲームの根幹となる衝突判定と、蛇が成長する仕組みについて解説する。ここでは、蛇が壁や自身に衝突した場合の判定と、食べ物を摂取した際の体節追加処理を実装していく。
衝突判定を実装するにあたり、蛇の頭部が次に進む座標をあらかじめ計算し、その座標に存在するオブジェクトの種類を調べる手法をとる。この次座標の計算処理を再利用可能にするため、Serpent ...
7月30日 08:57 投稿
アルゴリズム学習ノート：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 投稿
アルゴリズム競技問題集：動的計画法とデータ構造の応用
問題A：連続要素の除去
この問題では、与えられたシーケンスから連続する重複要素を除去する必要があります。
解法：連続する同じ要素を1つにまとめることで、シーケンスの長さを最小化します。
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
void process() {
int elements;
cin >> elements;
...
7月29日 16:55 投稿
鋳造炉の容量制約下における最大耐久性の動的計画法
問題定義
特殊な錬成炉を用いて伝説の武器を鍛造する際、計 N 種類の素材を準備します。各素材 i には固有の強度パラメータ A[i] が割り当てられています。錬成規則により、素材は番号順（1 から N まで）に厳密に投入しなければなりません。
炉の容量は最大 W 個の素材までです。ここで重要な操作制限として、新しい素材を投入する直前 に限り、炉内に保管されている素材 ...
7月28日 19:24 投稿
キューを用いた二分木の階層順探索手法
問題定義
二分木の根ノードを入力として、階層順（レベル順）にノード値を探索するアルゴリズムを実装します（各レベルでは左から右へ順にアクセス）。
解法アプローチ
標準的な手法として、キューを用いた幅優先探索（BFS）を適用します。
キューで各階層のノードを管理
各反復処理で現在のキューサイズを取得（現在階層のノード数）
ノードをデキューし、値を記 ...
7月28日 01:04 投稿