Python

問題概要2つの文字列 p と q、および数値 r が与えられたとき、p に含まれる各文字をアルファベット順に時計回りへ最大 r 回までシフトすることで、p を q に変換できるかどうかを判定するプログラムを作成します。例えば、「c」は時計回りに2回シフトすると「e」になります（c → d → e）。入力例と出力例入力が p = abc、q = ccc、r = 3 の場合を考えてみましょう。「a」を時計回りに2回シフトすると「c」になる「b」を時計回りに1回シフトすると「c」になる合計のシフト回数が3回で、許容される上限 r = 3 以内に収まるため、出力は True となります。解法のアプロー

問題の概要二分探索木（BST：Binary Search Tree）と、探索対象となる値 val が与えられたとき、その値が木の中に存在するかどうかを判定するプログラムを作成します。例えば、次のような二分探索木があったとします。このとき val = 7 とすると、7は木の中に存在するため、出力は True になります。アルゴリズムの手順BSTの性質を利用すると、効率的に値を探索できます。手順は以下の通りです。関数 solve() を定義します。引数として root（現在のノード）と val を受け取ります。root が null（None）の場合は False を返します。root のデータが

問題の概要 2つの小文字からなる文字列 s と t が与えられたとします。このとき、s 内の各文字を別の文字(同じ文字でも可)へ1対1対応でマッピングすることで、s を t に変換できるかどうかを判定するのが本記事のテーマです。なお、文字の並び順は変更しないものとします。 例えば、入力が s = papa、t = lili の場合、出力は True になります。これは「p → l」「a → i」というマッピングを作成できるためです。 逆に、同じ文字が異なる文字にマッピングされようとした場合(例えば「p」が一度「l」に対応したのに、後で「m」に対応しようとする場合)や、異なる文字が同じ文字に重複

二分木が与えられたとき、ツリー内の任意のレベルにおける最大幅を求めることを考えます。ここでいう「レベルの幅」とは、そのレベルにおいて最も左端にあるノードと最も右端にあるノードの間に含まれるノード数のことです。例えば、次のような二分木が入力として与えられた場合を考えてみましょう。この場合、出力は 2 となります。解決のための手順この問題を解くために、以下の手順に従います。各深さにおける位置の最小値と最大値を保持するマップ d を作成します。初期値は、最小値を無限大（∞）、最大値を 0 とします。関数 dfs() を定義します。この関数は引数として root、pos := 0、depth := 0

問題の概要 2つの文字列 s、t と正の整数 n が与えられたとします。このとき、次のルールで定義される数列 A の第 n 項を求める必要があります。 A[0] = s A[1] = t n が偶数のとき：A[n] = A[n-1] + A[n-2] n が奇数のとき：A[n] = A[n-2] + A[n-1] ここで「+」は文字列の連結を表します。ポイントは、添字の偶奇によって連結する順序が入れ替わる点です。 具体例 s = a、t = b の場合、数列 A は次のように生成されます。 A[0] = a A[1] = b A[2] = ba（b + a） A[3] = bba（b

問題の概要2つの文字列 s と t が与えられたとき、t を s の部分文字列にするために必要な最小の操作回数を求めます。ここでいう1回の操作とは、「s 内の任意の位置を選び、その位置の文字を任意の別の文字に変更する」ことを指します。例えば、入力が s = abbpqr、t = bbxy の場合、出力は 2 になります。これは、s の部分文字列 bbpq に着目し、p を x に、q を y に変更することで t = bbxy と一致させられるためです。解法のアプローチこの問題はスライディングウィンドウ（全開始位置の走査）を使うことで簡単に解けます。s の中で長さ k（= t の長さ）に等しい

ある数値 num が与えられたとき、その各桁の数字をすべて足し合わせた合計を求めます。ここでは、文字列に変換せず、数値演算だけで解く方法を紹介します。たとえば、入力が num = 512 の場合、5 + 1 + 2 = 8 となるため、出力は 8 になります。解き方の手順合計を格納する変数 sum を 0 で初期化します。num が 0 になるまで、次の処理を繰り返します。sum に「num を 10 で割った余り」(最下位の桁)を加算します。num を「10 で割った商」(整数)で更新します。繰り返しが終わったら sum を返します。アルゴリズムのポイントこの手法では、「10 で割った余り」

