USACO13OPEN Photo G の解説
序文
問題のリンク：洛谷。
問題概要
長さが \(n\) の配列があり、一部の要素はすでに色が塗られています。\(m\) 個の制約が与えられ、それぞれ \(l_i \sim r_i\) の範囲内にちょうど1つの要素が色付きであることを示します。この制約をすべて満たすように、最大で何個の要素を色付けできるかを求めます。
\(n \leq 2 \times 10^5\)，\(m \leq 10^5\)。
問題解析
解法 \(1\ ...
8月15日 23:59 投稿
洛谷 P1381 単語暗記 問題の解説
問題の説明
霊夢は n 個の単語を覚えたいのですが、一つの文章の一部分を通じてこれらの単語を覚えようとしています。文章は m 個の単語から構成されており、彼女は文章の中から連続した一部分を見つけ出し、その中に含まれる覚えたい単語の数を最大にしたいと考えています（重複する単語は一つとしてカウントします）。そして、覚える単語の数を最大にした上で、選んだ文 ...
7月28日 00:31 投稿
二分探索と二重ポインタの基本テクニック
二分探索
×
復習時の重要ポイント
midの計算時にint mid = left + (right - left) / 2;を使用して、int mid = (left + right) / 2;による整数オーバーフローを防ぐ必要がある
通常の検索、左境界、右境界はすべて左閉じ右閉じ区間を使用可能。閉区間のright = arr.length-1と開区間のright = arr.lengthの違い、およびwhileループでの<=と<の使い分けに注意
3種 ...
6月28日 01:20 投稿