Python

正の整数からなるリスト nums が与えられたとき、「桁数が奇数になっている要素」がいくつあるかを求める問題を考えてみましょう。 たとえば、入力が [1, 300, 12, 10, 3, 51236, 1245] の場合を確認してみます。 1 → 1桁（奇数）✓ 300 → 3桁（奇数）✓ 12 → 2桁（偶数）✗ 10 → 2桁（偶数）✗ 3 → 1桁（奇数）✓ 51236 → 5桁（奇数）✓ 1245 → 4桁（偶数）✗ この場合、該当する要素は 4 個なので、出力は 4 となります。 解き方のアプローチ この問題は、次の手順で解くことができます。 カウンター c を 0 で初期化す

Pythonでは、「メジャー.マイナー.パッチ」の形式で表現されたソフトウェアパッケージのバージョン番号を扱うことがあります。このとき、指定された新しいバージョン（newer）が、古いバージョン（older）よりも実際に新しいものかどうかを判定したいケースがあります。 例えば、older = 7.2.2、newer = 7.3.1 という入力が与えられた場合、newer の方が新しいため、出力は True になります。 解決のアプローチ この問題は、以下の手順で解くことができます。 older を「.」で分割し、メジャー・マイナー・パッチの各番号からなるリストに変換する newer も同様に

正の整数のリスト nums が与えられたとき、i < j を満たすインデックスの組 (i, j) のうち、nums[i] + nums[j] の合計が奇数になる「有効なペア」の数を求める問題を考えてみましょう。 例えば、入力が [5, 4, 6] の場合、出力は 2 になります。これは、[5, 4] と [5, 6] の2つのペアの合計（9 と 11）がどちらも奇数になるためです。 解法のアプローチ この問題は、以下の手順で効率的に解くことができます。 e := リスト nums から偶数のみを取り出した新しいリストを作成する (nums の要素数 − e の要素数) × e の要素数

アルファベット文字からなる文字列 s と整数 k が与えられたとします。このとき、s に含まれる文字だけを使って構成できる「長さ k の回文」の総数を求めます。同じ文字は何度でも繰り返し使用して構いません。例えば、入力が s = xy、k = 4 の場合、出力は 4 になります。これは、作成できる回文が [xxxx, yyyy, xyyx, yxxy] の 4 通りだからです。解法のアプローチこの問題は、回文の性質を利用すると非常にシンプルに解けます。長さ k の回文では、前半部分が決まれば後半部分は自動的に鏡像として決まるため、自由に選べるのは前半の文字だけです。さらに k が奇数の場合は、

パングラム（pangram）とは、英語のアルファベット26文字すべてが少なくとも1回は登場する文章のことです。本記事では、Pythonを使って、与えられた文字列 s がパングラムであるかどうかを判定するプログラムの実装方法を解説します。問題の概要ある文字列 s が文を表しているとします。このとき、英語のアルファベットのすべての文字が少なくとも1回以上使われているかどうかを確認する必要があります。例えば、入力が The grumpy wizards make toxic brew, for the evil queen and Jack の場合、出力は True になります。この文にはアルファベ

問題概要 バランスの取れた括弧「(」と「)」だけで構成された文字列 s が与えられたとします。この文字列を、それ以上分割できない単位ごとに、できるだけ多くのバランスの取れたグループへと分割することを考えます。 たとえば、入力が "(()())()(())" の場合、出力は ['(()())', '()', '(())'] になります。それぞれのグループは、それ自体で完結したバランスの取れた括弧列となっています。 解法のアプローチ この問題は、「現在読んでいる位置での括弧の深さ」を表すカウンタを1つ用意するだけで解くことができ

パスカルの三角形とはある数 n が与えられたとき、パスカルの三角形の n 番目(0始まり)の行を求めることを考えます。パスカルの三角形は、次のようなルールで作成できます。最上行は「1」のみで構成される2行目以降は、左上の数と右上の数を足し合わせた値が並ぶ具体的には、以下のような形になります。例えば入力が 4 の場合、出力は [1, 4, 6, 4, 1] となります。解法のアプローチこの問題は、以下の手順で解くことができます。n が 0 の場合 → [1] を返すn が 1 の場合 → [1, 1] を返すls を [1, 1]、temp を [1, 1] として初期化するi を 2 から n