数値のリスト nums ともう一つの数値 k が与えられたとき、リスト内の任意の2つの数値を足した合計が k と一致するかどうかを判定するプログラムを作成します。ただし、同じ要素を2回使用することはできません。また、数値には負の数や0が含まれる場合もあります。例えば、入力が nums = [45, 18, 9, 13, 12]、k = 31 の場合、18 + 13 = 31 となるため、出力は True になります。解法のアプローチこの問題は「セット（集合）」を使うことで効率的に解けます。各数値に対して、それとペアになるべき値（k - num、いわゆる補数）を事前にセットへ記録しておき、後から

問題概要 文字列 s が与えられたとき、その文字列が回文（パリンドローム）であるかどうかを判定します。回文とは、前から読んでも後ろから読んでも同じになる文字列のことです。 たとえば、入力が s = racecar の場合、「racecar」を逆から読んでも「racecar」であるため、出力は True になります。 解法のアプローチ この問題は以下の手順で解くことができます。 文字列 s を反転したものを t とする t が s と一致する場合は True を返す そうでない場合は False を返す Pythonではスライス記法 [::-1] を使うことで、文字列を簡単に反転できます。

問題の概要 2つの整数 start と end(start < end)が与えられます。次の2種類の操作のみを使って start を end に変換するとき、必要な操作の最小回数を求めるプログラムを作成しましょう。 数値に 1 を加える(インクリメント) 数値に 2 を掛ける 例として、start = 5、end = 11 の場合を考えます。5 に 2 を掛けて 10 とし、そこへ 1 を加えれば 11 になるため、答えは 2 回となります。 解き方のアプローチ この問題は、start から順に操作を試すよりも、end から逆算していく貪欲法(グリーディ法)が有効です。end が偶

問題の概要タスクのリストと人のリストが与えられたとします。tasks[i] は i 番目のタスクを実行するために必要な体力（強さ）を表し、people[i] は i 番目の人が持っている体力を表します。ここで、「1人は最大でも1つのタスクしか担当できない」という条件のもとで、完了できるタスクの総数を求める必要があります。例えば、入力が tasks = [4, 3, 9, 15]、people = [10, 5, 3, 2] の場合、出力は 3 になります。これは、1人目がタスク「9」を、2人目がタスク「4」を、3人目がタスク「3」をそれぞれ実行でき、4人目はどのタスクも実行できないためです。解

問題の概要 文字列 s が、エディタに入力された一連の文字を表しているとします。ここで、記号「<-」はバックスペース（直前の1文字を削除する操作）を意味します。このとき、すべての入力処理が完了した後のエディタの最終的なテキスト（現在の状態）を求めるのが課題です。 たとえば、入力が s = ilovepython<-<-ON の場合、出力は ilovepythON になります。「ilovepython」と入力した直後にバックスペースが2回押されているため、末尾の2文字「on」が削除され、その後「ON」が新しく入力されるためです。 解決のためのアプローチ この問題は、リストをス

