Python

問題概要単語のリストと、スペースを含まない文字列 s が与えられたとき、その文字列をリスト内の単語の組み合わせに分解できるかどうかを判定します。たとえば、words = [love, python, we, programming, language]、s = welovepythonprogramming の場合、「we love python programming」というように分解できるため、出力は True になります。解法のアプローチこの問題は、再帰（バックトラッキング）を用いて解くことができます。具体的な手順は以下の通りです。words を、重複のない単語からなるセット（set）に

問題の概要時系列順に並んだ企業の株価を表す数値リスト prices が与えられたとします。このとき、買いと売りを合わせて最大2回まで行えるという条件のもとで、得られる利益の最大値を求める必要があります。なお、取引は必ず「先に買って、後で売る」という順序で行わなければなりません。例えば、入力が prices = [2, 6, 3, 4, 2, 9] の場合、出力は 11 になります。これは、最初に価格2で購入して6で売却し、その後再び価格2で購入して9で売却することで、(6−2) + (9−2) = 11 の利益を得られるためです。解法のアプローチこの問題は、4つの状態変数を使って動的に最適値を

問題の概要数値のリスト nums と整数 k が与えられているとします。nums[i] の各要素は、インデックス i に着地したときにかかるコストを表しています。プレイヤーはインデックス 0 からスタートし、nums の最後のインデックスを目指します。各ステップでは、現在いる位置 X から、最大 k ステップ先までの任意の位置へジャンプすることができます。ゴールである最後のインデックスに到達するまでに支払うコストの合計を最小化したい場合、その最小値はいくつになるでしょうか?入力例たとえば、nums = [2, 3, 4, 5, 6]、k = 2 という入力が与えられたとします。このとき、出力は

