樹形動的計画法の典型アルゴリズムと問題解説
二分リンゴの木 (Binary Apple Tree)
この問題は「樹上ナップサック」の典型例です。木の枝に重みが付いており、保持する枝の数を制限したときの最大価値を求めます。
状態定義:
dp[u][j] : 頂点 u を根とする部分木において、j 本の枝を残したときの最大価値。
遷移式:
dp[u][j] = max(dp[u][j], dp[u][j - k - 1] + dp[v][k] + edge_weight)
ここで v は u の子、k は子 ...
10月20日 15:44 投稿
競技プログラミング問題集：文字列処理、ゲーム理論、データ構造、グラフ理論
問題1：文字列処理 - 文字と数字の間に空白を挿入
文書内の隣接する英字と数字の間に空白を追加する問題である。文書の最初と最後の文字は空白ではないことが保証されている。
getlineを用いて1行全体を読み込み、文字を順に走査しながら条件に合わせて空白を挿入する。
実装コード
#include <iostream>
#include <string>
#include <cctype>
using ...
9月6日 19:39 投稿
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 投稿
Wdoi R2 プログラミングコンテスト問題解法
本記事では、プログラミングコンテスト「Wdoi R2」の問題に対する解法を解説します。各問題の戦略と実装の詳細について見ていきましょう。
問題 A: 幻の如く咲く花
解法
配列に対する操作は「要素の反転」と「整数値の加算」の2種類です。配列を反転させる操作は、最大でも1回行えば十分です。なぜなら、2回反転させると元に戻るためです。したがって、反転操作を行う場合 ...
8月7日 20:25 投稿
プログラミングコンテスト初級：典型問題の実装パターン
問題1：文字列の反復生成
文字 'L'、'o' を N 回繰り返した文字列、そして "ng" を連結して出力する問題です。ループを使用せず、文字列コンストラクタを活用することで簡潔に記述できます。
#include <iostream>
#include <string>
int main() {
int repeat;
std::cin >> repeat;
std::string result = "L" + std::string(repeat, 'o') + ...
7月17日 16:04 投稿
AtCoder Beginner Contest 357 における A から D 問題の解法解説
問題A: Sanitizer
N人の人が順番に手を消毒します。各人が必要とする消毒液の量 $H_i$ が与えられ、合計 $M$ 単位の消毒液があるとき、何人目までが完全に手を消毒できるかを求める問題です。
実装としては、配列に格納された各 $H_i$ を順に累積し、その合計が $M$ を超えた時点のインデックスを確認します。累積和が $M$ を超えない場合は、全員が消毒可能です。
#inclu ...
7月1日 16:24 投稿
2023 年度 HDU マルチスクールコンテスト ラウンド 5 完全解答
本稿では、2023 年に開催された HDU 主催の大学生向け競技プログラミング大会（マルチスクール）第 5 回の各問に対するアルゴリズム解説と参考実装を示します。
A. タイフーン接近距離
問題概要
n 個の点によって構成される折線があり、q 回のクエリにおいて指定された座標からこの折線までの最短距離を計算する必要がある。データサイズは n, q ≤ 10^4 程度である。
解 ...
6月22日 20:42 投稿
Codeforces Round 999 合併部門における競技プログラミング問題の解説
A - 数列の並べ替えとスコア最適化
長さ n の整数列 a が与えられる。初期値が 0 の変数 s に対して、a の要素を順に加算する。s が偶数になった場合、ポイントを 1 加算した上で s を 2 で割った余り（つまり s % 2）に更新する。この操作を繰り返す中で、得られるポイントの合計を最大化するために、a の要素をどのように並び替えるべきか。
重要な観察として、奇数の個 ...
6月22日 18:23 投稿
競技プログラミングにおけるアルゴリズム実装：SMU Autumn 2023 Round 4 解説
A. Access Denied：パスワードの推測と応答時間解析
この問題は、サーバーからの応答時間を利用してパスワードを推測する対話型の課題です。パスワードの最大長は20文字であり、推測した文字列の長さが正解と異なる場合、応答には5msの遅延が生じます。また、文字ごとの照合には9msの遅延が加算されるという仕組みを利用します。
まず、長さ1から20までの文字列を順次送 ...
6月21日 23:00 投稿
第14回 藍橋杯 C/C++ Bグループ 省大会 競技課題の解説と実装
1. 日付統計 (Date Statistics)
8桁の数値が並んだ100個のデータから、2023年に存在する有効な日付（YYYYMMDD形式）がいくつ作れるかをカウントする問題です。部分列として抽出する必要があるため、全探索や動的計画法でアプローチします。このコードは計算済みの結果を出力する例です。
#include <iostream>
int main() {
// 探索アルゴリズムによって算出され ...
6月9日 22:20 投稿