Python

ロボットが2次元座標平面（直交座標系）の原点 (0, 0) にいるとします。ロボットが実行できる移動のリストが与えられ、各移動は N（北）、S（南）、W（西）、E（東） のいずれかです。このロボットが、目的地の座標 (x, y) に到達できるかどうかを判定するプログラムを作成します。 例えば、入力が moves = [N,N,E,E,S]、目的地が (x, y) = (2, 1) の場合、出力は True になります。北に2回、東に2回、南に1回移動することで、最終的に (2, 1) に到達できるからです。 解決のアプローチ この問題は、ロボットの移動を実際にシミュレーションすることで解けます

ソートされた数値リスト nums が与えられたとき、リスト内のすべての数値ペアの絶対差の合計を求めることを考えます。ここで、(i, j) と (j, i) は異なるペアとして扱います。答えが非常に大きくなる場合は、結果を 10^9+7 で割った余りを返します。例えば、nums = [2, 4, 8] の場合、|2 - 4| + |2 - 8| + |4 - 2| + |4 - 8| + |8 - 2| + |8 - 4| を計算することになるため、出力は 24 となります。解法のアプローチこの問題を効率的に解くために、以下の手順に従います。m = 10^9 + 7 とします。total を 0

問題の概要 正の整数 n が与えられたとき、n を互いに異なる階乗の値(1!, 2!, 3! など)の和として表すことができるかどうかを判定する問題です。 たとえば、入力が n = 144 の場合を考えてみましょう。 4! + 5! = 24 + 120 = 144 となるため、この場合の出力は True になります。 解法のアプローチ この問題は、次の手順で解くことができます。 fact を 1 で初期化し、結果を格納するための空のリスト res を用意します。また、カウンタ x を 2 とします。 fact <= n である限り、以下を繰り返して n 以下のすべての階乗をリストに

問題の概要コーダーのパフォーマンススコアを表す数値リスト「ratings」が与えられているとします。マネージャーは各コーダーに最低1,000ルピーを支払いますが、隣接する2人のコーダーが存在する場合、パフォーマンスが優れている方には、劣っている方よりも少なくとも1,000ルピー多く支払いたいと考えています。この制約をすべて満たすとき、マネージャーが支払うべき最小金額を求めるのが目標です。例えば、入力が ratings = [1, 2, 5, 1] の場合、出力は 7000 になります。これは、各コーダーへの支払額がそれぞれ [1000, 2000, 3000, 1000] となるのが最適だから

数値のリスト nums が与えられたとき、その中に存在しない「最初の正の整数」、すなわち欠けている最小の正整数を見つける問題を考えます。配列には重複した値や負の数が含まれる可能性がある点に注意が必要です。 例えば、入力が nums = [0, 3, 1] の場合、出力は 2 となります。0・1・3 は存在しますが、2 だけが欠けているためです。 解決のアプローチ この問題は、集合（set）を使うことでシンプルかつ効率的に解くことができます。手順は以下の通りです。 nums から正の数のみを取り出して集合を作成する（負の数と重複は自動的に除外される） 集合が空の場合は、正の数が一つも存

サイズnの、重複のないソート済み整数リストが与えられたとします。このとき、範囲[1からn+1]の中で配列に存在しない最初の正の整数を見つける必要があります。例えば、入力が nums = [0,5,1] の場合、出力は2になります。これは、1から5の範囲において2が最初に欠けている数だからです。解決のアプローチこの問題を解くには、以下の手順に従います。変数 target を1で初期化する配列 arr の各要素 i について以下を繰り返すi が target と等しい場合、target を1増やす（target := target + 1）ループ終了後、target の値を返すこのアルゴリズムは、

出発空港と到着空港のペア [from, to] で表される航空券のリストが与えられたとします。このとき、すべての航空券を一度ずつ使用する旅程を正しい順序で復元する必要があります。すべての航空券は KLK から出発する一人の旅行者が所有しているため、旅程は必ず KLK から始まります。たとえば、入力が [[MUC, LHR], [KLK, MUC], [SFO, SJC], [LHR, SFO]] の場合、出力は [KLK, MUC, LHR, SFO, SJC] となります。解決のためのアプローチこの問題は、グラフ理論におけるオイラー路（Eulerian Path）を求める問題として捉えること

