Python

問題概要二次元平面上の原点 (0, 0) にいる状態から、1単位ずつの水平移動(H)と垂直移動(V)のみを使って点 (x, y) へ移動することを考えます。目的地への到達方法は複数存在し、それぞれの経路は「H」と「V」の列で表現できます。たとえば、(0, 0) から (2, 2) へ移動する場合、「HVVH」は有効な経路の一つです。ここで整数 k が与えられたとき、すべての経路を辞書順に並べた際の k 番目の経路(文字列)を求めます。たとえば、入力が (x, y) = (3, 3)、k = 3 の場合、出力は「HHVVVH」になります。解法の考え方この問題は、各ステップで「次に H を選んだ場

問題の概要N段の階段を考えます。一段ずつ上がることもできれば、各段で最大N段までジャンプすることもできます。このとき、最上階までたどり着く方法が全部で何通りあるのかを求めるのが目的です。ただし、Nは非常に大きな値になる可能性があります。そこで、答え全体ではなく「上位K桁」と「下位K桁」だけを求めればよいことになっています。例を見てみましょう。入力が N = 10、k = 2 のとき、出力は 63 になります。10段の階段に対して、頂上への登り方がS通りあるとし、そのSを wxyz という4桁の数と考えると、wx(上位2桁)と yz(下位2桁)の合計が 63 になるのです。背後にある数学実は、こ

問題の概要 「A」がn個、「B」が2n個含まれる文字列を考えます。このとき、文字列のすべての接頭辞(プレフィックス)とすべての接尾辞(サフィックス)を取り出しても、「B」の数が常に「A」の数以上になっているような並べ方が何通り存在するかを求めるのが本記事のテーマです。 例えば、n = 2 の場合を考えてみましょう。「A」が2個、「B」が4個あるとき、条件を満たす並べ方は次の4通りになります。 BBAABB BABABB BBABAB BABBAB したがって、入力が n = 2 のとき、出力は 4 となります。 解法のアプローチ この問題は、再帰呼び出しを利用した分割統治の考え方で解くこ

問題の概要 1からnまでのすべての要素を含む集合Aを考えます。P(A)は、Aに含まれる要素のすべての順列を表します。本記事では、次の2つの条件を満たすP(A)の要素の個数を求めるプログラムを紹介します。 条件1: 範囲[1, n]内のすべてのiに対して、A[i] ≠ i である(どの要素も自分自身の位置に配置されない) 条件2: k個のインデックスからなる集合 {i1, i2, ..., ik} が存在し、j < k のとき A[ij] = ij+1、かつ A[ik] = i1 となる(長さkの循環構造を持つ) 具体例：n = 3、k = 2 の場合 入力が n = 3、k = 2

問題の概要 n個のノードを持つ無向グラフGを考えます。単純無向グラフのコストは、そのグラフに含まれるすべてのノードのコストの合計として定義されます。さらに、各ノードのコストは D^k で表されます。ここで D はそのノードの次数(接続されているエッジの本数)です。 このとき、n と k の値が与えられるので、n個のノードから構成可能なすべての単純無向グラフについて、コストの合計を求めます。結果は非常に大きな数になる可能性があるため、1005060097 で割った余りを返します。 具体例 たとえば、入力が n = 3、k = 2 の場合、出力は 36 になります。これは、3つのノードを持つ単純グ

1からnまでの番号が振られた数直線を考えてみましょう。最初は位置0におり、まず1ステップジャンプして位置1へ移動し、次に2ステップジャンプして位置3に到達し、さらに3ステップジャンプして位置6に到達します。このようにジャンプ幅を1ずつ増やしながら進んだとき、最終的に位置nにぴったり到達できるかどうかを判定するのがこの問題です。 例えば、入力が n = 21 の場合、出力は True になります。これは 1+2+3+4+5+6 = 21 となり、6回目のジャンプでちょうど位置21に到達できるためです。 解法のアプローチ この問題は数学的な性質を利用すると効率的に解けます。手順は以下の通りです。

リスト A が与えられたとします。ここで、A のすべての空でない部分列(サブリスト)を考えます。n 個の要素を持つリストには (2n − 1) 個の空でない部分列が存在することが知られています。それぞれの部分列について要素の総和(sublist_sum)を計算し、それらを S1, S2, S3, …, S(2N−1) と表します。そして、次のような特別な総和 P を定義します。P = 2S1 + 2S2 + 2S3 + … + 2S(2N−1)この P の値を求めるのが目的です。ただし、P は非常に大きな値になる可能性があるため、P mod (109 + 7) を返します。入力例と出力例たとえ

