異端開発室

本稿では、プログラミングコンテストやアルゴリズム学習で頻繁に利用される基本的なアルゴリズムについて解説します。特に、配列操作を効率化する線形次元削減テクニック、そして二分探索、貪欲法といった重要な解法に焦点を当てます。 線形次元削減のテクニック 累積和と差分配列 累積和（Prefix Sum）は、配列の特定区間の合計値を効率的に計算するための手法です。与え ...

離散化 #include <bits/stdc++.h> using namespace std; const int MAX_N = 1000010; int n, m; vector<int> originalValues; vector<int> addedValues; vector<int> startPos, endPos; vector<long long> diffArray; bool canProcess(int limit) { fill(diffArray.begin(), diffArray.end(), 0); for (int i = 0; i < li ...

マトリックス操作と深さ優先探索（DFS） 最初の問題は、与えられたバイナリ行列を行の反転と列の置換によって目標の行列に一致させられるかを判定するものです。行の反転は同一の行に対して2回行うと無効になるため、各行に対する操作は「行う」か「行わないか」の二択です。 まず、各行の要素の合計値を見て、反転することが確定している行を処理します。特定の行において ...

問題概要 配列内の2つの要素を選択し、その和が指定された値に一致する組み合わせを高速に見つける。配列は少なくとも1組の解を持つことが保証されている。 例：配列 [5, 6, 1, 4, 7, 8, 9]、目標値 10 解法1：全探索（二重ループ） すべてのペアを試す方法。時間計算量は O(N²) であり、効率が低い。 <pre> #include <iostream> using namespace std; v ...

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 ...

ある科学研究の調査で得られた自然数がn個あり、それぞれの数は1500000000（1.5×10⁹）以下である。異なる数の個数は10000個以下である。与えられた自然数それぞれの出現回数をカウントし、自然数の昇順に結果を出力する。 入力形式最初の行には整数nが与えられる。続くn行には自然数が一つずつ書かれている。 出力形式異なる数の個数m行が出力される。各行には自然数とその ...

LeetCode 977. 平方済みソート済み配列 この問題では、昇順にソートされた整数配列が与えられたとき、各要素を二乗した後の配列も昇順になるような新しい配列を作成します。配列の両端から中央に向かって比較しながら埋めていく手法が有効です。 実装上の注意点： 結果用の新しい配列を明示的に確保し、そこに値を埋めていく方式を採用すること 配列の末尾から順に値を ...

A - 二つのオーブンを使用した最小調理時間 N個の料理を連続して調理するのに必要な時間がT_i分与えられます。二つのオーブンを使用する場合の全料理の最短調理時間を求めます。 解法 動的計画法を用いて、一方のオーブンで実現可能な調理時間の組み合わせを求め、最小の最大調理時間を探索します。 #include <vector> #include <algorithm> #include <iost ...

二分探索は効率的な検索アルゴリズムで、ソート済み配列に対する操作に適しています。基本的な実装パターンは以下の通りです： int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length; while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; ...

二分探索法の基本ロジック 要素が昇順に整列された配列に対し、目的のキーが含まれるインデックスを対数時間で特定する関数です。境界値の更新順序と終了条件の設計が正しさの鍵となります。 参考実行枠組み #include <stdio.h> #include <stdlib.h> #define MAX_CAPACITY 10 #define SEARCH_FAILED 0 typedef int ValueT; typedef int IndexT; typedef st ...