問題概要 辺のリストとして表されたグラフが与えられたとき、そのグラフが木の集合（フォレスト）であるかどうかを判定します。 たとえば、入力が下図のような場合、出力は True になります。 グラフがフォレストであるためには、すべての連結成分が木であり、閉路（サイクル）が一切存在しないことが必要です。そこで、深さ優先探索（DFS）を用いて各連結成分を調べます。 解法の考え方 DFSの探索中に、すでに訪問済みのノードへ再び到達した場合、閉路が存在すると判断できます。ただし、無向グラフでは直前にいた親ノードへの「逆戻り」は必ず発生するため、このケースは除外して判定します。 アルゴリズムの手順

分数ナップサック問題とは 同じ長さを持つ2つのリスト「weights（重さ）」「values（価値）」と、ナップサックの容量を表す数値「capacity」が与えられます。weights[i] と values[i] は、i 番目の品物の重さと価値を表します。容量を超えない範囲で品物を選び、品物の一部だけを持ち運ぶことも可能（その場合、価値は持ち込んだ重さに比例して減少する）という条件のもとで、得られる価値の合計の最大値を求めます。最終的な答えは、小数点以下を切り捨てた整数として返します。 たとえば、入力が weights = [6, 7, 3]、values = [110, 120, 2]、c

