合同最短経路アルゴリズム応用技法
無限ナップサック構造型問題
正整数集合による数値構成問題において、合同最短経路アプローチが有効。任意の基準値Mを定義し、f(x)を「x + kM (k∈N)の形式で構成可能な最小k」として最短経路問題に変換。
構成可能数カウント応用
有名問題「スカイスクレイパー機」では、適切なモジュラ数を選択しf(x)を計算することで解が導出可能：
void dijkstra() {
...
whi ...
7月29日 04:47 投稿
洛谷 P1381 単語暗記 問題の解説
問題の説明
霊夢は n 個の単語を覚えたいのですが、一つの文章の一部分を通じてこれらの単語を覚えようとしています。文章は m 個の単語から構成されており、彼女は文章の中から連続した一部分を見つけ出し、その中に含まれる覚えたい単語の数を最大にしたいと考えています（重複する単語は一つとしてカウントします）。そして、覚える単語の数を最大にした上で、選んだ文 ...
7月28日 00:31 投稿
ABC352コンテスト問題解説
問題A: 停車可能区間の判定
ある区間内に指定された位置が含まれるかを判定する問題です。xとyの大小関係によって、区間の方向が変わる点に注意が必要です。
コード例
#include <iostream>
#include <algorithm>
int main() {
int n, x, y, z;
std::cin >> n >> x >> y >> z;
bool result = false;
if (x ...
7月7日 21:07 投稿
C言語によるLeetCode 1047と239の実装解説：スタック処理と単調キュー最適化
問題 1047: 隣接する重複文字の完全除去
問題定義
英小文字のみで構成される文字列が引数として渡されます。この文字列に対して、「隣接する同一文字をペアで取り除く」という演算を繰り返し適用します。すべての演算が行き詰まった時点で残っている文字列を返却してください。解答は一意に決まります。
入力例: "abbaca" → 出力: "ca"
制約条件: 文字列長は [1, 20000] ...
7月5日 22:28 投稿
LeetCode: 重複しない文字を含まない最長部分文字列の長さを求める
3. 重複しない文字を含まない最長部分文字列
文字列 s が与えられた場合、重複しない文字を含む最長の部分文字列の長さを見つけてください。
例 1:
<strong>入力:</strong> s = "abcabcbb"
<strong>出力:</strong> 3
<strong>説明:</strong> 重複しない文字を含む最長部分文字列は "abc" であるため、その長さ ...
7月2日 18:02 投稿
最小サイズの連続部分配列の探索
問題定義
n個の正の整数からなる配列と正の整数sが与えられたとき、要素の合計がs以上となる連続する部分配列のうち最小の長さを求める。条件を満たす部分配列が存在しない場合は0を返す。
例:
入力: s = 7, nums = [2,3,1,2,4,3]
出力: 2
説明: 部分配列[4,3]が条件を満たす最小長の連続部分配列
解法アプローチ
総当たり法
最も単純な方法は二重ループを用いた総当 ...
6月30日 23:57 投稿
CF251A 直線上の点の解説
問題文
Petyaは点が大好きです。彼の母親は彼に数直線OX上のn個の点を与えました。Petyaは、最も遠い2点間の距離がd以下となるような3つの異なる点を選ぶ方法がいくつあるか知りたいです。3つの点の順序は関係ありません。
入出力形式
入力
最初の行には2つの整数n (1 ≤ n ≤ 105) と d (1 ≤ d ≤ 109) が含まれます。次の行には、Petyaが持つ点のx座標を表すn個の整数x1, x ...
6月27日 00:38 投稿