時系列順に並んだ企業の株価リスト nums と、売買の最大回数 k が与えられているとします。このとき、最大で k 回の買いと売り(必ず「買う→売る→買う→売る」の順序を守る)から得られる最大利益を求めるのが本記事の目的です。例えば、prices = [7, 3, 5, 2, 3]、k = 2 という入力の場合、出力は 3 になります。これは、3 で買って 5 で売り、その後 2 で買って 3 で売ることで、利益 (5 − 3) + (3 − 2) = 3 を得られるためです。解法のアプローチこの問題は動的計画法(DP)の考え方を使って解くことができます。手順は以下の通りです。関数 dp(i,

ここでは、加算（+）、減算（-）、乗算（*）、除算（/）を含む数式を表す文字列が与えられる問題を考えます。ただし「/」は整数除算（小数点以下を切り捨てる割り算）を表します。この数式を、eval() などの組み込み関数に頼らずに自力で評価し、結果を返すプログラムを実装していきます。 たとえば、入力が s = "2+3*5/7" の場合、出力は 4 になります。これは 2 + ((3 * 5) / 7) ＝ 2 + (15 / 7) ＝ 2 + 2 ＝ 4 となるためです。 解決のアプローチ ポイントは演算子の優先順位の扱いです。「*」と「/」は「+」や「-」よりも先に計算し

問題の概要n × 3 の行列が与えられます。各行は [出発地(src)、目的地(dest)、路線ID(id)] の3つのフィールドで構成されており、そのバスが出発地から目的地へ運行していることを表しています。新しいバスに乗るたびに1単位の料金がかかりますが、同じバスに乗り続けている間は合計で1単位しか支払いません。このとき、場所0から最終目的地(最大の場所番号)まで移動するために必要な最小コストを求めます。目的地に到達できない場合は -1 を返してください。入力例010120230351502上記の入力の場合、出力は 2 になります。場所0でバス0に乗り、場所3で降りて、そこからバス1に乗り換

問題概要 N × N の2値行列を考えます。ここで 0 は空のセル、1 はブロックされたセルを表します。このとき、「すべての行とすべての列に、選ばれたセルが少なくとも1つ含まれる」ように N 個の空のセルを選ぶ方法の数を求めます。答えが非常に大きくなる可能性があるため、結果は 10^9 + 7 で割った余りとして返します。 例えば、入力が次のような行列だったとします。 000000010 この場合、出力は 4 になります。以下の4通りの配置(x が選択されたセルを表す)が存在するためです。 アプローチ:ビットマスクを使った再帰探索 この問題は、行ごとに順番に処理を進めていく再帰的な探索で解

数値のリスト nums が与えられたとき、最長の増加部分列（LIS）の長さを求めることを考えます。ただし、この問題では部分列がリストの末尾に到達した後、先頭に戻って続くことができる、いわゆる「循環」を許容する点が特徴です。問題の例たとえば、入力が次の場合を考えてみましょう。nums = [6, 5, 8, 2, 3, 4]このとき出力は 5 になります。これは、最長の増加部分列が [2, 3, 4, 6, 8] となるためです。末尾の要素から先頭へ「折り返して」部分列を構成できる点に注目してください。解法のアプローチ循環を扱うために、元のリストを2回連結した配列を作成し、各開始位置から標準的な

問題の概要 直交座標系の点のリスト [(x1, y1), (x2, y2), ..., (xn, yn)] が1つのポリゴン(多角形)を表しているとします。ここに、判定対象となる点 (x, y) が与えられたとき、その点がこのポリゴンの内側、あるいは境界上に存在するかどうかを判定するのが本記事のテーマです。 例として、次のような入力を考えてみましょう。 points = [(0, 0), (1, 3), (4, 4), (6, 2), (4, 0)] pt = (3, 1) この場合、点 (3, 1) はポリゴンの内部にあるため、出力は True となります。 解決のアプローチ この問題は

数値のリスト nums と整数 k が与えられたとき、リストの要素から作れる部分集合（サブセット）のうち、合計がちょうど k になるものの個数を求めます。答えが非常に大きくなる可能性があるため、結果は 109 + 7 で割った余りを返します。 たとえば、入力が nums = [2, 3, 4, 5, 7]、k = 7 の場合、出力は 3 になります。[2, 5]、[3, 4]、[7] の 3 つの部分集合が条件を満たすためです。 解法のアプローチ：動的計画法（DP） この問題はナップサック問題と同じ構造を持っており、動的計画法を使うことで効率的に解けます。dp[j] を「合計が j になる部分

国をN個のノードとN-1本の辺からなる木構造として表現することを考えます。各ノードは町を表し、各辺は道路を表します。サイズN-1のリストsourceとdestが与えられ、i番目の道路はsource[i]とdest[i]を双方向に結んでいます。また、サイズNのリストpopulationも与えられ、population[i]はi番目の町の人口を表します。 ここで、いくつかの町を「都市」へアップグレードすることを考えます。ただし、以下の条件を満たす必要があります。 2つの都市が互いに隣接してはならない 町に隣接するすべてのノードは都市でなければならない(すべての道路は必ず町と都市をつなぐ) こ

文字列 s が与えられたとき、最大 k 文字を削除することでその文字列を回文（前から読んでも後ろから読んでも同じになる文字列）にできるかどうかを判定する問題を考えてみましょう。 例えば、s = lieuvrel、k = 4 という入力の場合、出力は True になります。3 文字を削除すれば回文 level を作ることができるためです。 解法のアプローチ：最長共通部分列（LCS）を活用する この問題は、最長共通部分列（LCS：Longest Common Subsequence）を利用すると効率的に解けます。考え方のポイントは以下の通りです。 文字列 s と、それを逆順にした文字列との最長

問題の概要 0と1だけで構成されるバイナリ行列と整数 k が与えられます。各ピースに必ず1つ以上の「1」が含まれるように、この行列を k 個の部分に分割する方法の数を求めるのが目的です。ただし、切断には次のルールがあり、必ずこの順序で従う必要があります。 方向を選ぶ：垂直方向または水平方向のどちらかを選択します。 切断位置を選ぶ：行列内のインデックスを1つ選び、そこで2つの領域に分割します。 垂直に切った場合：左側の領域はこれ以上切断できず、右側だけを切り続けられます。 水平に切った場合：上側の領域はこれ以上切断できず、下側だけを切り続けられます。 この条件下で、行列を分割できる異なる方法

2次元のマトリックス(行列)が与えられたとき、あるセルを出発点として選び、上下左右に隣接する同じ値のセルへ移動しながら進み、再び出発点に戻れるかどうか(つまりサイクルが存在するかどうか)を判定します。ただし、直前のステップで訪れたセルにはすぐに戻ることはできません。 たとえば、入力が以下のマトリックスだった場合を考えてみましょう。 222121212221 この場合、出力は True になります。「2」のセルを順にたどると環状の経路(サイクル)が形成されるためです。 解決のためのアルゴリズム この問題は、深さ優先探索(DFS)を使うことで効率的に解けます。手順は以下の通りです。

各要素が [uid, time_sec] の形式（uid はユーザーID、time_sec はタイムスタンプ）で構成されるリクエストのリストを考えてみましょう。これは「IDが uid のユーザーが、時刻 time_sec にウェブサイトへリクエストを送信した」ことを意味します。 さらに、2つの値 u と g が与えられます。 u: 特定の uid に対して、60秒未満の時間枠内で許容される最大リクエスト数 g: システム全体に対して、60秒未満の時間枠内で許容される最大リクエスト数 リクエストを1件ずつ処理しながらレート制限を適用します。複数のユーザーから同時にリクエストが届いた場合は、u

この記事では、NumPy配列を活用してpandasのSeriesデータ構造を作成し、インデックスに明示的に値を指定する方法を解説します。通常、Seriesを作成する際にインデックスを指定しない場合は、0から始まる連番が自動的に割り当てられます。しかし、index引数を使用することで、任意のカスタムインデックスを自由に設定できます。サンプルコードimport pandas as pd import numpy as np my_data = np.array([ab,bc,cd,de, ef, fg,gh, hi]) my_index = [3, 5, 7, 9, 11, 23, 45, 67]

データ分析において可視化（ビジュアライゼーション）は非常に重要なステップです。数値を一つひとつ確認したり複雑な計算を行ったりしなくても、データに何が起きているのかを直感的に把握できるからです。その可視化を手軽に実現できるライブラリの一つが、Pythonの「Seaborn」です。 散布図（scatter plot）とは、データポイントをグラフ上に点として散りばめて分布を表現するグラフのことです。数値データの値をドットで表し、横軸・縦軸上の各ドットの位置が、それぞれのデータポイントの値を示します。散布図を使うことで、2つの変数間の関係性（相関）を視覚的に理解することができます。 ここでは、Sea

はじめにpandasのSeriesデータ構造では、スカラー値(定数値)を一度だけ定義すると、その値がすべての行(エントリ)に自動的に繰り返し適用されます。この仕組みにより、同じ値を持つ複数のデータを簡単に作成できます。以下に具体的な例を示します。例1: インデックスを指定して作成するimport pandas as pd my_index = [ab, mn ,gh,kl] my_series = pd.Series(7, index = my_index) print(This is series data structure created using scalar values and

pandasのSeriesでは、デフォルトのインデックス値が使われている場合、通常のインデックス指定によって要素にアクセスできます。一方、インデックスをカスタマイズしている場合は、そのカスタムインデックスをキーとして渡すことで要素にアクセスし、コンソールに表示することが可能です。 ここでは、実際のコード例をもとに、それぞれのアクセス方法を詳しく見ていきましょう。 サンプルコード import pandas as pd my_data = [34, 56, 78, 90, 123, 45] my_index = [ab, mn ,gh,kl, wq, az] my_series = pd.Ser

はじめにPandasのシリーズ（Series）では、インデックス値を自由にカスタマイズできます。カスタムインデックスを設定した場合、series_name[index_value] の形式で各要素にアクセスすることが可能です。シリーズに渡された index_value は、元のシリーズのインデックスと照合され、一致するものが見つかれば、その対応するデータがコンソールに表示されます。本記事では、この仕組みを使って複数の要素を一度に取得する方法を、具体的なコード例とともに解説します。コード例import pandas as pd my_data = [34, 56, 78, 90, 123, 45