数の三角形とは 本記事で扱うのは、次のような規則で生成される「数の三角形」です。 1 1 1 1 1 2 3 2 11 3 6 7 6 3 1 この三角形では、各行の要素はその真上にある3つの数を足し合わせることで生成されます。両端の要素については、真上に存在する数だけが加算されます。 問題の定義 行番号 l が与えられたとき、その行に最初に現れる偶数が何番目にあるかを求めます。位置は 1から始まる ものとします。 例えば、l = 5 の場合、答えは 2 になります。実際に5行目まで書き出すと次のようになります。 1 1 1 1

ある値 n が与えられたとき、次の式で定義される数列 S の最後の桁(一の位)を求めることを考えます。 $$\sum_{i=0\: 2^{^{i}}\leqslant n}^{\alpha } \sum_{j=0}^{n} 2^{2^{^{i}+2j}}$$ 例えば、入力が n = 2 の場合、出力は 6 になります。条件 2^i ≤ n を満たすのは i = 0 と i = 1 のみなので、計算は次のようになります。 S0 = 2^(2^0 + 0) + 2^(2^0 + 2) + 2^(2^0 + 4) = 42 S1 = 2^(2^1 + 0) + 2^(2^1 + 2) + 2^(

問題の概要 4つの整数 a、b、c、d が与えられたとき、次の方程式を満たすペア (x, y) の個数を求めます。 x² + y² = (x × a) + (y × b) ただし、x の範囲は [1, c]、y の範囲は [1, d] とします。 たとえば、入力が a = 2、b = 3、c = 2、d = 4 の場合、出力は 1 になります。このとき条件を満たすのは (2, 3) のみです。実際、2² + 3² = 13 であり、(2 × 2) + (3 × 3) = 13 となるため、等式が成立していることが確認できます。 解法のアプローチ この問題は、方程式を y についての二次方程式と

ある危険なウイルスが急速に増殖していると仮定しましょう。このウイルスは、1単位時間ごとに細胞数がx倍になる確率が0.5、y倍になる確率も0.5となっています。最初にウイルスの細胞が1個だけ存在していたとき、時間t後に存在するウイルス細胞数の期待値を計算してください。ただし、答えが非常に大きくなる場合は、結果を10^9+7で割った余りを出力します。 例として、入力が x = 2、y = 4、t = 1 の場合を考えてみます。初期状態ではウイルスは1個の細胞しか持っていません。確率0.5でその数は2倍になり、同じく確率0.5で4倍になります。したがって、時間t = 1後のウイルス細胞数の期待値は

要素の集合 nums が与えられ、これを非減少順(昇順)に並べ替えることを考えます。ただし、ここで使うのは「ランダム化ソート」という手法です。まず配列がソート済みかどうかを確認し、まだ整列していなければランダムにシャッフルして再度チェックします。すべての要素が正しく並ぶまで、この確認とシャッフルを繰り返します。このとき必要となるシャッフル回数の期待値を求め、答えは小数点以下6桁まで表示します。この手法は俗に「ボゴソート(Bogosort)」とも呼ばれます。 例として nums = [5,2,7] の場合を見てみましょう。このときの出力は 6 になります。3つの異なる要素の並べ方(順列)は 3

問題の概要 n行m列のグリッドを考えます。Amal（アマル）とBimal（ビマル）が、このグリッド上で次のようなルールのゲームを行います。 Amalは白い「蓮（ロータス）」のタイルを最上行の任意のマスに置き、Bimalは「毛虫（キャタピラー）」のタイルを最下行の任意のマスに置きます。 Amalが先手となり、交互に手番を進めていきます。 Amalは自分のタイルを、現在いるマスに隣接する8方向（縦・横・斜め）のいずれかのマスへ移動できます。 一方、Bimalの毛虫タイルは、左右への移動またはその場にとどまることしかできません。 Amalの目的はできるだけ少ない手数でBimalを捕まえることであ

配列 colors があり、これは1つの正n角形の各頂点の色を表しているとします。この多角形の各頂点には、配列内に存在するn種類の色の中からランダムに1色が割り当てられています。ここで、次の条件をすべて満たす「特別なサブセット」の数を求める必要があります。 サブセットのサイズは2以上であること。 サブセットに含まれる頂点を多角形から取り除くと(それらの頂点に隣接する辺も同時に削除されます)、残った頂点と辺がいくつかの連続したパスを形成すること。 どのパスにも、同じ色の頂点が2つ以上含まれていないこと。 そのようなサブセットの総数を数えます。答えが非常に大きくなる場合は、10^9 + 7 で

配列 nums とインデックスのペア (x, y) が与えられ、再帰関数 find(x, y) の計算結果が偶数か奇数かを判定したい場面を考えてみましょう。find() 関数は次のように定義されています。x > y の場合：find(x, y) = 1それ以外の場合：find(x, y) = nums[x] ^ find(x+1, y)なお、ここでの「^」はビット演算ではなく累乗（べき乗）を表すことに注意してください。計算例入力が nums = [3, 2, 7]、(x, y) = (1, 2) の場合、出力は「偶数（Even）」になります。その理由は以下の通りです。find(1, 2)

整数 n が与えられたとき、その真の約数（n 自身を除く約数）の中から無作為に 1 つ選んだ際、それが「偶数の完全平方数」である確率を求める問題を考えます。 たとえば入力が n = 36 の場合、出力は 1/8 になります。これは、36 の真の約数が {1, 2, 3, 4, 6, 9, 12, 18} の 8 個あり、そのうち偶数かつ完全平方数に該当するのは 4 のみだからです。 解法のアプローチ この問題は、次の手順に従って解くことができます。 n を 4 で割った余りが 0 でない場合は 0 を返します（2 の指数が不足しているため、条件を満たす約数が存在しない）。 それ以外の場合は

問題概要 2つの長整数値 maximum（最大値）と minimum（最小値）が与えられているとします。このとき、min <= d <= max を満たす分数 n/d のうち、|n/d − π| が最小になるものを見つける必要があります。ここで π = 3.14159265... です。条件を満たす分数が複数存在する場合は、分母が最も小さい分数を返します。 たとえば、minimum = 1、maximum = 10 が入力された場合、出力は 22/7 になります。 解法のアプローチ この問題はファレイ数列（Farey sequence）の性質を利用すると効率的に解けます。ファレイ

問題の概要 数 n と値 k が与えられ、最初の N 個の自然数(1, 2, ..., n)を要素とする配列 A があるとします。このとき、i < j を満たす要素 A[i] と A[j] のペアのうち、その合計が k で割り切れるものの総数を求めるのが課題です。 例えば、入力が n = 10、k = 4 の場合、合計が 4 で割り切れるペアは次の 10 個存在するため、出力は 10 となります。 [(1,3), (1,7), (2,6), (2,10), (3,5), (3,9), (4,8), (5,7), (6,10), (7,9)] 解法のアプローチ この問題は、全ペアを素朴に

2つの整数 n と m が与えられたとき、「1」を n 個並べた数(例：n = 4 なら 1111)を m で割った余りを求めます。 たとえば入力が n = 4、m = 27 の場合、出力は 4 になります。これは 1111 ÷ 27 の余りが 4 であるためです。 アプローチ n が大きくなると、「1」を n 個並べた数は桁数が膨大になり、そのまま整数として扱うのは非現実的です。そこで、この種の数(レピュニット)が次の式で表せることを利用します。 R(n) = (10n − 1) / 9 つまり、R(n) mod m を求めるには、10n mod 9m を高速に計算できれば十分です。ここで法

ここでは、k個のキャンディを子どもたちに分配する問題を考えます。ただし、分配には以下のルールがあります。i番目の子どもは、ちょうど i² 個のキャンディを受け取るi番目の子どもは、1番目から i−1 番目までの子ども全員に配り終わるまで、キャンディを受け取れないi番目の子どもが i² 個を受け取れない場合、その分配は無効とみなされる例えば、入力が k = 20 の場合、出力は 3 になります。1番目の子どもが1個、2番目の子どもが 2² = 4個、3番目の子どもが 3² = 9個を受け取り、合計14個が消費されます。4番目の子どもには 4² = 16個が必要ですが、残りは6個しかないため、この