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 投稿
プログラミングコンテスト問題集（7問）
L1-1 人と神
指定された文字列を直接出力するPHP実装
<?php
echo "To iterate is human, to recurse divine.";
?>
L1-2 C言語速習
基本数値計算処理の実装例
#include <iostream>
using namespace std;
void calculate() {
int total, studied, hours;
cin >> total >> studied >> hours;
cout input;
int century = input / 100;
...
5月25日 23:04 投稿
二分木の深さ優先探索：非再帰アルゴリズムとJava実装
DFS分析
深さ優先探索(DFS)は子ノードを先に訪問し、その後親ノードを訪問する手法です。訪問順序により以下の3種類に分類されます：
前順序(pre-order)：根→左→右
中順序(in-order)：左→根→右
後順序(post-order)：左→右→根
DFS非再帰実装
前順序と後順序
前順序と後順序の実装は類似したロジックで実現できます。前順序訪問は根ノードから開始し、左部分木、右 ...
5月24日 22:35 投稿
LeetCode 二分木問題集（その2）
101 対称二分木
二分木の根ノード root が与えられたとき、木が対称構造か判定する。
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return checkNodes(root.left, root.right);
}
private boolean checkNodes(TreeNode leftNode, TreeNode rightNode) {
if (leftNode == null ...
5月18日 15:41 投稿
アルゴリズム入門：検索、グラフ探索、動的計画法、ハッシュ
検索アルゴリズム
データ集合から特定の要素を見つける操作です。代表的なものに線形探索と二分探索があります。
線形探索: 先頭から順番に各要素を比較し、目的の値が見つかるか、リストの終端に達するまで繰り返します。時間計算量はO(n)です。
二分探索: ソート済みの配列に対して使用されます。探索範囲の中間点の値と目的の値を比較し、探索範囲を半分ずつ狭めていき ...
5月17日 23:06 投稿