3つの数 x、y、z が与えられたとき、それらの積を求める問題を考えてみましょう。ただし、同じ値が2つ以上現れた場合は、その値を計算の対象から除外します。たとえば、入力が x = 5、y = 4、z = 2 の場合、3つの数はすべて異なるため、出力は 5 * 4 * 2 = 40 となります。解き方のアプローチこの問題は、集合（set）を2つ使うことでシンプルに解決できます。1つ目の集合は「これまでに見た値」を記録し、2つ目の集合は「重複しているため除外すべき値」を記録します。temp_set := 新しい空の集合（出現した値を記録）remove := 新しい空の集合（重複した値を記録）[x,

テプリッツ行列とは？ある行列 M が与えられたとき、それがテプリッツ行列（Toeplitz matrix）であるかどうかを判定することを考えます。テプリッツ行列とは、左上から右下へ向かうすべての対角線（斜めの並び）上の要素が同じ値であるような行列のことです。例として、次のような入力行列を考えてみましょう。726372537この行列では、どの対角線を見ても値が一定になっています。たとえば「7 → 7 → 7」「2 → 2」「3 → 3」といった具合です。したがって、この場合の出力は True となります。判定アルゴリズムの考え方テプリッツ行列の性質を利用すると、判定は非常にシンプルです。各要素は

行列の転置とはn × n の行列 M が与えられたとき、その転置行列（transpose）を求めることを考えます。転置行列とは、行と列のインデックスを入れ替えた行列のことで、形式的には、すべての行番号 r と列番号 c に対して次の関係が成り立ちます。matrix[r][c] = matrix[c][r]つまり、元の行列の r 行 c 列にある要素は、転置後の行列では c 行 r 列へと移動します。入力例726372537出力例（転置行列）735273627解法のアプローチこの問題は、以下の手順に従って解くことができます。結果を格納するための新しいリスト M を用意します。カウンター trac

問題の概要数値 n が与えられたとき、n 段の階段を表す文字列を作成することを考えます。文字列内の各行は改行文字（\n）で区切られます。例えば、入力が n = 5 の場合、出力は次のようになります。    *    **   ***  **** *****解法のアプローチこの問題は、各行ごとに「空白の数」と「星（*）の数」を計算して文字列を組み立てることで解けます。具体的には、i 行目（0始まり）では空白が (n - i - 1) 個、星が (i + 1) 個必要になります。手順は以下の通りです。空の文字列 s を用意します。i を

ある整数 n が与えられたとき、その素因数が 2・3・5 のみで構成されているかどうかを判定する問題を考えてみましょう。この条件を満たす正の整数は「醜い数（Ugly Number）」と呼ばれます。 例えば、入力が n = 18 の場合を考えます。18 の素因数は 2 と 3 だけなので、出力は True となります。 アルゴリズムの手順 この問題は、次の手順で解くことができます。 n < 0 の場合は False を返します。 チェック対象の因数として [2, 3, 5] のリストを用意します。 各因数 i について、n が i で割り切れる間、n を i で割り続けます。 最終的に

「a」と「b」のみで構成された文字列 s があるとします。このとき、「a」はそのまま「a」のままでもよいし、「b」に変換してもかまいません。一方、「b」は一切変更できません。この条件のもとで、作成できるユニークな文字列の総数を求めるのが本問題の目的です。問題の例たとえば、入力が s = baab の場合、出力は 4 になります。これは、以下の4種類の文字列を作成できるためです。baab（元のまま）babbbbabbbbb解法のアプローチこの問題は非常にシンプルな数学的性質を利用して解けます。「a」はそれぞれ独立に「a」または「b」の2択を選べるため、文字列中の「a」の個数を n とすると、組み

ソートされた数値リスト nums が与えられたとき、そのリストに含まれる一意な要素（重複を除いた値）の個数を求める問題について解説します。 例えば、入力が nums = [3, 3, 3, 4, 5, 7, 7] の場合、一意な数値は [3, 4, 5, 7] となるため、出力は 4 になります。 解決のアプローチ この問題は、セット（集合）を使うことでシンプルに解決できます。手順は以下の通りです。 空のセット s とカウンター cnt = 0 を用意する nums の各要素 i について以下を繰り返す i がまだセット s に存在しない場合、i をセットに追加し、cnt を1増やす

問題の概要文字列のリストとして与えられたUnix形式のパスについて、その解決済み（正規化）の結果を求めることを考えます。Unixでは、「..」はひとつ前の（親）ディレクトリへ移動することを表し、「.」は現在のディレクトリに留まることを表します。ここでいう「解決」とは、これらの特殊な記号を評価し、最終的にどのディレクトリにいるのかを求める処理のことです。たとえば、入力が次の場合を考えてみましょう。path = [usr, .., usr, ., local, etc, foo]このパスは「/usr/../usr/./local/etc/foo」を表しており、解決すると「/usr/local/et