C++

問題概要 n桁の数字列 S があるとします。この S はデジタル時計を表しており、文字列全体で 0 から 10n − 1 までの整数を表示しています。桁数が足りない場合は、先頭に 0 が並んで表示されるものとします。行える操作は次の2種類です。 時計の表示する数値を 1 減らす 任意の2つの桁を入れ替える(スワップする) できるだけ少ない操作回数で、時計の表示を 0 にしたいと考えています。そのために必要な最小の操作回数を求めましょう。 たとえば、入力が S = 1000 の場合、出力は 2 になります。先頭の 1 と末尾の 0 を入れ替えて 0001 にし、続けて 1 減らす操作を行え

n個の要素を持つ配列Aがあるとします。この配列に対して、次のような操作を適用することを考えます。操作の内容は、「互いに異なる値を持つ隣接する2つの要素を取り除き、その位置にそれらの合計値を配置する」というものです。この操作を1回行うごとに、配列のサイズは1ずつ減少していきます。ここでの課題は、操作を実行した後に到達可能な配列の最短の長さを求めることです。例えば、入力が A = [2, 1, 3, 1] の場合、出力は 1 になります。まず (1, 3) を選ぶと配列は [2, 4, 1] となり、次に (2, 4) を選んで [6, 1] とし、最後に残りの2つを選ぶことで [7] が得られる

ある正の整数 n が与えられます。この n に対して、次のいずれかの操作を何度でも実行できるものとします。n が2で割り切れるとき、n を n/2 に置き換えるn が3で割り切れるとき、n を 2n/3 に置き換えるn が5で割り切れるとき、n を 4n/5 に置き換えるこれらの操作を繰り返し、n を1にするまでに必要な最小の操作回数を求めてください。どうしても1にできない場合は -1 を返します。たとえば、入力が n = 10 のとき、出力は 4 になります。具体的な手順は次のとおりです。n/2 の操作で 10 → 54n/5 の操作で 5 → 4n/2 の操作で 4 → 2n/2 の操作で

要素数 n の配列 A と数値 k が与えられたとします。クラスには n 人の生徒がおり、i 番目の生徒のレーティングは A[i] で表されます。ここで、「全メンバーのレーティングが互いに異なる」という条件を満たす k 人のチームを編成することを目標とします。編成が不可能な場合は「Impossible」を返し、可能な場合は選んだ生徒のインデックス列を返してください。例えば、入力が A = [15, 13, 15, 15, 12]、k = 3 の場合、出力は [1, 2, 5] となります。これは、1番目・2番目・5番目の生徒のレーティングがそれぞれ 15・13・12 であり、互いに重複していな

問題の概要ある正整数 n が与えられます。バイナリデシマル(binary decimal)とは、10進表記におけるすべての桁が 0 または 1 のみで構成されている正整数のことです。たとえば、1001(千一)はバイナリデシマルですが、1021 は 2 という桁を含むため該当しません。この問題では、与えられた数 n を、いくつかのバイナリデシマル(同じ数を何度使っても構いません)の和として表現することを考えます。その際に必要となるバイナリデシマルの最小個数を求めるのが目的です。たとえば、入力が n = 121 の場合、出力は 2 になります。これは、121 を 110 + 11 または 111

問題概要 2つの整数 a と b が与えられたとします。アマル（Amal）とビマル（Bimal）があるゲームを行います。まず、二人はそれぞれ 1 から 6 までの整数を紙に書きます。その後、サイコロを1回振ります。書いた数字がサイコロの出目に最も近いプレイヤーがそのラウンドに勝利し、二人の差が同じであれば引き分けとなります。アマルが a を、ビマルが b を書いたとき、「アマルが勝つ出目の数」「引き分けになる出目の数」「ビマルが勝つ出目の数」をそれぞれ求めてください。 たとえば、入力が a = 2、b = 4 の場合、出力は [2, 1, 3] となります。これはアマルが2通りの出目で勝利で

3つの整数 c0、c1、h と2進文字列 S が与えられるとします。S 内の任意のビットを反転することができ、反転1回につき h コインを支払います。反転を何回か行った後（0回でも構いません）、その文字列を購入することになります。文字列を購入するには、すべての文字を買い取る必要があります。ビット「0」の購入には c0 コイン、「1」の購入には c1 コインが必要です。ここで、文字列の購入に必要な最小のコイン数を求めるのが問題です。 入力例と動作 たとえば、入力が c0 = 10、c1 = 100、h = 1、S = 01010 の場合を考えてみましょう。まず S の2番目と4番目のビット（「1

