競技プログラミング問題の解法と実装
A - 二つのオーブンを使用した最小調理時間
N個の料理を連続して調理するのに必要な時間がT_i分与えられます。二つのオーブンを使用する場合の全料理の最短調理時間を求めます。
解法
動的計画法を用いて、一方のオーブンで実現可能な調理時間の組み合わせを求め、最小の最大調理時間を探索します。
#include <vector>
#include <algorithm>
#include <iost ...
8月4日 20:00 投稿
順序リストの実装
空間計算量
一般的な再帰は深さ優先探索であり、深さ優先探索の空間計算量は再帰の深さによって決まります。ある方向での再帰が終了すると、その時点で使用していたスタック領域が解放され、同じメモリが再利用されます。
順序リスト
静的順序リスト
typedef int SLDataType;
#define N 10
struct SeqList {
SLDataType a[N];
int size;
};
動的順序リスト
seq ...
7月30日 01:26 投稿
フラッドフィルアルゴリズムによる領域の囲い込みと最長連続シーケンス探索
問題1: フラッドフィルを用いた領域の囲い込み
二次元グリッドが与えられ、各セルは'X'または'O'で構成されます。境界に接続されていない'O'の領域を特定し、それらを'X'に変換する必要があります。境界に隣接する'O'は変換せずに保持します。
アプローチ: 深さ優先探索(DFS)を活用し、境界上の'O'から接続された領域を一時マークで識別します。その後、マークされていない ...
7月28日 16:43 投稿
バックトラッキングアルゴリズムとその応用問題
組合せ問題（Leetcode77）
// アプローチ: 1からnまでの数を再帰的に探索し、リストでk個の組み合わせが作成されたかを記録
// 各ループの開始値が前の値と重複しないように、開始インデックスを設定
class Solution {
private List<List<Integer>> 結果;
private List<Integer> 現在の組み合わせ;
private int 目標サイズ;
public ...
7月2日 17:53 投稿
3×3グリッド全点灯における最小操作手数求解アルゴリズム
問題概要
3行3列のマトリックス状に配置された9つの照明スイッチがある。各スイッチを操作すると、該当する位置および上下左右に隣接するセルの電球状態が反転する（ON⇔OFF）。初期状態の入力が与えられた際、すべてのセルをON状態に切り替えるための最小操作回数を求めよ。
入力・出力仕様
標準入力からは3行にわたり、各行3個の整数が半角スペース区切りで渡される。各 ...
6月29日 21:46 投稿
グラフ理論と行列操作アルゴリズム
100. 島の最大面積
与えられた1（陸地）と0（水）からなる行列において、島の最大面積を計算します。島は水平または垂直方向に隣接する陸地で構成され、周囲が水で囲まれているものとします。
from collections import deque
def max_area_of_island(grid):
rows, cols = len(grid), len(grid[0])
max_area = 0
for i in range(rows):
for j in ...
6月18日 17:18 投稿
牛客プログラミングコンテスト89 解法解説
A. 牛牛吃米粒
入力: 整数 n, k と符号なし整数 s、および k 個の位置 a_i。各ビット位置が制限されていないか検証し、s のビットが立っている位置が禁止領域と重なる場合は "NO"、それ以外は "YES" を出力。
#include <iostream>
#include <vector>
using namespace std;
int main() {
unsigned long long s;
int n, k;
cin >> n >> k;
vect ...
6月5日 22:18 投稿
深さ優先探索（DFS）の実装と応用
基本原理：
深さ優先探索は、開始ノードから出発し、一つの分岐を深く進み続けます。葉ノードまたは進めなくなったノードに到達するまで探索を続けます。
探索が葉ノードまたは進めなくなったノードに到達した場合、未探索の前のノードに戻り、他の分岐の探索を続けます。
既に訪問したノードをマークすることで、同じ経路での重複訪問を避けます。
DFSアルゴリズムのス ...
5月31日 11:33 投稿
コーススケジュールII - トポロジカルソート - DFS・BFSによる解法
問題概要
0からnumCourses-1までの整数で表される複数のコースが存在します。配列prerequisitesの各要素prerequisites[i] = [ai, bi]は、コースaiを受講する前にbiを完了する必要があることを示します。
すべてのコースを受講可能な順序を返してください。複数の有効な順序が存在する場合は、そのいずれかを返します。不可能な場合は空配列を返します。
例1
入力: numCou ...
5月30日 02:57 投稿
競技プログラミングにおける探索・数論・木構造アルゴリズムの実装技法
行選択による列制約の充足判定
グリッド状のデータに対し、行の削除操作を制限回数内で行った後、残存する列の要件数が指定値以下に収まるかを検証する問題である。行数が比較的小さいため、深さ優先探索を用いて行の採用・不採用のパターンを網羅する。各探索ノードでは、未削除行に含まれる列インデックスを集合に記録し、重複を除いた後のサイズが閾値を超えないか判定 ...
5月26日 19:47 投稿