Python

リストの中にリストが格納された rooms というデータがあるとします。各インデックス i は部屋番号を表し、rooms[i] にはその部屋から他の部屋を開けるための鍵のリストが入っています。部屋0は最初から開いており、自分はそこにいる状態です。それ以外の部屋はすべて施錠されています。開いた部屋の間は自由に移動できるものとして、すべての部屋を開けられるかどうかを判定する必要があります。例えば、入力が rooms = [[2, 0], [3], [1], []] の場合、出力は True になります。部屋0からスタートし、持っている鍵2を使って部屋2へ移動できます。部屋2には鍵1があるので部屋1

n×n の行列が1つのチェス盤を表していると考えます。行列には「1」と「0」が含まれており、「1」はクイーンが置かれているセル、「0」は空のセルを表します。ここで、この盤面がNクイーン問題の有効な解となっているかどうかを判定する必要があります。 Nクイーン問題において有効な解とは、どの2つのクイーンも互いに攻撃し合っていない盤面のことです。つまり、同じ行・同じ列・同じ斜め線上に複数のクイーンが存在してはいけません。 例として、次のような入力が与えられた場合を考えてみましょう。 この場合、出力は True になります。 解法のアプローチ この問題を解くためには、以下の手順に従います。 n :

ここでは、2〜9の数字のみを含む文字列が与えられたとき、その数字列から生成されうるすべての文字の組み合わせを求める方法を解説します。数字と文字の対応関係は、一般的な電話機のテンキーと同じです。なお、「1」にはいくつかの記号が割り当てられていますが、英字は割り当てられていません。12a b c3d e f4g h i5j k l6m n o7p q r s8t u v9w x y z*0#たとえば、入力として「49」が与えられた場合、出力される可能性のある文字列は次の12通りになります。[gw, gx, gy, gz, hw, hx, hy, hz, iw, ix, iy, iz]解法のアプロー

問題概要ある企業の日々の株価が、時系列順に並んだリストとして与えられているとします。ここで、元のリストと同じ長さの新しいリストを作成することを考えます。新しいリストのインデックス i の値は、「その日の株価を上回る価格が現れるまでに何日待てばよいか」という最小日数を表します。もし将来どの日を見ても利益を得られる見込みがない場合は、その値は 0 とします。例えば、入力が prices = [4, 3, 5, 9, 7, 6] の場合、出力は [2, 1, 1, 0, 0, 0] となります。インデックス 0(価格 4):2 日後に価格 5 となり利益を得られますインデックス 1(価格 3):1

「hh:mm」形式の24時間表記の時刻文字列が与えられたとき、その文字列に含まれる数字を再利用して作ることができる、最も近い次の時刻を求める問題を考えます。ここで重要なのは、与えられた文字列内の各数字は何度でも再利用できるという点です。 例えば、入力が s = 03:15 の場合、出力は 03:30 となります。これは、与えられた数字（0、3、1、5）だけを使って作れる時刻の中で、元の時刻に最も近い次の時刻が 03:30 だからです。 解法のアプローチ この問題は、バックトラッキング（探索の枝戻り法）を使って、使用可能な数字のすべての組み合わせを生成することで解けます。ただし、時刻として有効

文字列のリストが与えられたとき、そのリスト内の他の単語を連結することで作られる単語がいくつあるかを求める問題を考えてみましょう。連結の際には単語を何度でも再利用でき、連結回数にも制限はありません。 例えば、入力が words = [hello, world, helloworld, famous, worldfamous, programming] の場合を考えます。このとき出力は 2 になります。なぜなら、「helloworld」は「hello」と「world」の連結であり、「worldfamous」は「world」と「famous」の連結で作られているからです。 解決のためのアプローチ

単語のリスト words と文字列 letters が与えられたとき、letters に含まれる文字を並べ替えて作ることができる「最長の単語」の長さを求める問題を考えてみましょう。 この問題には2つのポイントがあります。 letters にはアスタリスク(*)が含まれることがあり、これは任意の1文字として扱えるワイルドカードです。 与えられた文字をすべて使い切る必要はありません。 たとえば、入力が次のような場合を考えます。 words = [prince, rice, price, limit, hello] letters = *r**ce* このとき出力は 6 になります。ワイルドカー