要素数 n の配列 A と、ある数値 k があるとします。コンテストには n 問の問題が出題されており、Amal の問題解決能力は k です。Amal は常にリストの左端または右端から問題を選んで解き、難易度が k より大きい問題は解くことができません。そして、左右両端の問題の難易度がどちらも k を超えると、そこで作業をやめます。私たちの課題は、彼が解くことのできる問題の数を数えることです。A[i] は i 番目の問題の難易度を表します。例えば、入力が A = [4, 2, 3, 1, 5, 1, 6, 4]、k = 4 の場合、出力は 5 になります。まず左端の難易度 4 の問題を解き、続

問題概要整数 n が与えられます。まず、「良い（good）配列」とは、要素の合計がその配列の長さで割り切れる配列 B のことです。さらに、n 個の要素からなる配列 A が「完全（perfect）」であるとは、A の空でないすべての部分配列が「良い」配列であり、かつ A の各要素が 1 以上 100 以下の範囲に収まっていることを指します。この問題では、与えられた n に対して、上記の条件を満たす「完全な配列」A を構築することが求められます。たとえば入力が n = 4 の場合、出力の一例は [7, 37, 79, 49] となります。ただし、これ以外にも条件を満たす配列は無数に存在するため、別

n個の要素からなる配列Aを考えます。地球上にはn台の飛行機があり、それぞれ1からnまでの番号が付けられています。番号iの飛行機は、番号A[i]の飛行機を「好き」であることが保証されており、A[i] ≠ i（自分自身を好きになることはない）が常に成り立ちます。このとき、「飛行機pはqを好き、qはrを好き、そしてrはpを好き」という3台の飛行機による循環関係が存在するかどうかを判定するのがこの問題です。例えば、入力が A = [2, 4, 5, 1, 3] の場合、出力は True になります。これは、飛行機2は4を好き（A[2]=4）、飛行機4は1を好き（A[4]=1）、飛行機1は2を好き（A[

2つの整数 n と k が与えられたとします。このとき、1から n までの数字をすべて使って構成し、ちょうど k 個のピーク（山）を持つ順列 A を作成する必要があります。ここで、配列 A のインデックス i が「ピーク」であるとは、次の条件を満たすことを指します。A[i] > A[i-1] かつ A[i] > A[i+1]つまり、隣接する両側の要素よりも大きい要素がピークとなります。もし条件を満たす順列が存在しない場合は、-1 を返します。例として、n = 5、k = 2 が入力された場合、出力は [2, 4, 1, 5, 3] のようになります（これ以外の答えも存在します）。ア

問題概要2つの整数 n と s が与えられます。要素の合計がちょうど s と等しくなるような、n 個の非負の要素からなる配列を考えたとき、その中央値として実現可能な最大値を求めます。例えば、入力が n = 3、s = 5 の場合、出力は 2 になります。これは、配列 [1, 2, 2] を考えると、合計が 5 で中央値が 2 となり、これより大きい中央値は実現できないからです。解法のアプローチこの問題は、次の手順で解くことができます。配列を昇順に並べたとき、中央値より前に位置する下位 n / 2 個の要素は、すべて 0 にしても構いません。すると、残りの合計 s を中央値以降の (n / 2)

同じ長さ n の3つの文字列 S・T・U が与えられているとします。0 から n-1 までの各インデックス i に対して、U[i] を S[i] または T[i] のどちらか一方と交換する必要があります。つまり、合計でちょうど n 回の交換操作を行うことになります。この一連の操作を終えたとき、文字列 S を T と完全に一致させられるかどうかを判定するのが本問題です。考え方実は、この問題は各インデックスごとに独立して考えることができます。インデックス i の交換は S[i] と T[i] のどちらか一方にしか影響しないためです。U[i] を S[i] と交換した場合：S[i] は元の U[i]

ここに3つの整数 a、b、c があるとします。それぞれの長さが a、b、c である3本の棒があり、1分ごとに好きな棒を1本選んで長さを1cmずつ伸ばすことができます。ただし、棒を折ったり切ったりすることはできません。このとき、3本の棒で三角形を形成できるようにするために必要な最小の分数を求めます。問題例たとえば、入力が a = 2、b = 3、c = 5 の場合、出力は 1 になります。a または b のどちらか一方を1だけ伸ばせば、(a + b) > c という条件を満たす三角形を作ることができるためです。つまり、わずか1分で十分ということになります。解き方・アルゴリズムの手順三角形の

5つの整数 s、v1、v2、t1、t2 が与えられます。Amal（アマル）とBimal（ビマル）は、オンラインでタイピングゲームの対戦を行っています。このゲームでは、長さ s の文字列を入力します。Amalが1文字入力するのにかかる時間は v1 ミリ秒、Bimalは v2 ミリ秒です。また、Amalのネットワーク遅延は t1 ミリ秒、Bimalのネットワーク遅延は t2 ミリ秒です。 通信遅延がある場合のゲームの流れ 通信遅延が t ミリ秒であるとき、各参加者にとって競技は次のように進行します。 ゲーム開始からちょうど t ミリ秒後に入力すべきテキストが届く。 テキストを受け取った直後に入力

2つの整数 n と k が与えられます。1から n までの範囲に含まれる相異なる要素の中から、「合計が k に等しくなる部分集合が一つも存在しない」という条件を満たすように、できるだけ多くの要素を選びます。そして、そのような選び方が見つかる場合は、選んだ数値を出力します。 例えば、入力が n = 5、k = 3 の場合、出力は [4, 5, 2] となります。 解法のアプローチ この問題を解くためには、以下の手順に従います。 i を (k + 1) / 2 から k - 1 まで1ずつ増やしながら繰り返す： i を出力する i を k + 1 から n まで1ずつ増やしながら繰り返す：

問題概要2つの整数 n と k が与えられます。価値が 1 から n までのコインを無限に持っているものとします。これらのコインを組み合わせて合計をちょうど k にしたいのですが、同じ価値のコインは何枚でも繰り返し使えます。このとき、合計 k を作るために必要なコインの最小枚数を求めましょう。例えば、n = 6、k = 16 が入力された場合、出力は 3 となります。これは「価値 6 のコイン 2 枚」と「価値 4 のコイン 1 枚」を組み合わせて (2 × 6) + 4 = 16 が達成できるためです。解法の考え方この問題は O(1) の定数時間で解くことができます。ポイントは、価値 1 か

問題概要長さ n の文字列 S があり、A または P の 2 種類の文字のみで構成されているものとします。一列に並んだ n 人の学生がおり、S[i] = A ならば i 番目の学生は「怒っている」状態、P ならば「忍耐強い」状態を表します。インデックス i にいる怒った学生は、毎分インデックス i+1 にいる忍耐強い学生を叩きます。ただし、最後の学生は、たとえ怒っていても誰も叩くことができません。また、忍耐強い学生は叩かれた瞬間から、自分自身も怒り出します。このとき、「新しく怒り出す学生がいなくなるまで」にかかる最小の時間(分)を求めるのが本問題です。例えば、入力が S = PPAPP の場

問題概要 4つの整数 n1、n2、k1、k2 が与えられます。ここに2つの箱があり、1つ目の箱には n1 個のボール、2つ目の箱には n2 個のボールが入っています。 Amal（アマル）と Bimal（ビマル）の2人がこのゲームをプレイします。Amal は自分の手番で1個から k1 個のボールを取り除くことができ、Bimal は1個から k2 個のボールを取り除くことができます。Amal が先手となり、2人は交互に手番を進めていきます。そして、自分の手番でボールを取り除けなくなったプレイヤーが負けとなります。このゲームの勝者が誰になるのかを求めるのが課題です。 具体例 例えば、入力が n1

問題概要 文字列 S が与えられます。S には「x」と「a」の2種類の文字が含まれています。いくつかの文字を取り除いた後に残る文字列が「良い文字列」となるようにするとき、残せる文字列の長さの最大値を求めます。ここで「良い文字列」とは、文字列全体の長さの半分を厳密に超える数の「a」が含まれている文字列のことです。 たとえば、入力が S = xaxxxxa の場合、出力は 3 になります。「x」を4つ削除すると文字列は xaa となり、これは長さ 3 の良い文字列だからです。 解法のアプローチ この問題は、次の手順で効率よく解くことができます。 x := 2 ×（S に含まれる a の個数）−