Python

垂直暗号とは 垂直暗号（縦読み式の転置暗号）は、平文となる文字列を指定した行数のグリッドに行ごとに書き込み、それを列ごとに上から下へ読み上げることで暗号文を作る古典的な手法です。本記事では、Pythonを使ってこの変換をシンプルに実装する方法を解説します。 問題の概要 文字列 s と整数 n が与えられたとします。s を n 行に並べ替え、その結果を縦方向（上から下、左から右）に読み取った文字列のリストを求めます。 たとえば、入力が s = ilovepythonprogramming、n = 5 の場合、出力は次のようになります。 [ipnrn, lypag, otrm, vhom, eo

問題の概要 小文字アルファベットのみで構成された文字列 text と、もう一つの文字列 key が与えられたとします。このとき、text の各文字 text[i] を、key[i] が表すオフセット分だけ右へずらした新しい文字列を作成します。ここでのオフセットとは、key[i] のアルファベット上の位置（a=0、b=1、c=2 …）のことです。ずらした結果が「z」を超えた場合は、先頭の「a」に戻って折り返します。これは古典暗号の一つであるヴィジュネル暗号（Vigenère cipher）として知られる方式です。 例えば、入力が text = code、key = team の場合、出力は vs

小文字のアルファベットのみで構成された文字列 s が与えられたとき、すべての母音をアルファベット順に並べたものの後ろにすべての子音をアルファベット順に並べたものを連結した文字列を作る問題を考えてみましょう。 問題例 入力が helloworld の場合、出力は eoodhlllrw になります。これは、母音が e、o、o の3つでソート後も eoo、子音をソートすると dhlllrw になるためです。 解き方のアプローチ この問題は、以下の手順で解くことができます。 母音を格納するための空文字列 k と、子音を格納するための空文字列 t を用意します。 文字列 s の各文字 c に対して次の

数値 n、p、q が与えられているとします。あなたは n 人が並んでいる列の中に立っており、自分が何番目にいるかは正確には分かりません。ただし、前方には少なくとも p 人、後方には最大でも q 人いることは分かっています。このとき、自分が立ち得る位置の候補が何通りあるかを求めるのがこの問題です。例として、入力が n = 10、p = 3、q = 4 の場合を考えてみましょう。合計 10 人が並んでおり、前方に最低 3 人、後方に最大 4 人いるため、立つことのできる位置はインデックス [0, 1, 2, 3, 4] の 5 箇所となります。たとえばインデックス 0 の位置では、前方に 9 人、

時系列順に並んだ企業の株価リストが与えられたとき、その株を一度だけ買って売ることで得られる最大の利益を求める問題を考えてみましょう。ただし、「売る」ためには必ず先に「買って」おく必要がある点に注意してください。 たとえば、入力が prices = [10, 12, 9, 6, 8, 12] の場合、出力は 6 になります。これは、株価が 6 のときに購入し、12 のときに売却すれば、最大の利益 12 - 6 = 6 が得られるためです。 解法のアプローチ この問題は、リストを一度走査するだけで解くことができます。ポイントは「これまでの最安値」を常に記録しておき、各時点での売却益を計算して最大値

2部グラフとは無向グラフが与えられたとき、そのグラフが2部グラフ(バイパータイトグラフ)であるかどうかを判定する方法を解説します。2部グラフとは、グラフのすべての頂点を2つの集合 A と B に分割でき、グラフ内のすべての辺 {u, v} が必ず一方の端点 u が集合 A、もう一方の端点 v が集合 B に属するようなグラフのことです。つまり、同じ集合内の頂点同士を結ぶ辺(A-A や B-B)が一切存在しないグラフです。例として、次のようなグラフを考えてみましょう。この場合、頂点 [0, 4] を集合 A に、[1, 2, 3] を集合 B に分類できます。すべての辺は A から B、または

時系列順に並んだ企業の株価リストが与えられたとします。このとき、その株式を何度でも自由に売買して得られる最大の利益を求める必要があります。ただし、株式は必ず「購入してから売却する」という順序で取引しなければならない点に注意してください。 例えば、入力が prices = [10, 50, 30, 40, 60] の場合、出力は 70 になります。これは、10で購入して50で売却し、その後30で再度購入して60で売却することで、合計70の利益を得られるためです。 解法のアプローチ この問題は「貪欲法(グリーディー法)」を使うことで、非常にシンプルかつ効率的に解くことができます。手順は以下の通りで

数値のリスト nums と別の数値 k があるとします。インデックス k から開始し、現在いる任意のインデックス i において、ちょうど nums[i] ステップだけ左または右へ移動することができます。このとき、リストの末尾（最後のインデックス）に到達できるかどうかを判定する必要があります。例えば、入力が nums = [0, 0, 2, 1, 3, 3, 1, 1]、k = 2 の場合、出力は True になります。これは、インデックス 2 から開始してインデックス 4 へジャンプし、その後最後のインデックス 7 に到達できるためです。解法のアプローチこの問題は、グラフの探索問題として捉える

文字列のリスト words と、別の文字列 letters が与えられたとします。このとき、letters に含まれる文字だけを使って作成できる words 内の最も長い文字列の長さを求めます。どの単語も作成できない場合は 0 を返します。なお、同じ文字を再利用することはできません。例として、words = [dog, cat, rat, bunny, lion, bat]、letters = gabctnyu の場合を考えてみましょう。このとき出力は 3 になります。「cat」や「bat」なら与えられた文字で作成できますが、それより長い単語は作れないため、最大の長さは 3 となるからです。解

n × n の行列 M が与えられたとき、その中で「Z」の字形を形成するすべての要素の合計を求めます。ここでいうZ字は、最初の行全体、最後の行全体、そして右上から左下へ向かう副対角線によって構成されます。 たとえば、入力として次のような行列が与えられたとします。 432918256 この場合の出力は 23 になります。Z字を構成する要素は [4+3+2+1+2+5+6] となり、その合計が 23 だからです。 解き方のアプローチ この問題は、以下の手順で解くことができます。 変数 n に行列の行数を代入します。 n が 2 以下の場合、Z字の形が成立しないため、行列内の全要素の合計をそのまま

問題の概要同じ長さを持つ2つのリスト「weights（重さ）」と「values（価値）」、そして容量を表す数値 k が与えられているとします。weights[i] と values[i] は、それぞれ i 番目の品物の重さと価値を表します。ここで、合計の重さが容量 k を超えない範囲で品物を選びます。ただし、各品物は1つしか選べないものとします。この条件のもとで、取得できる価値の合計の最大値を求めるのが目的です。これは動的計画法（DP）を使って解ける、いわゆる「0/1 ナップサック問題」の典型例です。入力例weights = [2, 3, 4]values = [2, 6, 4]capacit

2つの2進数を表す文字列 a と b が与えられたとします。この2つの2進数を加算し、その合計値を同じく文字列として返す必要があります。例えば、入力が a = 10110、b = 10010 の場合、出力は 101000 となります。アルゴリズムこの問題は、筆算と同じ要領で下の桁から順に足し合わせていくことで解けます。具体的な手順は以下の通りです。結果を格納するための空の文字列 ret を用意するna := a のサイズ、nb := b のサイズ とするi := na - 1、j := nb - 1(各文字列の末尾のインデックス)繰り上がり用の変数 carry を 0 で初期化するi >

問題の概要「nums」という数値のリストがあるとします。これはある路線上のバス停を表しており、nums[i] はバスが i 番目の停留所に到着しなければならない時刻を示しています。バスは前方にしか進めないため、すべての停留所を通過するために必要な最小のバス台数を求める必要があります。たとえば、入力が nums = [1, 2, 7, 9, 3, 4] の場合、出力は 2 になります。1 台目のバスが時刻順に [1, 2, 3, 4] の停留所を担当し、2 台目のバスが [7, 9] を担当できるからです。解法のアプローチこの問題は貪欲法（グリーディ法）を使って効率的に解くことができます。まだ訪

プログラミングの典型的な問題として、「階段の登り方」問題があります。この記事では、Pythonを使ってこの問題を動的計画法（DP）で解く方法を詳しく解説します。 問題の概要 n段の階段があるとします。一度に1段または2段ずつ上ることができる場合、この階段を上るユニークな登り方の総数を返す関数を定義する必要があります。 ポイントは、段を踏む順序が異なれば別の登り方としてカウントするという点です。また、答えが非常に大きな数になる可能性があるため、結果を 10^9 + 7 で割った余りを返します。 例えば、入力が n = 5 の場合、出力は 8 となります。これは、次の8通りのユニークな登り方が存

n段の階段と整数kが与えられた場面を考えてみましょう。最初は0段目に立っており、一度の移動で1段、2段、または3段ずつ上ることができます。ただし、「3段ずつの移動」は全体で最大k回までしか使えません。この条件下で、階段を一番上まで登る方法が何通りあるかを求めるのがこの問題です。 たとえば n = 5、k = 2 の場合、答えは 13 になります。実際にあり得る登り方は次の13通りです。 [1, 1, 1, 1, 1] [2, 1, 1, 1] [1, 2, 1, 1] [1, 1, 2, 1] [1, 1, 1, 2] [1, 2, 2] [2, 1, 2] [2, 2, 1] [1, 1

数値のリスト nums と別の数値 k が与えられているとします。インデックス k から開始し、任意のインデックス i にいるとき、ちょうど nums[i] ステップだけ左または右へ移動することができます。このとき、リストの末尾（最後のインデックス）に到達できるかどうかを判定する必要があります。例えば、入力が nums = [0, 0, 2, 1, 3, 3, 1, 1]、k = 2 の場合、出力は True になります。インデックス2から開始すると、まずインデックス4へジャンプし、その後最後のインデックス7へジャンプできるためです。解決のためのアプローチこの問題は、到達可能なインデックスを順

問題概要数値のリスト nums が与えられたとき、その中のすべての連続する部分配列(サブリスト)を考えます。それぞれの部分配列の合計を計算し、さらにそれらの総和を求めます。最後に、結果を 10 ** 9 + 7(1,000,000,007)で割った余りを返します。例えば、入力が nums = [3, 4, 6] の場合、出力は 43 になります。考えられる部分配列は以下の通りです。[3][4][6][3, 4][4, 6][3, 4, 6]これらすべての合計を足すと 3 + 4 + 6 + 7 + 10 + 13 = 43 となります。解法のアプローチすべての部分配列を実際に生成して合計を計算

同じ長さを持つ2つの空でない文字列 s と t が与えられたとします。これらを部分文字列に分割し、s と t の各ペアが同じサイズで、互いにアナグラム（並べ替え語）となるようにします。そのうえで、s と t を最大回数カットできるような切り分け位置（インデックス）を求めます。条件を満たす結果が存在しない場合は、空のリストを返します。例えば、入力が s = bowcattiger、t = owbactietgr の場合、出力は [0, 3, 5, 6, 10] となります。これは、文字列を5つの区間に分割でき、それぞれの対応する部分文字列が互いにアナグラムになっているためです。具体的には、s =

カードの山が与えられ、それをめくったときに昇順で現れるような初期配置を求める問題を考えてみましょう。カードがめくられるルール一番上のカードを取り除いて表向きにし、その直後のカードは一番後ろへ移動させる。手順1を、カードがなくなるまで繰り返す。この操作を行ったとき、めくられたカードの並びが昇順となるような配置を求めるのが目的です。入力例と動作のシミュレーションたとえば、入力が cards = [1, 2, 3, 4, 5, 6, 7, 8] の場合、出力は [1, 5, 2, 7, 3, 6, 4, 8] となります。1 を取り除き、5 を一番後ろへ移動 → 現在の状態：[2, 7, 3, 6,

片方向リンクリスト（単方向連結リスト）の先頭ノードが与えられたとき、その中央ノードの値を求めることを考えます。ノード数が偶数で中央にあたるノードが2つ存在する場合は、後ろ側（2番目）の中央ノードを返すものとします。さらに、リスト全体をたどるのは1回だけ（シングルパス）で解くのが条件です。例えば、入力が [5,9,6,4,8,2,1,4,5,2] の場合、要素数は10なので中央は「8」と「2」の2つになります。したがって、出力は後ろ側の 2 となります。解法のアプローチこの問題は、基準点となるポインタ p をゆっくり進めながら、カウンタを組み合わせて処理することで解けます。手順は以下の通りです。