文字列 s が1つのパスワードを表しているとします。このパスワードが所定の基準を満たしているかどうかを判定する必要があります。チェックすべきルールは以下の通りです。パスワードの長さは8文字以上20文字以下であること少なくとも1つの数字を含むこと少なくとも1つの小文字と1つの大文字を含むこと!#$%&\()*+,-./:;<=>?@[\\]^_`{|}~ のような特殊文字を少なくとも1つ含むことタブや改行など、上記以外の文字を含まないこと例えば、入力が @bCd12#4 の場合、すべての条件を満たしているため、出力は True になります。解決のアプローチこの問題を解くために

正の整数 n が与えられ、n は保有している金額を「セント」単位で表したものとします。このとき、人間が読みやすい通貨形式（3桁ごとのカンマ区切り＋小数点以下2桁）に整形した文字列を求めるのが本記事のテーマです。 例えば、入力が n = 123456 の場合、出力は 1,234.56 となります。 解法のアルゴリズム この問題は、数値を一度文字列に変換し、後ろから桁を区切りながらカンマを挿入していくことで解決できます。手順は以下の通りです。 n を文字列に変換して cents とする cents の桁数が 2 未満の場合は、「0.0」+ cents を返す cents の桁数がちょうど 2 の

この記事では、Pythonを使って「n人のプログラマーを、互いに隣り合わないように会場に着席させられるかどうか」を判定するアルゴリズムを解説します。これは配列の走査と貪欲法（グリーディ法）の基本的な考え方を学べる、定番の練習問題です。 問題の概要 ある数値 n は、会議（コンベンション）に参加しようとしているプログラマーの人数を表します。また、0と1からなるリスト convention が与えられます。 1 … その席にすでにプログラマーが座っている 0 … 空席である ここで重要なルールは「2人のプログラマーを隣同士の席に座らせてはいけない」というものです。この条件下で、n人全員が着席で

問題の概要すべて小文字で構成された単語のリストが与えられたとき、先頭の文字が同じである連続する部分リストの中で最も長いものの長さを求めることを考えます。例えば、入力が [she, sells, seashells, on, the, seashore] の場合、出力は 3 になります。これは、「she」「sells」「seashells」という3つの連続する単語がすべて同じ先頭文字「s」を持っているためです。解決のアプローチこの問題は、リストを一度走査しながら「現在注目している先頭文字」と「その文字が続いている長さ」を追跡することで効率的に解けます。具体的な手順は以下の通りです。最大長を記録す

Pythonで1からnの範囲のn+1個の数値から重複する要素を見つける方法長さ n+1 の数値リスト nums があるとします。これらの数値はすべて 1, 2, ..., n の範囲から選ばれています。鳩の巣原理(ピジョンホール原理)により、このリストには必ず重複が存在することが分かります。この重複する要素を見つけて返すのが、この問題の目的です。例えば、入力が [2, 1, 4, 3, 3] の場合、出力は 3 となります。解法のアプローチこの問題は、合計値の差を利用することで効率的に解くことができます。手順は以下の通りです。l := nums のサイズ(n+1 に相当)temp := l *

