競技プログラミング・アルゴリズム問題解説：動的計画法、単調スタック、貪欲法の実装
問題概要と考察
本稿では3つのアルゴリズム問題を解くための手法について説明します。各問題で異なる技術が要求されています。
第1問：骨牌配置の最適化
n枚の骨牌を並べるとき、ある位置から倒すことで連続して倒れる骨牌の数を最小化する問題です。
考え方
最終的な回答は、末尾のいくつかの骨牌を削除した後の状態から計算できます。任意の位置まで考えた時の最適値を ...
8月21日 23:21 投稿
ICPC 2025 成都站 8 題解説
A – 絵画の枚数
四捨五入を満たす整数列 b を構成する問題。
条件は各 i に対して
round(100·b_i/Σb)=a_i。
これを区間に直すと
(2a_i-1)·Σb/200 ≤ b_i < (2a_i+1)·Σb/200。
Σb ≤ 201 であることから、s を 1…201 まで全探索し、各 s に対して貪欲に b_i を決めればよい。
bool build(int n, vector<int> a, vector<int> &out) {
for (in ...
8月11日 08:10 投稿
競技プログラミングにおける構築技法と置換環の実装解説
A. 文字列生成の列挙処理
入力された2文字が同一か否かを判定し、条件を満たす文字列候補を列挙する。同一文字の場合は長さ1と2の2通り、異なる文字の場合は単体および結合形の計4通りを出力すればよい。
def solve_string_gen():
c1, c2 = input().split()
if c1 == c2:
print(2)
print(c1)
print(c1 * 2)
else:
print(4)
...
8月6日 05:07 投稿
DPと貪欲法による丑数の計算
丑数とは、2, 3, 5のいずれかの数の積からなる数のことです。
最初、私は深さ優先探索（DFS）と集合（set）を使って解こうとしたが、これは効率的ではありませんでした。代わりに、各丑数を順番に配置したいと考えました。例えば、6の次は8であり、9ではありません。
次の丑数は以下の3つの可能性のうちの最小値になります：
prev1 * 2;
prev2 * 3;
prev3 * 5;
ここで、pre ...
8月3日 22:24 投稿
Codeforces Round 1051 (Div. 2) A~D2問題の解説
A. 全ての長さの減算
思考問題。
長さが \(k(k \in [1,n])\) の区間を選び1を引く操作を繰り返す場合、まず\(a_i = n\) の位置を特定します。次に、\(n\) が存在する区間を維持し、\(n-k+1\) がその両側に存在するか確認し、存在すれば区間を拡張します。存在しない場合は操作は不可能です。
コードを表示```
#include <bits/stdc++.h>
using namespace std;
using i ...
8月1日 18:57 投稿
限定枚数の板による占有区間の最小被覆アルゴリズム
複数の隣接する配置ユニットが一列に連なっている状態を想定する。これらユニットのうち特定の位置には対象物が存在しており、それらの位置を最大 $M$ 枚の連続する板材で覆う必要がある。各板材は任意の長さを指定可能だが、使用できる総数は上限 $M$ に固定されている。すべての存在位置が含まれるように板材を設置した際、板材が占めるユニットの合計数を最小化するため ...
8月1日 11:28 投稿
2023年10月25日 模擬試験の反省
時間管理
7:40 から 8:40 まで、対拍と乱数生成の準備を行い、問題を読み込み、T1 を開始しました。40分で初回の提出を完了し、対拍で小さな誤りを見つけたため修正して再提出しました。
8:40 から 10:20 まで、T2 の解決に取り組みました。以前の模擬試験の T2 と類似点がありましたが、直接的な解法が見つからなかったため、まずは暴力解法を考えました。しかし、n ≤ 6 ...
7月14日 20:38 投稿
2010年NOIP普及組 課題解説
問題1: 数字の出現回数のカウント
与えられた区間 $[L, R]$ 内のすべての整数について、数字「2」が合計で何回現れるかを求める問題です。
输入例:
2 22
出力例:
6
解法:
各区間内の整数を1つずつ走査し、各数字を10進数桁ごとに分解して「2」の出現回数をカウントします。
#include <iostream>
using namespace std;
int main() {
int left, right;
...
7月1日 16:28 投稿
競技プログラミング問題集: 生成器、MEX、XORの応用
理想的な生成器の判定
正整数kが「理想生成器」であるとは、任意の整数n（n ≥ k）が、長さkの回文配列の要素和として表現可能な場合を指す。回文配列とは、配列aがa1からakまでとakからa1までが同一となる配列である。例として、k=1は理想生成器である（nは[n]で表現可能）が、k=2は非理想（3を表現不可能）。
解法: kが奇数の場合のみ理想生成器となる。偶数の場合、配列 ...
6月26日 21:45 投稿
2024年ICPCヨーロッパ大会最終問題解説
A. Hitoshizuku
貪欲法で解きます。
右端点でソートした後、マッチングされていない点に対して、各右端点以下の点を管理し、その端点が管理されている集合の中で右端点が最も小さい2点とマッチングします。
最適性の証明は調整法によるそうです。
コード例
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using name ...
6月21日 19:26 投稿