# AI用DSA設計・実装ガイドライン 更新日: 2026-09-08 言語: 日本語 状態: experimental ## 目的 この文書は、AIがデータ構造とアルゴリズムの設計、実装、検証を支援するときの判断基準です。DSAを機械的に当てはめるためではなく、正しさを守りながら、実際の制約に合う選択を行うために使います。 人向けページと同じ構造化ルールから生成し、設計・実装・レビューで判断基準がずれないようにします。 ## 対象範囲 課題を定義し、正しさを守り、データ構造とアルゴリズムを選択し、実装と測定で検証するまでを対象にします。Android版VEINは、経路探索に限定せず、実際のコードで確認できる戦闘、魔力脈、描画、進行管理などの具体例に使います。 ## AIへの指示 - 最初に、利用者が困る場面、入力、出力、入力サイズ、実行頻度、制約を確認する。 - 不明な仕様、規模、端末条件を推測で確定しない。仮定した場合は明示する。 - データ構造やアルゴリズムの名前から設計を始めず、必要な操作と守る振る舞いから選ぶ。 - 最適化前に、変更前後で守る正しさをテストする。 - Big Oを実行時間として扱わない。計算量による予測とAndroid実機の測定を分ける。 - 高速化だけでなく、正しさ、応答性、メモリ、割り当て、保守性も比較する。 - 改善が確認できない結果や、単純な実装で十分だった結果も残す。 - VEINを例に挙げる場合は、実際のコードを確認し、存在しない機能や用途を推測で作らない。 - コードを変更する場合は、対象プロジェクトの既存設計とテスト方法を確認してから作業する。 ## 設計を提案するときの順番 1. 利用者の場面と解く課題を一文で定義する。 2. 入力、出力、n、実行頻度、端末上の制約を記録する。 3. 変えてはいけない振る舞いを、具体例とテストで固定する。 4. 現在の実装と時間・空間計算量を分析する。 5. 主な操作に合う候補を複数比較し、最も単純な選択を提案する。 6. Microbenchmarkなどで局所的な仮説を確かめる。 7. 実機の利用者操作でフレーム時間などの影響を確かめる。 8. 結果、代償、不採用案、適用限界を作業結果として報告する。 ## Design & Analysis（設計と分析） 課題を定義し、データの持ち方と処理手順を設計して、正しさと効率を確かめます。 ### Designing Data Structures and Algorithms（データ構造とアルゴリズムの設計） - ルールID: `designing-data-structures-and-algorithms` - 判断: 入力・出力・制約を明確にしてから、必要な操作に合うデータ構造とアルゴリズムを設計する。 - 意味: 計算したい課題を定義し、データの表し方と処理手順を選び、正しさと使用資源を確かめる流れを説明します。 - 理由: 個別の解法を暗記せず、未知の課題にも使えるDSAの設計プロセスを身につけられます。 確認すること - 入力と出力を定義したか - 守る条件と入力規模を明確にしたか - データ構造を選ぶ理由があるか - 正しさと時間・空間計算量を説明できるか 良い例: VEINの移動処理を、盤面・通行可否・目的地・次の一歩という計算上の課題に整理してからBFSを選ぶ。 避ける例: 有名なアルゴリズムを先に決め、用途を後付けする。 ## Array / Hash Table（配列・ハッシュテーブル） 配列の走査と、キーから値を探すハッシュテーブルの使い分けを学びます。 ### Hash Table（ハッシュテーブル） - ルールID: `hash-table` - 判断: 頻繁に行う操作がキーによる検索であり、追加メモリと更新コストを許容できる場合に使う。 - 意味: キーから対応する値を探す仕組みと、VEINの戦闘で対象IDごとにダメージを集計するMapの使い方を説明します。 - 理由: 値を先頭から探す代わりに、キーのハッシュ値から保存場所を絞ることで、検索を平均O(1)で行えます。 確認すること - 何をキーにするか - キーのequalsとhashCodeが安定しているか - 順序を保持する必要があるか - 追加メモリと更新コストを許容できるか 良い例: 攻撃対象のIDをキーにして、同じtick内で受けるダメージをMapへ加算する。 避ける例: 順番に一度読むだけの小さな一覧を、速そうという理由だけでHashMapへ変える。 ### Two Sum（2つの数の和） - ルールID: `two-sum` - 判断: Arrayによる全探索と、必要な相手をMapから探す方法を、正しさ・時間・追加メモリの観点で比較する。 - 意味: 複数の整数から、二つを足すと指定された値になる組を見つける課題を題材に、ArrayとHashMapの選択を比較します。 - 理由: 配列の全探索とハッシュテーブルによる検索を比較でき、時間とメモリのトレードオフを学べます。 確認すること - 同じ位置の要素を二回使っていないか - 同じ値が別の位置にある入力を扱えるか - 返すのが値ではなく位置であることを守れるか - 時間計算量と空間計算量を説明できるか 良い例: 走査中にtargetとの差をMapで探し、見つかった時点で二つの位置を返す。 避ける例: ソートして位置情報を失ったまま、二つの値だけを返す。 ### Group Anagrams（アナグラムのグループ化） - ルールID: `group-anagrams` - 判断: 各単語から同じグループを表すキーを作り、そのキーごとにMapへまとめる。 - 意味: 文字の並び順だけが異なる単語を、同じグループへまとめる課題です。 - 理由: 複数の値を同じ特徴量で分類するときの、ハッシュテーブルの使い方を学べます。 確認すること - 同じ文字数を正しく数えているか - 空文字を扱えるか - キーの作成コストを説明できるか 良い例: 文字頻度をキーにして、同じ構成の名前を同じ一覧へ追加する。 避ける例: 単語同士をすべて比較し、グループが増えるたびに全件を調べ直す。 ### Valid Sudoku（有効な数独） - ルールID: `valid-sudoku` - 判断: 行・列・区画ごとにSetを持ち、数字を一度の走査で検証する。 - 意味: 数独盤面の各行、各列、各3×3区画に重複がないかを確認する課題です。 - 理由: 二次元配列の位置と、重複検出用のSetを組み合わせる方法を学べます。 確認すること - 空きマスを無視しているか - 行・列・区画を別々に検証しているか - 区画番号を正しく計算できるか 良い例: 各マスの数字を、対応する行・列・区画のSetへ登録し、既存なら不正とする。 避ける例: 行だけを検証し、列や3×3区画の重複を見落とす。 ## Two Pointers（2ポインター） 二つの位置を動かし、探索範囲を効率よく絞る考え方を学びます。 ### 3Sum（3つの数の和） - ルールID: `three-sum` - 判断: 配列をソートし、一つを固定して残りを左右のポインターで探索する。 - 意味: 整数配列から、合計が0になる重複しない三つ組をすべて見つける課題です。 - 理由: ソート後の順序を利用して、探索範囲を動かす考え方を学べます。 確認すること - 同じ三つ組を重複して返していないか - ポインターを動かす条件が正しいか - ソートの計算量を含めているか 良い例: 固定値と左右の合計が小さければ左、大きければ右を動かす。 避ける例: 三重ループで全組合せを調べ、重複を後から複雑に除去する。 ### Container With Most Water（最も多くの水を入れられる容器） - ルールID: `container-with-most-water` - 判断: 両端から始め、面積を記録しながら低い側のポインターを内側へ動かす。 - 意味: 高さの配列から、二本の線で作れる最大面積を求める課題です。 - 理由: 捨てても最適解を失わない候補を説明しながら、探索範囲を縮める方法を学べます。 確認すること - 幅と低い方の高さで面積を求めているか - 低い側を動かす理由を説明できるか - 全候補を調べずに済む根拠があるか 良い例: 現在の面積を記録し、高さが低い側だけを一つ内側へ進める。 避ける例: 根拠なく左右を交互に動かし、最大候補を飛ばす。 ## Linked List（連結リスト） ノード同士のつながりをたどり、追加・削除・並べ替えを扱います。 ### Add Two Numbers（2つの数の加算） - ルールID: `add-two-numbers` - 判断: 二つのノードと繰り上がりを同時に管理し、末尾まで一度ずつたどる。 - 意味: 逆順の各桁を持つ二つの連結リストを足し、新しい連結リストで答えを作る課題です。 - 理由: 長さの異なる連結リストと繰り上がりを、一つの反復処理で扱う方法を学べます。 確認すること - 片方が先に終わる場合を扱えるか - 最後の繰り上がりを追加できるか - 入力ノードを不用意に壊していないか 良い例: 存在しない側を0として加算し、合計の1桁と繰り上がりを分ける。 避ける例: 二つのリストが同じ長さであると仮定する。 ### Merge Two Sorted Lists（2つのソート済み連結リストの結合） - ルールID: `merge-two-sorted-lists` - 判断: 先頭ノードを比較し、小さい側を結果へつないでポインターを進める。 - 意味: 昇順の二つの連結リストを、一つの昇順リストへまとめる課題です。 - 理由: ノードを作り直さず、参照をつなぎ替えながら線形時間で処理する方法を学べます。 確認すること - 空のリストを扱えるか - 残ったノードを最後につないでいるか - 結果の順序が保たれているか 良い例: ダミーヘッドを使い、結果の先頭だけを特別扱いしない。 避ける例: 全要素を配列へ移して再ソートする。 ## Stack / Queue（スタック・キュー） 後入れ先出しと先入れ先出しを使い、処理順序を管理します。 ### Valid Parentheses（有効な括弧） - ルールID: `valid-parentheses` - 判断: 開き括弧をStackへ積み、閉じ括弧が来たら直前の開き括弧と対応するか確認する。 - 意味: 丸・波・角括弧が、正しい種類と順序で閉じられているか確認する課題です。 - 理由: 最後に開いたものを最初に閉じる、後入れ先出しの性質を学べます。 確認すること - 空のStackから取り出していないか - 括弧の種類が対応しているか - 最後にStackが空か確認しているか 良い例: 閉じ括弧ごとに、対応する開き括弧をStackの末尾から取り出して比較する。 避ける例: 各種類の個数だけを数え、閉じる順序を確認しない。 ### Min Stack（最小値を取得できるスタック） - ルールID: `min-stack` - 判断: 各要素と、その時点までの最小値を一緒に積む。 - 意味: 通常のStack操作に加え、現在の最小値を定数時間で取得できるStackを設計する課題です。 - 理由: 操作を高速にするため、更新時に補助情報を保持する設計を学べます。 確認すること - pushとpop後の最小値が正しいか - 同じ最小値が複数ある場合を扱えるか - 各操作の計算量を説明できるか 良い例: 値と現在の最小値のペアをStackへ積む。 避ける例: 最小値を取得するたびにStack全体を走査する。 ## Binary Search（二分探索） 条件を満たす範囲を半分ずつ絞る探索方法を学びます。 ### Search Insert Position（挿入位置の検索） - ルールID: `search-insert-position` - 判断: 答えになり得る半開区間を保ちながら二分探索する。 - 意味: 昇順配列でtargetを探し、存在しなければ挿入すべき位置を返す課題です。 - 理由: 検索結果が見つからない場合にも、境界そのものを答えとして使う方法を学べます。 確認すること - 先頭と末尾への挿入を扱えるか - 探索区間の定義が一貫しているか - 無限ループにならないか 良い例: 探索終了時にleftを挿入位置として返す。 避ける例: 見つからない場合を一律に-1として、挿入位置を失う。 ### Search in Rotated Sorted Array（回転ソート配列の検索） - ルールID: `search-in-rotated-sorted-array` - 判断: 中央を見て左右どちらが整列済みか判定し、targetを含む側へ探索範囲を絞る。 - 意味: 途中で回転された昇順配列からtargetの位置を探す課題です。 - 理由: 配列全体が単純な昇順でなくても、局所的な順序を使って二分探索できます。 確認すること - どちら側が整列済みか判定できるか - targetが境界値の場合を含めているか - 探索範囲が必ず狭くなるか 良い例: 整列済みの範囲にtargetが含まれるか確認して、残す側を決める。 避ける例: 回転位置を無視して通常の二分探索を行う。 ## Tree / Graph（木・グラフ） 要素同士の関係を表し、深さ優先探索と幅優先探索でたどります。 ### Number of Islands（島の数） - ルールID: `number-of-islands` - 判断: 未訪問の陸を見つけるたびに数を増やし、DFSまたはBFSでつながる陸を訪問済みにする。 - 意味: 陸と水からなる二次元グリッドで、上下左右につながった陸のまとまりを数える課題です。 - 理由: 二次元配列をグラフとして捉え、連結成分を探索する基本を学べます。 確認すること - 上下左右だけを隣接としているか - 同じマスを再訪問しないか - 盤面の端を越えないか 良い例: 未訪問の陸から探索を開始し、到達した陸をすべて訪問済みにする。 避ける例: 陸のマスを一つずつ数え、つながりを考慮しない。 例外・補足: VEINでは同じ考え方を、コアに接続された組織をQueueと訪問済みSetでたどり、魔力脈を近い順に活性化する処理に使っています。これは目的地までの経路を求める処理ではなく、連結した範囲を展開するBFSです。 ### Clone Graph（グラフの複製） - ルールID: `clone-graph` - 判断: 元ノードと複製ノードの対応をMapへ保存し、DFSまたはBFSで隣接関係を再構築する。 - 意味: 連結された無向グラフを、元とは独立した同じ構造のグラフとして複製する課題です。 - 理由: 循環を含む構造を再訪問せず、参照関係を保って複製する方法を学べます。 確認すること - 元と複製が別インスタンスか - 循環で無限に探索しないか - すべての隣接関係を再現できるか 良い例: 初めて訪れたノードをMapへ登録してから、その隣接ノードを探索する。 避ける例: 訪問済み管理をせず、循環するグラフを再帰し続ける。 ## AIの回答に含めること - 解く課題を表す一文 - 確認できた事実、仮定、未確認事項 - 入力サイズと主な操作、その実行頻度 - 変更前後で守る振る舞い - 基準実装と候補ごとの時間・空間計算量 - 推奨案と、採用・不採用の理由 - テスト方法と測定方法 - 期待する利用者上の効果 - 追加される複雑さと適用限界 ## 実装を変更するときに行うこと 1. 対象コードと呼び出し元を確認する。 2. 現在の振る舞いをテストで固定する。 3. 最も単純な基準実装と、必要な場合だけ改善案を用意する。 4. データ構造を変更した場合は、順序、重複、同値性、空入力、境界値を再確認する。 5. 時間・空間計算量を比較する。 6. 性能改善が目的なら、同じ条件で変更前後を測定する。 7. 対象プロジェクトのテスト、Lint、ビルドを実行する。 8. 変更内容、検証結果、残るトレードオフを報告する。 ## AIが避けること - DSAを使うこと自体を目的に、必要のない複雑なデータ構造を導入する。 - O(1)、O(log n)などの表記だけで高速だと断定する。 - debugビルドや一回の測定から一般的な結論を出す。 - 平均値だけを示し、遅いフレームやばらつきを隠す。 - 順序、重複、同値性などの意味を確認せずコレクション型を変更する。 - 面接向けの用語を並べ、実際の課題、コード、テスト、測定を省略する。