問題概要 二分木が与えられたとき、「左の子 → 右の子 → 左の子…」のように左右交互にたどりながら下へ進む最長のパス(交互パス)の長さを求めます。 例として、次のような二分木が入力されたとします。 この場合、交互パスは [2, 4, 5, 7, 8] となるため、出力は 5 になります。 解き方のステップ この問題を解くには、以下の手順に従います。 ルートが null(空)の場合は 0 を返します。 dfs() 関数を定義します。この関数は node(現在のノード)、count(現在のパス長)、flag(次に進むべき方向)を引数に取ります。 node が null でない場合: f

文字列 s と整数 k が与えられたとき、s の各文字を順に取り出し、左上から右下へ斜めに進んで k 行目に達したら、今度は右上へ折り返す――この動きを繰り返してできる「ジグザグ型」の文字列を作成する方法を解説します。 たとえば、入力が s = ilovepythonprogramming、k = 5 の場合、出力は次のようになります。 解法のアプローチ この問題は、いわゆる「蛇行（ジグザグ）パターン」への文字列変換です。各行にどの文字がどの位置に来るかを記録しておき、最後に行単位で組み立てるのがポイントです。具体的には、次の手順で解きます。 初期化：各行の文字情報を格納する辞書 line

リストのリスト ports が与えられているとします。ここで ports[i] は、港 i が接続されている港の一覧を表します。さらに別のリストのリスト shipments もあり、その各要素は [i, j] という形式のシーケンスで、「港 i から港 j への出荷依頼」を意味します。港 i から港 j へ出荷するコストは、2つの港間の最短経路の長さとして定義されます。このとき、すべての出荷を完了させるために必要な総コストを求めるのが課題です。たとえば、入力が次のような場合を考えてみましょう。ports = [[1, 4],[2],[3],[0, 1],[]] shipments = [[1,

問題の概要有向グラフの隣接リストが与えられます。各インデックス i のリストには、ノード i から直接接続されているノードの一覧が格納されています。さらに、探索対象となる値(target)も与えられます。この課題では、target を含むサイクル(閉路)の中で最も短いものの長さを求めます。該当するサイクルが存在しない場合は -1 を返してください。具体例例えば、次のようなグラフが与えられたとします。graph = [[1, 4], [2], [3], [0, 1], []]target = 3 の場合、出力は 3 になります。これは、ノード 1 → 2 → 3 → 1 というサイクルが存在する

数値のリスト nums があるとします。各要素は、一緒にスカイダイビングをしたいグループの人数を表しています。また、もうひとつの値 k は、スカイダイビングの申し込みが可能な日数を表します。ここで、すべてのリクエストを k 日以内に処理できるようにするために必要な、飛行機の最小定員を求めます。ただし、リクエストは与えられた順番どおりに処理しなければならず、飛行機は1日に1回しか飛べないものとします。たとえば、入力が nums = [16, 12, 18, 11, 13]、k = 3 の場合、出力は 28 になります。これは、28人乗りの飛行機を使えば、グループを [16, 12]、[18]、[

問題の概要 数値のリスト nums が与えられ、それぞれの要素はロケットの「向き」と「大きさ」を表しているとします。正の整数は右方向への移動、負の数は左方向への移動を意味し、数値の絶対値がロケットの大きさを表します。 2つのロケットが衝突したときのルールは以下の通りです。 大きさが異なる場合：小さい方のロケットが破壊され、大きい方のロケットはそのまま進み続けます 大きさが同じ場合：2つのロケットは互いに破壊し合います 同じ方向に移動している場合：速度が同じであるため、衝突することはありません このとき、すべての衝突が完了した後のロケットの状態を求めるのが本記事のテーマです。 たとえば、入

2次元のバイナリ行列(0と1のみで構成される行列)が与えられたとき、すべての要素が1である正方形の部分行列が合計いくつ含まれているかを求める問題を考えてみましょう。入力例11101110111000001011この場合の出力は 17 となります。内訳は、1×1の正方形が12個、2×2の正方形が4個、そして3×3の正方形が1個存在するためです。解き方:動的計画法(DP)この問題は、動的計画法を用いることで効率的に解けます。基本的な考え方は、各セルについて「そのセルを右下の角とする最大の正方形の一辺の長さ」を順番に計算していくというものです。重要なポイントとして、あるセルに記録された値は「その位置

問題の概要数値のリスト「pushes」と、別の数値リスト「pops」が与えられたとき、これがスタックに対するプッシュ(push)とポップ(pop)操作の正当なシーケンスであるかどうかを判定する必要があります。たとえば、入力が pushes = [1, 2, 5, 7, 9]、pops = [2, 1, 9, 7, 5] の場合、出力は True になります。これは、最初に [1, 2] をプッシュしてから両方をポップし、続いて [5, 7, 9] をプッシュしてすべてをポップできるためです。解法のアプローチこの問題は、実際にスタックをシミュレートすることで解決できます。以下の手順に従います。s

等間隔の時間ごとに記録された車の位置を表す数値のリストが与えられたとき、車が一定の速度で走行していた最も長い連続区間（サブリスト）のサイズを求める問題を考えてみましょう。例えば、入力が positions = [0, 4, 8, 12, 6, 4, 0] の場合、出力は 4 になります。これは部分リスト [0, 4, 8, 12] の間、各ステップでの移動距離が常に「4」で一定だからです。解法のアプローチこの問題は、隣接する2点間の移動距離を順番に比較していくことで解決できます。具体的な手順は以下の通りです。変数 j = 1 で走査を開始します。最大カウント max_cnt = 0、現在のカウ

ステップ数とは何かある数値 n が与えられたとき、n桁のステップ数（Stepping Number）の個数を求める問題を考えてみましょう。ステップ数とは、隣り合うすべての桁同士の絶対差がちょうど1になる数のことです。例えば「123」は隣接する桁が 1→2→3 とすべて1ずつ増えているためステップ数ですが、「124」は 2→4 の差が2になるためステップ数ではありません。また、答えが非常に大きくなる可能性があるため、結果は 10^9 + 7 で割った余りとして返します。入出力の例入力が n = 2 の場合、出力は 17 になります。これは、2桁のステップ数が以下の17個存在するためです。12,

それぞれの文字列が「A」と「B」の2種類の文字だけで構成された文字列のリストがあるとします。ここに、2つの整数値 a と b が与えられます。求めたいのは、生成できる文字列の最大数です。ただし、「A」は合計で最大 a 個まで、「B」は合計で最大 b 個までしか使用できず、一度使った文字を再利用することはできません。たとえば、入力が strings = ["AAABB", "AABB", "AA", "BB"]、a = 4、b = 2 の場合、出力は 2 になります。「A」を4個、「B」を2個消費して ["

問題概要 数値のリスト nums が与えられ、各数値はある候補者に対する1票を表しているとします。この中から、全投票数 n の3分の1（n / 3 の小数点以下切り捨て）より多くの票を獲得した候補者のIDを、昇順で求める必要があります。 例えば、入力が nums = [3, 2, 6, 6, 6, 6, 7, 7, 7, 7, 7] の場合、出力は [6, 7] になります。これは、候補者6と候補者7がそれぞれ全投票の約40%を獲得しており、基準となる33%を上回っているためです。 解法のアプローチ この問題は、以下の手順で解くことができます。 結果を格納するための空の集合 ans を用意

2つの文字列 source(ソース)と target(ターゲット)が与えられます。source の部分列を何度でも切り出して連結し、target とまったく同じ文字列を作りたいとき、必要となる部分列の最小個数を求めます。どのように組み合わせても target を作れない場合は -1 を返します。 たとえば source = "xyz"、target = "xyzyzz" の場合、答えは 3 になります。"xyz" + "yz" + "z" のように3つの部分列を連結すると target と一致す