数 n が与えられたとき、以下の規則に従って生成できる長さ n の文字列の総数を求めることを考えます。各文字は小文字の母音 [a, e, i, o, u] のいずれかである「a」の後に続けられるのは「e」のみ「e」の後に続けられるのは「a」または「i」「i」の後に「i」を続けることはできない「o」の後に続けられるのは「i」または「u」「u」の後に続けられるのは「a」のみ結果が非常に大きくなる可能性があるため、答えは 10^9 + 7 で割った余りを返します。例として、入力が n = 2 の場合、出力は 10 になります。このとき生成できる2文字の文字列は、[ae, ea, ei, ia, ie

Rの標準的な summary() 関数では、最小値、第1四分位数、中央値、平均値、第3四分位数、最大値といった基本的な統計量しか得られません。しかし、実務的なデータ分析では、分散、標準偏差、歪度、尖度といった記述統計も頻繁に必要となります。 fBasicsパッケージの basicStats() 関数を使う fBasics パッケージの basicStats() 関数を使用すると、これらすべての統計量を一度に取得できます。 パッケージの読み込み library(fBasics) 実践例1: mtcars データセット R標準搭載の mtcars データを用いて確認してみましょう。 データ

問題の概要点のリストと整数 k が与えられたとします。各点は (x, y) の形式で表されるデカルト座標上の位置です。2つの点 p1 と p2 の間のユークリッド距離が k 以下である場合、その2点は同じグループに属するとみなせます。このとき、全体をいくつの互いに素な（重なり合わない）グループに分割できるか、その総数を求めるのが目的です。入力例たとえば、次のような入力を考えます。points = [[2, 2], [3, 3], [4, 4], [11, 11], [12, 12]]k = 2この場合、出力は 2 になります。理由は、点を次の2つのグループに分けられるためです。グループ1：[2

問題の概要 バイナリ文字列（0と1のみで構成された文字列）が与えられたとき、すべての「1」を文字列内の任意の位置にまとめてグループ化するために必要な最小スワップ回数を求めます。 例えば、入力が 10101001101 の場合、出力は 3 になります。「00000111111」のように並べ替えることで、わずか3回のスワップですべての1を隣接させることができるためです。 解法のアプローチ：スライディングウィンドウと累積和 この問題は、スライディングウィンドウ（尺取り法）と累積和（プレフィックスサム）を組み合わせることで効率的に解けます。基本的な考え方は次の通りです。 文字列中の1の総数を one

Rでは、ベクトルに対して使うforループと、リストに対して使うforループに本質的な違いはなく、通常どおりの構文でそのまま利用できます。たとえば、Listという名前のリストのすべての要素を表示したい場合は、for(i in List){print(i)}と書くだけです。ここで変数iは、ループが1周するごとにList内の各ベクトルを順番に参照します。 サンプルリストの作成 まず、さまざまな種類のベクトルを含むリストを作成します。文字ベクトル、正規分布・ポアソン分布・一様分布・指数分布に従う乱数、丸めた整数値、そして1から100までの連続数列を要素として持たせています。 List <- li

問題の概要各セルの高さを格納した行列 M が与えられます。ここで M[r][c] はセル (r, c) の高さを表します。現在、左上隅に位置しており、右下隅へ移動したいと考えています。隣接するセル（上下左右）へは、そのセルの高さが現在いるセルの高さ「以下」である場合にのみ移動できます。ただし、移動を開始する前に、好きなだけ多くのセルの高さを上げることが可能です。このとき、右下のセルに到達するために必要な「高さの増加量の合計」の最小値を求めるのがこの問題です。入力例245861この場合、答えは 4 になります。経路 [2, 4, 5, 1] をたどることを考え、途中のセルの高さを次のように変更す

数値のリスト nums があるとします。各要素は、その位置から一度に進める最大ジャンプ数を表しています。このとき、インデックス0からスタートして、リストの最後のインデックスに到達できるかどうかを判定する必要があります。例えば、入力が nums = [2,5,0,2,0] の場合、出力は True になります。これは、インデックス0から1へジャンプし、さらにインデックス1（値が5なので最大5つ先まで進める）から最後のインデックスへ直接ジャンプできるためです。解法のアプローチこの問題は動的計画法（DP）を使って効率的に解くことができます。ポイントは、リストを後ろから前に向かって走査し、「その位置か

整数 n が与えられたとき、各位の数字が左から右へ厳密に増加している（隣り合う桁が必ず大きくなっている）n 桁の正の整数が何個存在するかを求めます。たとえば入力が n = 3 の場合、出力は 84 となります。該当するのは 123、124、125、…、678、789 のような数です。解き方のポイントこの問題は、組み合わせ（コンビネーション）の考え方を使うと非常にシンプルに解けます。使用できる数字は 1〜9 の 9 種類です。この中から n 個の異なる数字を選ぶと、それらを昇順に並べる方法はちょうど 1 通りしかありません。つまり、「厳密に増加する n 桁の整数」の個数は、「9 個の数字から n

はじめに二分木（バイナリツリー）が与えられたとき、その根（ルート）から通りがけ走査（インオーダートラバーサル）の結果をリストとして取得するプログラムを考えてみましょう。通りがけ走査とは、木に含まれるすべてのノードを以下の順序で訪問する走査方法のことです。左部分木を再帰的に走査する現在のノードを訪問する右部分木を再帰的に走査する本記事では、この問題を再帰を使わず、反復処理（イテレーティブ）な手法で解く方法を解説します。アルゴリズムの考え方例として、次のような二分木を入力とした場合を考えます。このとき、出力は [12, 13, 4, 16, 7, 14, 22] となります。この問題を解くための手

2つの連結リスト(リンクリスト)l1とl2が与えられたとき、l1から始めて両方のリストの要素を交互に組み合わせた(インターリーブした)1つの連結リストを返すことを考えます。どちらかのリストにノードが余った場合は、その残りのノードを結果のリストの末尾にそのまま追加します。 例えば、入力が l1 = [5,4,6,3,4,7]、l2 = [8,6,9] の場合、出力は [5,8,4,6,6,9,3,4,7] となります。 アルゴリズムの手順 この問題を解くには、以下の手順に従います。 ans := l1 と初期化する l2 が null でない限り、以下を繰り返す ans が null でない

二分木の根ノードが与えられたとき、それを「反転」することを考えます。反転とは、左部分木と右部分木を入れ替え、さらにその子ノードについても同様の入れ替えを再帰的に行う操作です。問題の例例えば、次のような二分木が入力として与えられたとします。この木を反転すると、出力は次のようになります。解き方のアプローチこの問題は、再帰を用いることでシンプルに解くことができます。手順は以下の通りです。ノードを受け取る solve() メソッドを定義します。根ノードが null（None）の場合は、何もせずに return します。根の左の子に solve(右の子) の結果を代入します。根の右の子に solve(左