数値のリスト nums が与えられたとき、最初の要素と最後の要素が一致するサブリスト（部分リスト）の個数を求めることを考えます。 たとえば、入力が nums = [10, 15, 13, 10] の場合、答えは 5 になります。条件を満たすサブリストは次の5つです。 [10] [15] [13] [10] [10, 15, 13, 10] 解法のアプローチ この問題は、各要素の出現回数を数えて組み合わせの公式を適用することで、O(n) の計算量で効率的に解けます。手順は以下の通りです。 単一要素のサブリストは必ず条件を満たすため、初期値として num_sublists := len(n

2次元の行列が与えられ、matrix[i] にはコース i を受講するために必要な前提コース（履修条件）のリストが格納されているものとします。このとき、すべてのコースを受講することが可能かどうかを判定する必要があります。例えば、入力が matrix = [[1],[2],[]] の場合、出力は True になります。これは、コース 2 → コース 1 → コース 0 の順番で受講できるためです。この問題は、前提関係を有向グラフとみなし、深さ優先探索（DFS）によってサイクル（循環参照）が存在しないかを確認することで解けます。前提コース同士が循環していると、その環状の中にあるコースはどれも受講で

問題の概要同じ長さの2つの文字列 S と T が与えられたとき、両方の文字列を共通の位置で切断し、S の前半部分と T の後半部分をつなぎ合わせて回文（前から読んでも後ろから読んでも同じになる文字列）を作ることができるかどうかを判定します。例えば、入力が S = cat、T = dac の場合、出力は True になります。文字列を「c」+「at」と「d」+「ac」に分割すると、「c」+「ac」（つまり cac）が回文になるためです。アルゴリズムの手順この問題を解くためには、以下の手順に従います。n := 文字列 a の長さi := 0i < n かつ a[i] が b[n-i-1] と

問題の概要「a」= 1、「b」= 2、…「z」= 26 というアルファベットと数字の対応関係があるとします。このとき、エンコードされたメッセージ(数字列)が与えられれば、そのメッセージをデコードできる方法が何通りあるかを数えるのが本記事のテーマです。例えば、入力が message = 222 の場合、出力は 3 になります。これは次の3通りにデコードできるためです。b・b・b(2, 2, 2)b・v(2, 22)v・b(22, 2)解決のアプローチ:動的計画法(DP)この問題は動的計画法を用いることで効率的に解くことができます。各位置 i までの文字列についてデコード方法の総数を記録し、1文字

二分木が与えられたとき、値が偶数であるすべての葉（リーフ）ノードを繰り返し削除する問題を考えてみましょう。削除を続けた結果、根ノードだけが残り、その値が偶数であった場合は、根ノードも併せて削除します。例えば、入力が次のような二分木だったとします。この場合、出力は次のようになります。解き方のアプローチこの問題は、後順（post-order）に近い再帰処理を使うことでシンプルに解けます。子ノードを先に処理し、その結果を受けて親ノードを判定する流れです。具体的には以下の手順に従います。関数 solve() を定義します。引数としてルートノードを受け取ります。root が null（None）の場合は

問題概要 互いにアナグラム（同じ文字で構成される順列）の関係にある2つの文字列 S と T が与えられます。S に対して許されている操作は、「先頭または末尾の1文字を取り除き、文字列中の任意の位置に挿入する」というものです。この操作を繰り返して S を T に一致させるとき、必要となる最小の操作回数を求めます。 入出力の例 たとえば、入力が s = zyvxw、t = vwxyz の場合、出力は 3 になります。実際の操作手順は次のとおりです。 末尾の w を取り除き、v の直後に挿入 → zyvwx 先頭の z を取り除き、x の直後に挿入 → yvwxz 先頭の y を取り除き、x の

問題の概要友人であるアマル（Amal）とビマル（Bimal）が、numsという名前のソート済み数値リストを使ってゲームを行っているとします。各ターンでは、まずアマルが任意の3つの数値を選び、次にビマルがそのうちの1つを削除し、続いてアマルがさらに1つを削除します。リストは最初、奇数個の要素で構成されています。ここで、アマルはリストから重複要素をなくすために必要なターン数を最小化したいと考え、一方ビマルはターン数を最大化しようとします。両者が最適な戦略で行動するとき、このゲームが完了するまでに必要なターン数を求めるのが課題です。入出力例例えば、入力が nums = [1, 1, 2, 3, 3,

n × m の行列 Mat が与えられたとき、左上から右下へ向かう各対角線（斜め方向）に沿って要素を昇順に並べ替えることを考えます。つまり、すべての対角線上の要素がそれぞれ独立にソートされた状態にします。例えば、次のような入力行列があったとします。331122121112この場合、出力される行列は次のようになります。111112221233解決のためのアプローチこの問題は「同じ対角線上にある要素を一度取り出してソートし、元の位置に書き戻す」というシンプルな発想で解決できます。具体的には、以下の手順に従います。solve() というメソッドを定義します。引数として対角線の開始位置 si、sj と