LeetCode バイウィークリーコンテスト 第111回 解説
問題2824: 目標値より小さい和を持つインデックスペアの数え上げ
この問題は、全ての可能なペアを列挙して条件を満たすものをカウントするだけで解決できます。
class Solution {
public:
int countPairs(vector<int>& values, int target) {
int length = values.size();
int result = 0;
for(int i = 0; i + 1 < length; i++) {
...
8月2日 18:56 投稿
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 投稿
2025 XCPC浙江省競技プログラミングコンテスト FLM問題解説
F. Challenge NPC III
多起点最短経路と第二最短経路問題。
同じ色の頂点に対してBFSを実行し、各経路の起点を維持します。同じ色の頂点から自身への経路が最短であるため、最終的に第二最短経路がkより小さいかを判定すれば十分です。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n, m, k;
cin >> ...
8月1日 18:35 投稿
挿入型動的計画法の解説
概念
挿入型動的計画法（DP）とは、特定の順列に基づいてDPを行う問題で、計算量は一般的にO(n2)からO(n3)の範囲内です。この種の問題では、順列内の昇順や降順の変化点が答えに大きな影響を与えます。
基本的なアプローチは以下の通りです：
数値を小さい順に挿入し、その段階で状態設計を行います。これにより、既に挿入された数値は現在の数値より小さく ...
8月1日 16:29 投稿
eJOI競技プログラミング問題解説
eJOI（European Junior Olympiad in Informatics）の過去問から、いくつかの問題を解説します。
eJOI2017 A - Magic
問題概要
長さ\(n\)の文字列\(a\)が与えられ、使用される文字の種類数を\(|\Sigma|\)とします。部分文字列が「魔法的」であるとは、その部分文字列内に全ての種類の文字が少なくとも1回含まれ、かつ全ての種類の文字の出現回数が等しいことを意味します。 ...
8月1日 00:11 投稿
動的計画法の基礎：バックパック問題の完全解説
動的計画法の基礎：バックパック問題の完全解説
バックパック問題は動的計画法（DP）の最も古典的で基礎的な問題の一つです。多くのアルゴリズム学習者の「必修科目」とも言えるこの問題は、見た目は単純（バックパックに荷物を詰めて価値を最大化する）ですが、01バックパック、完全バックパック、多重バックパックなど多くのバリエーションに派生し、DPの核心思想が体系 ...
7月30日 16:50 投稿
第5回藍橋杯 C++ B級プログラミングコンテスト問題解説
1. ビールと飲料の購入
解法: 全探索（ブルートフォース）
ビール（1缶2.3元）と飲料（1缶1.9元）の合計金額が82.3元。ビールの本数が飲料より少ない条件で計算します。浮動小数点計算の誤差を避けるため、10倍して整数で処理します。
#include <iostream>
using namespace std;
int main() {
for (int beer = 0; beer <= 823 / 23; ++beer) {
for ( ...
7月29日 17:12 投稿
アルゴリズム競技問題集：動的計画法とデータ構造の応用
問題A：連続要素の除去
この問題では、与えられたシーケンスから連続する重複要素を除去する必要があります。
解法：連続する同じ要素を1つにまとめることで、シーケンスの長さを最小化します。
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
void process() {
int elements;
cin >> elements;
...
7月29日 16:55 投稿
鋳造炉の容量制約下における最大耐久性の動的計画法
問題定義
特殊な錬成炉を用いて伝説の武器を鍛造する際、計 N 種類の素材を準備します。各素材 i には固有の強度パラメータ A[i] が割り当てられています。錬成規則により、素材は番号順（1 から N まで）に厳密に投入しなければなりません。
炉の容量は最大 W 個の素材までです。ここで重要な操作制限として、新しい素材を投入する直前 に限り、炉内に保管されている素材 ...
7月28日 19:24 投稿
Javaアルゴリズム：動的計画法による0/1ナップサック問題の解法
ナップサック問題は、有限の容量を持つバッグにどの物品を詰めるかを最適化する古典的なアルゴリズム問題です。特に0/1ナップサック問題は、各物品をバッグに入れるか入れないかの二択しかない場合を指します。
問題設定：
3つの物品があります：
物品A：価値1000、重量1kg
物品B：価値2000、重量4kg
物品C：価値1500、重量3kg
バッグの容量は4kgで、この中に詰められる ...
7月26日 16:45 投稿