2026年NOI問題解決記録（十五）
コンテストリンク
\(\text{著者：DaiRuiChen007}\)
A. [UOJ702] 張飛の精鋭兵団 (3.5)
問題リンク
コンテストの過程を木として捉え、値を大きい順に埋めていく。制約は親子のトポロジカル順序であり、係数が\(-1\)の層を優先的に埋める。もし埋められない場合は、子ノードが最も多く、勝利回数が最も多いノードを選ぶ。
コードに落とし込むと複雑度を効率的に改善できる。
...
8月12日 06:48 投稿
プログラミングコンテスト模擬試験問題集
1. 約数の個数
2. 最大部分行列問題
総当たり法による解法
#include <iostream>
using namespace std;
// 部分行列の合計を計算
int grid[40][30];
long long maxSum;
int main() {
// 30x20のグリッドを読み込む
for(int row = 1; row <= 30; row++) {
for(int col = 1; col <= 20; col++) {
cin >> grid[row][col];
...
8月10日 22:56 投稿
Javaアルゴリズム実践：コレクション操作とデータ構造
コレクション操作ユーティリティ
ArraysとCollectionsクラスの主要メソッド：
asList：リスト変換には戻り値が必要
copyOfRange：配列の部分コピー
型変換テクニック
// List<Integer> → int[]
public int[] convert(List<Integer> list) {
return list.stream()
.mapToInt(Integer::intValue)
.toArray();
}
Stream ...
8月10日 13:21 投稿
動的計画法（1）——アルゴリズム入門（16）
動的計画法を学ぶために、まずは2つの問題から始めましょう。
鋼板の切断問題
1.1 問題の提示
ある企業は長さがnの鋼板をいくつかの断片に切り分けて販売したいと考えています。市場では、長さi（0[r_n = \max_{1\leq i\leq n}( p_i + r_{n-i}) ]よって、この問題を解決するには「トップダウン」の再帰的な方法が利用できます。
1.3 トップダウン再帰実装
public static ...
8月9日 20:24 投稿
一月の競技プログラミング問題解説
### \[ABC154F\] Many Many Paths
この問題は組み合わせ数を使用します。簡単な問題ですが、詳細な解説は後日行います。
### CF1542D
この問題では動的計画法（DP）を使用します。問題文を変換すると、各操作 \(+x\) に対して、その操作が加算されるためには、それより小さい操作が必要であることがわかります。つまり、操作の具体的な値ではなく、その大小関係に注目 ...
8月5日 01:57 投稿
競技プログラミング問題の解法と実装
A - 二つのオーブンを使用した最小調理時間
N個の料理を連続して調理するのに必要な時間がT_i分与えられます。二つのオーブンを使用する場合の全料理の最短調理時間を求めます。
解法
動的計画法を用いて、一方のオーブンで実現可能な調理時間の組み合わせを求め、最小の最大調理時間を探索します。
#include <vector>
#include <algorithm>
#include <iost ...
8月4日 20:00 投稿
C言語で実装する階段ジャンプの問題解決手法（組合せと動的計画法）
問題の定式化
段数が n の階段を登る際、一度に1段または2段ずつ飛んで進行します。この移動規則に従い、最終段に到達するまでの全経路パターン数を計算するアルゴリズムについて解説します。
アプローチ1：数学的組合せによる求解
組合せ数学の応用では、1段ジャンプを s 回、2段ジャンプを d 回実施した場合の制約式 s + 2d = n に着目します。具体的な回数組合せが確定 ...
8月3日 23:08 投稿
DPと貪欲法による丑数の計算
丑数とは、2, 3, 5のいずれかの数の積からなる数のことです。
最初、私は深さ優先探索（DFS）と集合（set）を使って解こうとしたが、これは効率的ではありませんでした。代わりに、各丑数を順番に配置したいと考えました。例えば、6の次は8であり、9ではありません。
次の丑数は以下の3つの可能性のうちの最小値になります：
prev1 * 2;
prev2 * 3;
prev3 * 5;
ここで、pre ...
8月3日 22:24 投稿
最長共通部分列の解法
最長共通部分列
2つの文字列 s1 と s2 が与えられたとき、これらの文字列の最長共通部分列の長さを返してください。共通部分列が存在しない場合は 0 を返します。
文字列の部分列とは、元の文字列から文字の相対的な順序を変更せずに一部の文字を削除（または削除しない）して形成される新しい文字列です。
例えば、"ace" は "abcde" の部分列です ...
8月3日 19:44 投稿
動的計画法の核心パターンと実装テクニック
動的計画法の基本フレームワーク
動的計画法は過去の計算結果を再利用し、重複計算を回避する手法です。計算結果は通常1次元または2次元の配列に格納されます。実装には以下の3ステップが不可欠です。
ステップ1: 状態の定義
配列memo[i]の意味を明確に定義します。例えばmemo[i]が「i段目までの階段を登る方法の総数」を表す場合、最終的にmemo[n]が求める解となります。 ...
8月2日 20:11 投稿