二つのソート済み配列の中央値を二分探索で求める方法
問題の理解
二つのソート済み配列が与えられた場合、全体の中央値を効率的に見つける必要があります。単純な方法では両方の配列をマージしてから中央値を計算できますが、これではO(m+n)の時間計算量が必要です。より効率的な解法として、二分探索を用いることでO(log(min(m,n)))の時間計算量で解くことができます。
アルゴリズムの考え方
二つの配列から、左半分の要素数 ...
7月31日 01:06 投稿
競技プログラミング問題の解法とコード例
A 問題
ある日を選んで問題を解くとき、その日の問題数が次の日の問題数よりも多い場合に選択します。ただし、n+1 日目は 0 問とする。
コードを見る
<code>
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> a, b;
void solve() {
cin >> n;
a.resize(n + 1);
b.resize(n + 1);
for (i ...
7月15日 16:53 投稿
GJOI 2024.4.20 プログラミングコンテスト問題解説
朝の部
問題1: 鳥の撃ち合い
問題文:
n×nのグリッド上に、各格子点に1羽ずつ鳥がいます。(0,0)を除いて、すべての格子点に鳥がいます。(0,0)には無音の機関銃があり、任意の角度で発射できます。機関銃を発射すると、(0,0)から放射状に伸びる直線上にあるすべての鳥が撃たれます。最大でk回発射できます。撃てる鳥の最大数はいくつでしょうか？
ただし、m羽の鳥は事前に風 ...
7月7日 17:11 投稿
最長増加部分列の効率的解法：貪欲法と二分探索
動的計画法から最適解への転換
最長増加部分列(LIS)問題では、無秩序な配列から厳密に増加する最長の部分列を見つける。例えば配列[10,9,2,5,3,7,101,18]では、LISは[2,3,7,101]で長さ4となる。
動的計画法の基本アプローチ
基本解法は動的計画法(DP)によるO(n²)の実装：
def lis_length_dp(nums):
dp = [1] * len(nums)
for i in range(1, len(nums)):
f ...
7月6日 22:08 投稿
C言語による制御構造の基礎演習：分岐・反復処理の実装例
1. 単一値の階乗計算
nの階乗（n!）を算出する処理では、累積変数に対して反復処理を用いて乗算を適用します。
#include <stdio.h>
int main(void) {
int target_num = 0;
int factorial_val = 1;
printf("計算対象の整数を入力: ");
scanf("%d", &target_num);
for (int counter = 1; counter <= target_num; ++counter) {
f ...
7月5日 00:38 投稿
二分探索アルゴリズムの実践的まとめ
二分探索の基本原則
閉区間方式を推奨します。データ量が少ない場合は線形探索が適切です。探索終了時、iはtargetより大きい最初の要素を指し、jはtargetより小さい最初の要素を指します。配列にtargetが存在しない場合、挿入位置はiとなります。
74. 二次元行列探索
行列内の目標値探索手法。単一行/列の境界条件に注意。
public class MatrixSearcher {
public bool ...
7月4日 23:34 投稿
二分探索法と再帰を用いたデータ構造の問題解決
1. 二次元配列内の要素検索
二次元配列（各一次元配列の長さが同じ）で、各行が左から右に昇順に、各列が上から下に昇順にソートされている場合、与えられた整数が配列内に存在するかを判断する関数を作成します。
public class Solution {
public boolean find(int target, int[][] array) {
for (int i = 0; i < array.length; i++) {
for (in ...
6月29日 23:37 投稿
二分探索と二重ポインタの基本テクニック
二分探索
×
復習時の重要ポイント
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 投稿
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 投稿
木材伐採問題における最適切断高さの探索
きこりのミルコは、ある特殊な伐採機を用いて、要求される長さの木材を収集します。この伐採機は、設定された高さ H を基準に動作します。具体的には、伐採機は巨大な鋸刃を高さ H まで持ち上げ、その高さよりも高い部分を持つ全ての木から、H を超える部分を切り落とします。切り落とされた部分がミルコによって収集されます。H 以下の高さの木はそのまま残り、切り落とさ ...
6月25日 20:21 投稿