C++を用いた配列操作：最大値除外、平均算出、配列比較の実装手法
最大値と異なる数値の総和を求める
与えられた整数列の中から最大値を特定し、その最大値と一致しない要素のみを抽出して合計を算出するプログラムの実装です。
実装コード
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int elementCount;
if (!(std::cin >> elementCount)) return 0;
std::vector&l ...
5月30日 15:39 投稿
スライディングウィンドウの最大値を求めるアルゴリズム
スライディングウィンドウ問題において、各ウィンドウ内の最大値を効率的に求めるには、双方向キュー（deque）を活用した単調キューというデータ構造が有効である。このアプローチにより、O(n)の時間計算量で解を導出できる。
双方向キューの特性と選択理由
通常のキュー（queue）は、要素の追加が末尾から、取り出しが先頭からのみ可能である。一方、双方向キュー（deq ...
5月29日 23:52 投稿
コーディングテスト演習（一）——Codeforces 784B Santa Claus and Keyboard Check
はじめに
最近、コーディングテストの準備をしており、練習問題をまとめています。 元々はC言語の経験しかありませんでしたが、実際に使用会发现C++の方がテストに向いています。ライブラリ関数も豊富で、より多くの操作をサポートでき、コードを簡潔に記述できます。 例えば、C言語で文字列を定義するにはchar s[1000]が必要ですが、C++ではstring sだけで済みます。
問 ...
5月29日 16:25 投稿
二分探索木の有効性検証：中間順走査によるアプローチ
問題の概要
二分探索木（BST）が有効であるかどうかを判定するには、各ノードが以下の条件を満たしているかを確認する必要があります。
ノードの左部分木に含まれるすべての値は、そのノードの値より厳密に小さい。
ノードの右部分木に含まれるすべての値は、そのノードの値より厳密に大きい。
左右の部分木もそれぞれ二分探索木でなければならない。
これを効率的にチェ ...
5月29日 04:49 投稿
最小部分文字列の探索：スライディングウィンドウ手法の実装
問題定義
2つの文字列 s と t が与えられた場合、s 内の部分文字列の中で、t のすべての文字（重複を含む）を含む最小の長さを持つものを見つけます。該当する部分文字列が存在しない場合は空文字列を返します。
この問題は、スライディングウィンドウ（Sliding Window）アルゴリズムの典型例です。左右2つのポインタを用いてウィンドウの範囲を動的に管理することで、効率 ...
5月29日 02:43 投稿
FHQ-Treapの詳細と実装：分割と併合によるランダム化平衡二分探索木
FHQ-Treap（または無旋Treap）は、ノードの回転操作を行わずに「分割」と「併合」という2つのプリミティブな操作のみを用いてバランスを維持する二分探索木です。このデータ構造は、各ノードに「値」と「ランダムな優先度」を持たせます。値は二分探索木の性質（左の子 < 親 < 右の子）を満たし、優先度はヒープの性質（親が子よりも高い優先度を持つ）を満たすよう ...
5月26日 10:16 投稿
単調スタックの活用術と代表的なアルゴリズム問題
単調スタックの基本概念
単調スタック（Monotonic Stack）は、スタック内の要素が常に単調増加、または単調減少の順序を保つように維持するデータ構造です。この特性を利用することで、配列内の各要素に対して「左側または右側で最も近い、より大きい（または小さい）要素」を効率的に探索することができます。
典型的な応用としては、以下の 4 つのパターンがあります。
...
5月25日 20:41 投稿
C言語プログラミング課題：関数とアルゴリズムの実装演習
1. スコア判定プログラム
成績評価を行う関数を実装します。switch文を利用してスコアの階級分けを行います。
#include <stdio.h>
char get_grade(int score) {
switch (score / 10) {
case 10: case 9: return 'A';
case 8: return 'B';
case 7: return 'C';
case 6: return 'D';
default: return 'F';
}
}
int ...
5月23日 17:15 投稿
ハッシュテーブルの実装とアルゴリズム応用：基礎から競技プログラミング問題への適用まで
ハッシュテーブルの仕組みと実装
基本構造の構築
ハッシュ値の生成手法は一旦置き、ハッシュ値が外部から与えられる前提でハッシュテーブルの骨組みを実装する。内部では配列と連結リストを用いてキーと値のペアを管理する。
public class CustomHashMap {
static class Node {
int code;
Object key;
Object val;
Node next;
...
5月20日 12:47 投稿
スプレイ木（Splay Tree）の実装詳細と拡張機能解説
スプレイ木の概要
スプレイ木は、動的データ構造の一種であり、二叉探索木のバランスを保つための手法です。Daniel Sleator と Robert Tarjan によって提案されました。その特徴として、明示的なバランス操作を行わずとも、アクセスパターンの履歴に基づいて自動的に調整が行われる点が挙げられます。
この構造では、最近参照された要素を根へと移動させる「スプレイ」操作 ...
5月20日 12:22 投稿