Python

問題の概要 2つの整数 n と k が与えられたとします。ここで、1から n までの数字のリスト [1, 2, ..., n] を考え、このリストのすべての順列を辞書式順序で並べます。例えば n = 4 の場合、順列は次の24通りになります。 [1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321] この順列の中から k 番目の値を文字列として求めるのが本記事の目的

数値のリスト nums と整数 k が与えられたとき、長さが k 以上である任意の連続するサブリスト（部分配列）の中から、平均値が最大となるものを求める問題を考えます。 例えば、入力が nums = [2, 10, -50, 4, 6, 6]、k = 3 の場合を考えてみましょう。このとき出力は 5.33333333 になります。これは、サブリスト [4, 6, 6] の平均値 (4 + 6 + 6) ÷ 3 ≒ 5.333 が、条件を満たすすべての候補の中で最も大きいためです。 解法のアプローチ：二分探索とスライディングウィンドウ この問題は、平均値の候補範囲に対して二分探索（バイナリサーチ

問題の概要1が陸地、0が水を表す2次元のバイナリ行列(マトリックス)が与えられます。「島」とは、上下左右につながった1の集まりであり、周囲を水に囲まれた領域のことです。この問題では、最大で1つの水のセルを陸地のセルに変更できるという条件のもとで、作り出せる最大の島のサイズを求める必要があります。入力例101000110111この場合の出力は 7 になります。たとえば左端の2行目にある水のセルを陸地に変更すると、左上の小さな島(サイズ1)と下側の大きな島(サイズ5)がつながり、合計7の島が完成するからです。変更後の行列は次のようになります。101100110111アルゴリズムの考え方すべての水の

