異端開発室

モー隊（Mo's Algorithm）は、範囲クエリをオフラインで効率的に処理するためのアルゴリズムです。本質的には平方分割の考え方を応用したもので、クエリの順序を工夫することで計算量を削減します。 標準的なモー隊 標準的なモー隊は、静的な配列に対する範囲クエリに使用されます。 基本的な考え方 配列をサイズ $B = \frac{n}{\sqrt{m}}$ のブロックに分割します ...

本稿では、C言語の基礎から応用までを網羅する一連の実践演習問題を提供します。各問題は「穴埋め」「誤り訂正」「関数実装」の3形式で構成され、配列操作、文字列処理、ポインタの使い方、およびアルゴリズム的思考力を段階的に鍛える設計となっています。 問題セットA：数字の出現頻度と配列操作 以下の関数は、整数値の各桁に含まれる0〜9の数字の出現回数をカウント ...

木構造と動的計画法の親和性 木（Tree）は再帰的に定義されるデータ構造であり、部分問題に分割して解く動的計画法（DP）と非常に相性が良いです。本稿では、木構造におけるDPの典型的な問題と、その状態遷移および実装について解説します。 グラフ理論における4つの典型問題 一般のグラフにおいて、以下の4つの問題はNP困難またはco-NP完全として知られていますが、木構 ...

アルゴリズムの設計において、各局面で局所的に最善の選択を行うことで、結果として大域的な最適解を目指すアプローチを「貪欲法（Greedy Algorithm）」と呼びます。この手法は計算コストが低く実装が比較的容易ですが、必ずしも全てのケースで最適解を保証するわけではありません。以下では、贪欲法を応用した代表的な 2 つの問題、すなわち物体の収容効率化とデータ圧縮 ...

1. 高効率な乱数生成 現代的なJava開発（JDK 7以降）では、Randomクラスよりも並列処理に強く、より高品質な乱数を提供するThreadLocalRandomの使用が推奨されます。 Java: 指定範囲の乱数生成 /** * [min, max) の範囲で整数を生成 */ public static int getBoundedRandom(int min, int max) { return ThreadLocalRandom.current().nextInt(min, max); } Java: 重 ...

1. 1からnまでの総和 整数 n を読み込み、1+2+…+n を出力する。 int n, total = 0; cin >> n; for (int i = 1; i n; for (int v = 2; v > n; for (int i = 0; i < n; ++i) { cin >> x; avg += x; } printf("%.4f", avg / n); 7. 整数列の総和と平均（小数5桁） int n, val, total = 0; cin >> n; for (int i = 0; i < n; ++i) { cin >> val; total += val; } printf("%d ...

繰り返し二乗法 (Binary Exponentiation) 繰り返し二乗法は、べき乗の計算（$x^n \pmod m$）を効率的に行う手法です。標準的な pow 関数よりも高速であり、大きな数に対する余り（mod）の計算を安全に行うことができます。 アルゴリズムの原理 指数 $n$ を 2 進数として分解することで、計算回数を $O(n)$ から $O(\log n)$ に削減します。例えば、$x^{10}$ を計算する場 ...

100〜999の範囲にある3桁の数字のうち、各桁（一の位、十の位、百の位）の乗算結果が各桁の加算結果と一致する数値とその総数を出力する処理について説明します。 アルゴリズムの実装手順 1. 全ての3桁の数値を走査するループを構築します。 for (int num = 100; num < 1000; num++) 2. 各桁の値を抽出する必要があります。 例として数値472を考えます 472 / 1 == 4 ...

区間（Interval）を扱うアルゴリズム問題は、ソートと貪欲法（Greedy Algorithm）を組み合わせることで効率的に解決できる場合が多くあります。ここでは、「重複する区間の削除」「文字列の分割」「区間の統合」という3つの代表的なパターンについて解説します。 1. 無重畳区間の最小削除数 与えられた区間の集合から、重なりをなくすために削除する必要がある最小の区間 ...

数独ゲームにおける検証ロジックについて詳細を説明します。 行単位の検証処理： 各横一行に対して、1から9までの数字がすべて含まれているか確認します。特定の数値を固定し、配列内の各行と比較していきます。最後まで一致する要素が見つからない場合（インデックスが8に達した際）、エラーを出力してプログラムを終了します。 int fixed_value; for(int row_index = 0; ...