C++

問題の概要ある数 n が与えられたとき、l < r かつ l + (l + 1) + ... + (r − 1) + r = n を満たす2つの整数 l と r を見つけることを考えます。例えば、入力が n = 25 の場合、出力は l = −2、r = 7 となります。実際、(−2) + (−1) + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 = 25 が成り立つためです。なお、これ以外の組み合わせも答えとして成立します。解法のアプローチこの問題は非常にシンプルで、次の手順で解くことができます。-(n-1) と n を出力（返却）するこの解法が成り立つ理由は、−(n−

問題概要 整数 d が与えられたとします。ここで、一辺の長さが 1 の正方形タイルと正三角形タイルが無限枚あるものと考えます。これらのタイルを組み合わせて、一辺の長さが d の正十二角形（12 辺形）を作るとき、その作り方が何通りあるかを求めるのがこの問題です。答えが非常に大きくなる場合は、998244353 で割った余りを返します。 アプローチ この問題は、二項係数を利用することで効率的に解くことができます。結論から言うと、求めるべき答えは C(2d−1, d−1)、すなわち「2d−1 個の中から d−1 個を選ぶ組み合わせの総数」です。 階乗を直接計算すると値が急激に大きくなりオーバー

問題概要有向グラフ G の隣接行列が与えられているとします。グラフが空になるまで、次の操作を繰り返し実行します。グラフから任意の頂点を1つ選び、その頂点自身と、その頂点から辺をたどって到達できるすべての頂点をまとめて削除します。頂点を削除するとき、その頂点に接続されている辺も同時に取り除かれます。このとき、グラフが空になるまでに操作を行う回数の期待値を求めるのが目的です。入力例と出力例次のようなグラフが入力として与えられた場合を考えてみましょう。この場合の出力は 1.6667 になります。その理由は以下の通りです。最初に頂点 A を選べば、すべての頂点が一度で削除できる（操作回数 1 回）最初

3つの整数 a、b、c が与えられているとします。これらを使って、非退化(面積が0にならない)な単純四辺形の形をした閉じたフェンスを作りたいと考えます。すでに長さ a、b、c の3本の辺は手元にあり、残る4番目の辺 d の長さを求めるのがこの問題の目的です。 例えば、入力が a = 12、b = 34、c = 56 の場合、プログラムは 100 を出力します。ただし、これは唯一の正解ではなく、条件を満たす他の値(例えば 42 など)も答えとして成立します。 解き方の考え方 四辺形が成り立つためには、「どの1辺の長さも、他の3辺の合計より短くなければならない」という条件が必要です。もし1辺が他

問題の概要数値 n が与えられたとします。ここでいう括弧列（ブラケットシーケンス）とは、文字「(」と「)」のみから構成される文字列のことです。さらに、有効な括弧列とは、元の文字同士の間に「1」と「+」を挿入することで、正しい算術式へと変換できる括弧列を指します。たとえば「()()」は「(1)+(1)」のように書き換えられるため、有効な括弧列であるといえます。この記事では、数値 n が与えられたときに、長さ 2n の互いに異なる有効な括弧列をちょうど n 個見つけて出力する方法を解説します。たとえば、入力が n = 4 の場合、出力は次のようになります。[()()()(), (())()(),

n個の要素を持つ配列Aがあるとします。与えられた数値の中から任意の部分集合を選び、それらの数値の符号を反転（マイナスに変更）することができます。このとき、配列内に作り出せる異なる値の最大数を求めるのがこの問題です。 例えば、入力が A = [1, 1, 2, 2] の場合、出力は 4 になります。これは、最初と最後の数値の符号を反転することで、配列 [-1, 1, 2, -2] を作り、4つの異なる値が得られるためです。 解法のアプローチ この問題は、セット（set）を使うことでシンプルに解くことができます。考え方のポイントは次の通りです。 各要素について、その値がすでにセットに存在するか

問題の概要n個の要素を含む配列Aがあるとします。この配列から重複する要素を削除し、各要素について配列内で最も右側に出現するものだけを残したいと考えます。その際、残った一意な要素同士の相対的な順序は変更してはいけません。例えば、入力が A = [1, 5, 5, 1, 6, 1] の場合、出力は [5, 6, 1] となります。各要素の右端の出現だけが残り、元の配列での順序が保たれていることがわかります。アルゴリズムの手順この問題を解くために、以下の手順に従います。= 0 まで、i を 1 ずつ減らしながら繰り返す: b[i] を出力する実装例理解を深めるために、以下のC++による実装を

整数 X が与えられているとします。現在、銀行には 100 ルピーの預金があり、銀行は年 1% の複利で利息を付けてくれます（計算では整数のみを扱います）。このとき、預金残高が X ルピーに達するまでに何年かかるのかを求めるのが本記事の目的です。例えば、入力として X = 520 が与えられた場合、出力は 213 となります。解き方の手順この問題は、実際に残高が増えていく様子をシミュレーションすることで解けます。以下の手順に従います。sum := 0 balance := 100 while balance < n, do: interest := balance / 100

3つの整数 A、B、C が与えられます。ここで次のようなゲームを考えてみましょう。「整数パネル」が3枚あり、それぞれに1から9までの数字が1つずつ書かれています。また、「+」記号が書かれた「演算子パネル」が1枚あります。プレイヤーはこれら4枚のパネルを左から右へ並べ、X+Y の形の式を作らなければなりません。そして、その式の計算結果がもらえるお小遣いの金額になります。 この記事では、このゲームで得られるお小遣いの最大額を求める方法を解説します。 具体例 例えば、入力が A = 1、B = 5、C = 2 の場合、出力は 53 になります。これは、パネルを「52+1」という順序で並べたときにお小

問題の概要5つの整数 N, A, B, C, D が与えられます。数値を0から開始し、目標値Nまで到達させることがゴールです。数値は以下の操作を、それぞれ決められた枚数のコインを支払うことで変更できます。数値を2倍する：A枚のコインが必要数値を3倍する：B枚のコインが必要数値を5倍する：C枚のコインが必要数値を1増やす、または1減らす：D枚のコインが必要これらの操作は何回でも、好きな順序で実行できます。Nに到達するために必要な最小のコイン枚数を求めましょう。入力例と出力例例えば、入力が N = 11、A = 1、B = 2、C = 2、D = 8 の場合、出力は 19 になります。初期状態では

4つの数値 n、x、a、b が与えられているとします。一列に並んだ n 人の学生がおり、その中に2人のライバル関係にある学生がいます。1人は位置 a に、もう1人は位置 b にいます。位置は左から右へ 1 から n まで番号が付けられています。この2人の学生の間の距離を最大化したいと考えています。次の操作を x 回まで実行できます。隣り合う2人の学生を選んで入れ替えるというものです。x 回のスワップ後に実現可能な最大距離を求める必要があります。例えば、入力が n = 5、x = 1、a = 3、b = 2 の場合、出力は 2 になります。これは、位置 3 と位置 4 の学生を入れ替えることで、

n個の相異なる要素からなる配列Aと、整数xが与えられます。ここにn枚の金貨があり、i番目の金貨の重さはA[i]です。これらの金貨を体重計に1枚ずつ順番に載せていきます。ただし、この体重計には奇妙な欠陥があり、載せた金貨の合計重量がちょうどxになると爆発してしまいます。すべての金貨を爆発させることなく体重計に載せられるかどうかを判定し、可能であればその順序を求めてください。不可能な場合は「IMPOSSIBLE」を出力します。例えば、入力が A = [1, 2, 3, 4, 8]、x = 6 の場合、出力は [8, 1, 2, 3, 4] となります(他の順序も有効です)。解法のステップこの問題を

問題の概要N個の座標点Pが (xi, yi) の形式で与えられているとします。ここで、xとyの値はそれぞれ1からNまでの自然数の順列になっています。1からNまでの各kについて、自分は今「都市k」にいるものと考えます。次の操作を任意の回数だけ繰り返し実行できます。操作： 現在いる都市と比較して、「x座標とy座標の両方が小さい都市」または「x座標とy座標の両方が大きい都市」へ移動する。このとき、都市kから到達できる都市の総数を求めるのが目的です。例えば、入力が P = [[1, 4], [2, 3], [3, 1], [4, 2]] の場合、出力は [1, 1, 2, 2] となります。解き方のア

この記事では、小文字のみで構成された2つの文字列 S と T が与えられたとき、T と S をこの順番で連結して最終的な文字列を生成するC++プログラムを解説します。 たとえば、入力が S = ramming、T = prog の場合、T を先に連結するため、出力は programming となります。 アルゴリズムの手順 この問題は、次のシンプルな手順で解くことができます。 res := T と S をこの順に連結する res を返す C++での実装例 それでは、実際のコードを見てみましょう。 #include <bits/stdc++.h> using namespace

N個の要素を持つ配列Aと、長さNの2進文字列Sが与えられているとします。ここで、番号0と番号1の2人のプレイヤーがゲームを行います。変数xの初期値は0で、ゲームは全部でNラウンド構成されています。i回目のラウンドでは、S[i]に対応するプレイヤーが「xを x XOR A[i] に置き換える」か「何もしない」のいずれかを選択します。プレイヤー0はゲーム終了時にxが0になることを望み、一方プレイヤー1は0以外になることを望みます。私たちの課題は、ゲーム終了時にxが0になるかどうかを判定することです。 例えば、入力が A = [1, 2]、S = 10 の場合、出力は 1 になります。これは、プレ

問題概要n個の要素を持つ配列Aがあり、n人の兵士が円形に並んでいるとします。i番目の兵士の身長はA[i]で表されます。偵察ユニットは、隣り合う2人の兵士のうち、身長差が最も小さいペアで編成されます。身長の近い2人が並ぶことで、お互いに目立ちにくくなるためです。この記事では、偵察ユニットを編成できる兵士のペアのインデックスを求めるC++プログラムを紹介します。例えば、入力が A = [10, 12, 13, 15, 10] の場合、出力は (5, 1) となります。これは、5番目の兵士（身長10）と1番目の兵士（身長10）が円の上で隣り合っており、身長差が0と最小であるためです。解法のステップ兵

本記事では、配列Aに含まれる情報から、登った階段の数と、それぞれの階段の段数を求めるC++プログラムを紹介します。 問題の概要 n個の要素を持つ配列Aがあるとします。Amalは多層ビルの中で階段を上っており、階段を上るたびに1から数え始めます。例えば、3段と4段の2つの階段を上った場合、「1, 2, 3, 1, 2, 3, 4」のように数字を発します。 配列Aには、Amalが発した階段番号が記録されています。この配列をもとに、彼が何回階段を上ったかをカウントし、さらに各階段の段数を出力する必要があります。 例えば、入力が A = [1, 2, 3, 1, 2, 3, 4, 5] の場合、出力は

数 n が与えられたとき、最初の n 個の自然数（1 から n までの整数）を考えます。これらを2つの集合 A と B に分割します。ただし、各要素は必ずどちらか一方の集合にのみ属するものとします。このとき、集合 A の要素の合計と集合 B の要素の合計の絶対差が最小になるように分割し、その最小の差を求めます。 問題例 例として、n = 5 の場合を考えてみましょう。 A = {1, 3, 4}、B = {2, 5} と分割すると、それぞれの合計は 8 と 7 となり、差は 1 になります。これより小さい差は実現できないため、答えは 1 となります。 解き方のポイント まず、最初の n 個の自

問題概要n 文字からなる文字列 S が与えられます。S には小文字の英字と「)」という文字が含まれています。この文字列が悪い(bad)と判定されるのは、末尾に連続する「)」の数が、それ以外の残りの文字数よりも厳密に多い場合です。ここでは、与えられた文字列 S が悪いかどうかをチェックするプログラムを作成します。たとえば、入力が S = fega)))))) の場合、出力は True になります。なぜなら、この文字列には英字が4文字しかないのに対し、「)」が6個あるためです。解法のアプローチこの問題は、以下の手順で効率的に解くことができます。カウンタ変数 ans を 0 で初期化します。文字列の

問題の概要 n個の相異なる要素を持つ配列Aが与えられます。配列Bが「良い配列（nice）」であるとは、次の2つの条件を満たすことをいいます。 B[i] ≠ B[j] を満たす任意の2要素について、絶対差 |B[i] − B[j]| がBの中に少なくとも1回現れること Bのすべての要素が互いに重複しないこと 求めたいのは、配列Aにいくつかの整数を追加して、要素数300以下の良い配列を作ることができるかどうかです。可能であれば新しい配列を返し、不可能な場合は -1 を返します。 入力例と出力例 たとえば、入力が A = [4, 8, 12, 6] だった場合、出力は [8, 12, 6, 2