競技プログラミング問題集：文字列処理、ゲーム理論、データ構造、グラフ理論
問題1：文字列処理 - 文字と数字の間に空白を挿入
文書内の隣接する英字と数字の間に空白を追加する問題である。文書の最初と最後の文字は空白ではないことが保証されている。
getlineを用いて1行全体を読み込み、文字を順に走査しながら条件に合わせて空白を挿入する。
実装コード
#include <iostream>
#include <string>
#include <cctype>
using ...
9月6日 19:39 投稿
2023ACM夏合宿 Day5 モノトーンキューとモノトーンスタック
目次- DAY 5 モノトーンキュー/スタック
トレーニング概要
A問題
B問題
C問題
D問題
E問題 未解決、解説補完
F問題 未解決、解説補完
G問題 CFデータでWAのヒントを得る
J問題
K問題
L問題
補足情報
モノトーンスタック
モノトーンスタック
矩形関連
辞書順最小
貢献度法
モノトーンキュー
DAY 5 モノトーンキュー/スタック
トレーニングリンク：リンク
トレーニング ...
8月26日 19:16 投稿
AtCoder ABC369 のアルゴリズム解説
A. 369
整数 $C$ が存在して $A, B, C$ が等差数列となる条件は、$A+B$ が偶数であることです（$C = (A+B)/2$ が整数であることと同値）。特別な場合として、$A=B$ であれば数列の長さは1となるため、答えは1です。それ以外の場合、$A+B$ が偶数ならば $A$ と $B$ の間に整数が1つ、$A$ と $B$ の外側に整数が1つずつ存在するため、選択肢は3つになります。奇数の場合は $A ...
8月22日 09:01 投稿
フェニック木の設計と応用
高頻度で単一点の更新と範囲合計の取得が必要なシステムにおいて、従来の配列構造は計算量の問題から実用性に欠ける。この課題を解決するため、Peter Fenwickによって提案されたフェニック木（Binary Indexed Tree）は、効率的な範囲演算を実現するデータ構造である。
基本概念と構造
フェニック木では各ノードが特定の区間の情報を保持し、二進数のビット演算を利用して ...
8月15日 03:42 投稿
Wdoi R2 プログラミングコンテスト問題解法
本記事では、プログラミングコンテスト「Wdoi R2」の問題に対する解法を解説します。各問題の戦略と実装の詳細について見ていきましょう。
問題 A: 幻の如く咲く花
解法
配列に対する操作は「要素の反転」と「整数値の加算」の2種類です。配列を反転させる操作は、最大でも1回行えば十分です。なぜなら、2回反転させると元に戻るためです。したがって、反転操作を行う場合 ...
8月7日 20:25 投稿
栈データ構造を用いた文字列の検証と数式評価の実装
LeetCode 20. 有効な括弧 (Valid Parentheses)
スタック（Stack）はLIFO（後入れ先出し）の特性を持つため、括弧の対称性チェックのようなネスト構造の検証に適しています。実装の際は、不一致が発生するすべてのエッジケースを事前に分析することが重要です。
アルゴリズムのアプローチとして、左括弧が現れた際に、対応する「期待される右括弧」をスタックにプッシュする ...
8月3日 23:58 投稿
アルゴリズム実践トレーニングカリキュラム
配列操作編
二分探索と要素削除
二分探索：境界条件の2つの実装方法に注意。rightの定義、if条件と境界更新ロジックが重要。
左閉右閉左閉右開
rightの定義len(arr) - 1len(arr)
ループ条件while left <= right:while left < right:
境界更新right = mid - 1right = mid
class Solution:
def binary_search(self, arr: List[int], target: int) -> int:
...
6月26日 18:36 投稿
2023 年度 HDU マルチスクールコンテスト ラウンド 5 完全解答
本稿では、2023 年に開催された HDU 主催の大学生向け競技プログラミング大会（マルチスクール）第 5 回の各問に対するアルゴリズム解説と参考実装を示します。
A. タイフーン接近距離
問題概要
n 個の点によって構成される折線があり、q 回のクエリにおいて指定された座標からこの折線までの最短距離を計算する必要がある。データサイズは n, q ≤ 10^4 程度である。
解 ...
6月22日 20:42 投稿
Codeforces Round #1058 (Div. 2) 問題解説
A - MEX Partition
この問題の核心は、配列全体のMEX（Minimum Excluded Value）を求めることに帰着します。与えられた配列 $A$ をいくつかの部分集合に分割し、そのすべての部分集合のMEXが等しくなるための条件を考えます。
$A$ のMEXを $m$ とします。$m$ は $A$ に含まれない最小の非負整数であるため、$m$ より大きい要素は各部分集合のMEX計算において無視できま ...
6月21日 21:20 投稿
AtCoder Beginner Contest 366 の問題解説と実装
はじめに
今回のコンテストでは問題Eに大部分の時間を費やすことになり、残り15分でようやく正解にたどり着くという危ない場面でした。緑色レベルの問題にも苦戦するようでは、まだまだ実力不足を感じます。
A - Election 2
高橋君と青木君のどちらかが過半数の票を獲得したかどうかを判定するシンプルな問題です。
#include <iostream>
using namespace std; ...
6月4日 17:22 投稿