この記事では、PythonでLFU(Least Frequently Used:最低頻度使用)キャッシュを実装する方法を解説します。LFUキャッシュは、アクセス頻度が最も低いデータから優先的に追い出す(evictする)キャッシュ方式で、LRU(Least Recently Used)と並んでよく知られるアルゴリズムです。 LFUキャッシュに必要な操作 LFUキャッシュ用のデータ構造には、次の2つの操作が必要です。 get(key) … キーがキャッシュに存在すればその値を返し、存在しない場合は -1 を返します。 set(key, value) … キーがまだ存在しない場合に、値を挿入(ま

数値のリスト nums が与えられたとき、リスト内の任意の数と、それより小さい直近の数との間の最大差を求めることを考えます。この問題は、ソートに頼らず線形時間 O(n) で解くことが目標です。 たとえば、入力が nums = [14, 2, 6, 35, 12] の場合、出力は 21 になります。これは 35 と 14 の差が最も大きいためです。 解法のアプローチ：バケット分割の活用 この問題を線形時間で解く鍵となるのは「鳩の巣原理」に基づくバケット分割です。要素数を n、値の範囲を [min_val, max_val] とすると、最大差は少なくとも (max_val − min_val)

問題の概要 2次元行列とある値 k が与えられたとき、「要素の合計が k 以下」となる長方形領域の中で、合計が最大になるものを見つける問題を考えます。 例として、次のような行列を入力とした場合をみてみましょう。 5-2710 k = 15 のとき、出力は 12 になります。これは、縦方向に [5, 7] の長方形を選ぶことで合計が 12 となり、15 以下の条件を満たす中で最大の値を得られるためです。 解法のアルゴリズム この問題は、行の組み合わせを固定しながら累積和と集合を活用することで効率的に解けます。手順は以下の通りです。 n を行列 a の行数、m を列数とします ans を十分に

無限に広がる水のグリッドがあるとします。このグリッドに対して、陸地のブロックを1つずつ追加していきます。座標のリスト land_requests が与えられ、各座標は [r, c] の形式で表されます(r は行、c は列を意味します)。求めたいのは、各ブロックを追加した直後の時点で存在する島の数を要素とするリストです。例えば、入力が land_requests = [[1, 1], [2, 4], [1, 2], [1, 4], [1, 3]] の場合、出力は [1, 2, 2, 2, 1] となります。なぜ [1, 2, 2, 2, 1] になるのか[1, 1] を追加 → 島は1つ[2,

問題概要この記事では、2次元マトリックス(グリッド)を対象に、2人のコイン収集者が集められるコインの総数の最大値を求める問題を解説します。マトリックスの各セルにはそのセルにあるコインの枚数が格納されており、1人目の収集者は左上の角、2人目の収集者は右上の角からスタートします。2人は以下のルールに従って移動します。セル (i, j) にいる収集者は、次の行にある (i + 1, j − 1)、(i + 1, j)、(i + 1, j + 1) のいずれかのセルへ移動できます。セルに到達した時点で、そのセルのコインをすべて回収し、セルは空になります。収集者は移動せず同じ列にとどまることも可能ですが

問題の概要 数値のリスト nums が与えられていると仮定します。インデックス i からは、移動先がリストの範囲内に存在する限り、i + numbers[i] または i − numbers[i] の位置へジャンプすることができます。ここで求めたいのは、入力の順序を保ちながら、異なるパリティ（偶数・奇数の区別）を持つ別の値に到達するために必要な最小ジャンプ回数です。もし異なるパリティの数値にどうしても到達できない場合は、−1 を返します。 たとえば、入力が numbers = [7, 3, 4, 5, 6, 9, 6, 7] の場合、出力は [-1, 1, 2, -1, -1, -1, 1,

問題の概要 数値のリストが与えられたとき、「シーケンスから1つの数値を削除すると、残りのすべての数値が同じ回数だけ出現する」という条件を満たす、最長のシーケンスの長さを求める問題を考えてみましょう。 たとえば、入力が numbers = [2, 4, 4, 7, 7, 6, 6] の場合、出力は 7 になります。これは、先頭の 2 を削除すれば [4, 4, 7, 7, 6, 6] となり、4・7・6 がそれぞれ2回ずつ出現して条件を満たすためです。 解法のアプローチ この問題は、リストを先頭から順に走査しながら、各時点での出現頻度の状態を効率よく管理することで解けます。まず、次のデータ構造

少し変わったルールのゲームを考えてみましょう。3つの整数 n、k、h が与えられます。ゲームは0ポイントからスタートし、各ターンごとに1からhまでの整数をランダムに1つ選び、その数だけポイントを獲得します。合計スコアがkポイント以上に達した時点でゲームは終了です。このとき、最終的なポイントがn以下になる確率を求めます。なお、どの数値も選ばれる確率はすべて等しいものとします。 たとえば、入力が n = 2、k = 2、h = 10 の場合、出力は 0.11 になります。 解き方のステップ この問題は、現在のポイント数を状態とする再帰関数 dp() を使うことで効率的に解けます。手順は以下の通りで

1次元の道路を車で走行している状況を考えてみましょう。車の現在位置は position = 0、速度は speed = 1 です。この車に対しては、以下の2つの操作のどちらでも実行できます。 アクセル（加速）: position := position + speed、speed := speed * 2 バックギア（逆走）: speed > 0 の場合は speed := -1、それ以外の場合は speed := 1 このとき、目標地点（フィニッシュライン）に到達するまでに必要な最小の操作回数を求めるのが本記事の課題です。 たとえば、入力が target = 10 の場合、答えは

問題概要小文字の英字と丸括弧「(」「)」を含む文字列 s が与えられます。このとき、括弧で囲まれた部分文字列を再帰的に反転し、最終的な文字列を返すプログラムを作成します。たとえば、入力が s = back(aps)ce の場合、括弧内の「aps」が反転されて「spa」になり、出力は「backspace」となります。解法の考え方この問題は、次の2つの処理に分けて考えるのがポイントです。前処理：スタックを使い、開き括弧「(」と閉じ括弧「)」のペアとなるインデックス同士を事前に記録します。走査：進行方向 dir（+1 または -1）を持ちながら文字列を走査する trav() 関数を定義します。括弧に

問題の概要2つの文字列 s と t が与えられたとき、s の中から「t が部分列（subsequence）として含まれる」最短の部分文字列を見つけることを考えます。該当する部分文字列が存在しない場合は空文字列を返し、最短の候補が複数ある場合は最も左側にあるものを採用します。例えば、入力が s = abcbfbghfb、t = fg の場合、出力は fbg となります。解法のアルゴリズムこの問題は動的計画法（DP）を用いて効率的に解くことができます。手順は以下の通りです。N := 文字列 S の長さとするdp := 長さ N のリストを作成し、すべて無限大（INF）で初期化するi を 0 から

Pythonでは、CSVやJSONなどさまざまな形式のデータソースからデータを受け取ることが多く、それらはリストや辞書といったPythonオブジェクトへと変換できます。しかし、pandasなどのライブラリを使って計算や分析を行うには、そのデータをデータフレーム(DataFrame)に変換する必要があります。この記事では、「ネストした辞書」を要素として持つPythonのリストを、pandasのデータフレームへ変換する手順を解説します。変換の基本的な流れまず、ネストした辞書のリストから各行のデータを抽出します。次にforループを使って、あらかじめ空で作成しておいた新しいリストへ行データを追加してい

KivyとはKivyは、マルチタッチアプリに代表される革新的なユーザーインターフェースを持つアプリケーションを迅速に開発するための、オープンソースのPythonライブラリです。Androidアプリはもちろん、デスクトップアプリケーションの開発にも幅広く活用されています。本記事では、その中でも「AnchorLayout（アンカーレイアウト）」を使ったウィジェットの配置方法について、具体的なサンプルコードとともに解説します。AnchorLayoutの基本AnchorLayoutを使用すると、ウィジェットをレイアウト領域の端（上下左右）や中央に簡単に配置できます。この機能は kivy.uix.anc

Kivyは、マルチタッチアプリなど革新的なユーザーインターフェースを備えたアプリケーションを迅速に開発するために設計された、オープンソースのPythonライブラリです。Androidアプリはもちろん、WindowsやmacOSなどのデスクトップアプリケーション開発にも幅広く活用されています。本記事では、BoxLayoutウィジェットを使用して、異なる向き（orientation）や色を持つ複数のボタンを配置する方法を、具体的なサンプルコードとともに解説します。BoxLayoutの基本的な考え方以下のコードでは、まず縦方向（vertical）の外側のボックス（outerBox）を作成します。次に

Kivyは、マルチタッチアプリなど革新的なユーザーインターフェースを持つアプリケーションを迅速に開発するためのオープンソースのPythonライブラリです。Androidアプリだけでなく、デスクトップアプリケーションの開発にも広く活用されています。本記事では、Kivyにおいてボタンが押されたときにイベントを発生させる方法について解説します。実装例：ボタンとラベルの連動以下の例では、水平方向のBoxLayoutの中にボタンとラベルを1つずつ配置しています。まず、ボタンとラベルにそれぞれ初期テキストを設定します。その後、ボタンをクリックした際に発火するイベントを作成し、このイベントによってボタンとラ

メールやテキストデータを扱っていると、必ずしも通常のASCII文字だけではないデータに遭遇することがあります。例えば、英語以外の言語で書かれたメールがその代表例です。Pythonには、こうした特殊な文字を扱うための仕組みとして、MIME(Multipurpose Internet Mail Extensions)に基づいたモジュールが用意されています。本記事では、メール本文や単純な文字列入力に含まれるそうした文字を、エンコード・デコードする方法を解説します。 emailパッケージを使用する方法 Python標準ライブラリのemailパッケージには、mimeモジュールとcharsetモジュールが

ファイル転送の際には、暗号化や圧縮、あるいは異なるOSやファイル読み込みプログラムでの処理に対応するなど、さまざまな理由からファイルのエンコード・デコードが必要になることがよくあります。Python標準ライブラリのuuモジュールを使えば、こうしたエンコードとデコードを簡単に行うことができます。ファイルのエンコードここでは、以下の画像ファイルを使用して、エンコードを行い、その後デコードして元の画像を復元してみます。次のプログラムでは、encode関数を使って指定した画像をエンコードし、エンコード後のファイル内容を読み出して表示しています。サンプルコードimport uu infile = &q