C++

ここでは、それぞれD個の要素を持つ2つの配列 p と c、および整数 G が与えられます。あるプログラミングコンテストでは、各問題は難易度に応じて配点が設定されており、難易度iの問題は1問あたり 100×i 点となります。コンテスト全体の出題数は p[0] + ... + p[D-1] 問です。参加者のtotal_score（合計得点）は、次の2つの要素の合計として定義されます。 基本得点： 解いたすべての問題の配点の総和 ボーナス点： 難易度iの問題をすべて完答すると、基本得点に加えて完全ボーナス c[i] が付与される Amalはコンテストに初めて挑戦し、まだ1問も解いていません。彼

グラフGの隣接行列が与えられたとします。このとき、すべての辺が「隣接する2つの集合」に属する頂点同士を結ぶという条件を満たすように、頂点を空でない集合 V1, …, Vk に分割できるかどうかを判定します。分割が可能な場合は、そのような分割における集合数 k の最大値を求めてください。例えば、入力が以下のような隣接行列だったとします。010110101001010100101000100000010000この場合、出力は 4 となります。アプローチの考え方この問題は、各頂点をBFS（幅優先探索）による始点からの距離（レベル）で分類することで解けます。条件を満たす分割では、すべての辺がレベル差ち

問題概要2つの配列 X と H(どちらも N 個の要素を持つ)、および2つの整数 D と A が与えられます。この問題では、銀狐が N 匹のモンスターと戦うという設定です。モンスターたちは一列に並んでおり、i 番目のモンスターの座標は X[i]、体力は H[i] です。銀狐は爆弾を使って攻撃することができます。座標 x の位置に爆弾を落とすと、x − D から x + D の範囲内にいるすべてのモンスターにダメージを与え、それぞれの体力が A 減少します。すべてのモンスターの体力が 0 以下になった時点で銀狐の勝利となります。目標は、勝利するために必要な爆弾の最小使用回数を求めることです。入力

ある整数 A が与えられたとき、「A 以上で最も近い興味深い数（interesting number）」を求めることを考えましょう。ここで興味深い数とは、各桁の数字の合計が 4 で割り切れる数として定義されます。 たとえば、入力が A = 432 のとき、出力は 435 になります。これは 4 + 3 + 5 = 12 となり、12 が 4 で割り切れるためです。 解法の考え方 この問題はとてもシンプルな戦略で解決できます。A の各桁の合計が 4 で割り切れるようになるまで、A を 1 ずつ増やしていけばよいのです。 手順を疑似コードで表すと、次のようになります。 while ((A / 10

問題の概要 H行・W列のグリッドを考えます。各マスは「空きマス（整頓済み）」か「障害物マス（未整頓）」のいずれかです。このうち、0個以上の空きマスに自由にランプを設置できます。 ランプは上下左右の4方向へ光を放ち、グリッドの端、あるいは最初に障害物マスへ到達する直前までのセルを照らします（障害物のセル自体は照らされません）。もちろん、ランプを置いたセルそのものも照らされます。G[i, j] が「.」ならそのセルは空きマス、「#」なら障害物マスを表します。 空きマスの総数を K とすると、ランプの置き方は全部で 2^K 通り存在します。それぞれの置き方ごとに「1つ以上のランプによって照らされるセ

n 個の要素を持つ配列 A と、ある整数 m が与えられます。次の式が成立するような配列の並べ替えが存在するかどうかを判定してください。 $$\mathrm{\sum_{i=1}^{n} \sum_{j=1}^{n}\frac{A[j]}{j} = m}$$ なお、A[j]/j の計算では丸め処理（切り捨て）は行われません。 例として、入力が A = [2, 5, 1]、m = 8 の場合を考えてみましょう。このとき出力は True になります。配列を [1, 2, 5] と並べ替えると、(1/1 + 2/2 + 5/3) + (2/2 + 5/3) + (5/3) = 8 となるためです。

問題概要 4つの整数 p、a、b、c が与えられます。プールには3人の水泳選手がおり、それぞれ a 分、b 分、c 分かけてプールを往復します。開始時刻から数えて、1人目の選手は 0, a, 2a, 3a,… 分後にプールの左側に到着し、2人目は 0, b, 2b, 3b,… 分後、3人目は 0, c, 2c, 3c,… 分後に左側へ戻ってきます。 ここで、選手たちが泳ぎ始めてから p 分後にプールを訪れたとします。このとき、少なくとも1人の選手がプールの左側にいる状態になるまでの最小待ち時間を求めるのがこの問題です。 入力例と出力例 たとえば、入力が p = 2; a = 6; b =

問題概要 N個の要素を持つ配列Aが与えられます。このとき、次の条件を満たす整数のペア(l, r)の個数を求めてください。 A[l] XOR A[l+1] XOR … XOR A[r] = A[l] + A[l+1] + … + A[r] つまり、「区間内の要素をXORした結果」と「区間内の要素を足し合わせた結果」が一致するような区間を数え上げる問題です。 例えば、入力が A = [2, 5, 4, 6] の場合、出力は 5 になります。これは、(1,1)、(2,2)、(3,3)、(4,4)、(1,2) の5つのペアが条件を満たすためです。 解法のポイント すべての(l, r)の組み合わせを素

問題概要n 文字の文字列 S を考えます。S には小文字の英字のみが含まれています。ここで、0 以上 n 以下の範囲から整数 k を1つ選び、S から k 個の文字を選んで任意の順序に並べ替えます。このとき、選ばれなかった残りの文字は元の位置にそのまま留まります。この操作全体はちょうど一度だけ実行します。目的は、操作後に S が完全にアルファベット順（辞書順）にソートされた状態となるような、k の値を求めることです。例えば、入力が S = acdb の場合、出力は 3 になります。これは最初の文字 a がすでに正しい位置にあるため、残りの3文字（c、d、b）を並べ替えればよいからです。解法のア

問題概要 n個の要素からなる配列Aがあるとします。関数F(p)は、配列pの隣接する要素同士の合計値を昇順にソートした配列として定義されます。すなわち、F(p) = sort([p1+p2, p2+p3, ..., pn-1+pn]) です。ここで、ある順列Aが与えられたとき、F(A)の結果が元の配列と完全に同じになる「別の」順列を見つけることが課題となります。 具体例 入力が A = [2, 1, 6, 5, 4, 3] の場合を考えてみましょう。このときの出力の一例は [1, 2, 5, 6, 3, 4] です。 まず元の配列について計算すると: F(A) = sort([2+1, 1+6,

問題の概要要素数 K の配列 A があるとします。ここに N 人の子どもとゲームマスターがおり、ゲームは全部で K ラウンド行われます。第 i ラウンドでは、ゲームマスターが「A[i] 人のグループを作れ」と宣告します。子どもたちは A[i] 人ずつのグループをできるだけ多く結成し、どのグループにも所属できなかった子どもはその場でゲームから脱落します。残った子どもたちは次のラウンドへ進みます（脱落者が誰も出ないラウンドがあっても構いません）。そして第 K ラウンド終了時にちょうど 2 人が残り、その 2 人が優勝者となります。求めたいのは、ゲーム開始前の子どもの人数 N として考えられる最小値

N個の要素からなる配列Aがあるとします。1回の操作ごとに、任意の要素を1つ選び、その値を1増やすか1減らすことができます。ここで、次の2つの条件を満たすために必要な最小の操作回数を求めるのが目標です。 1以上n以下のすべてのiについて、第1項から第i項までの総和(接頭辞和)が0にならないこと。 1以上n−1以下のすべてのiについて、第1項から第i項までの総和の符号が、第1項から第(i+1)項までの総和の符号と異なること。 言い換えると、接頭辞和は正と負の間で交互に入れ替わりながら推移し、途中で一度も0になってはいけない、という条件です。 入力例と出力例 たとえば入力が A = [1, -3

問題概要座標 (x, y) が与えられているとします。2次元グリッド上で、ロボットは初期位置 (0, 0) におり、目標地点 (x, y) への移動を目指しています。ロボットは1回のコマンドで「上」「下」「左」「右」のいずれかに移動するか、現在のマスにとどまる（待機する）ことができます。ここで、目的地に到達するまでに必要なコマンド数、つまりステップ数の最小値を求めることが課題です。入力例と出力例たとえば、入力が x = 3、y = 4 の場合、出力は 7 になります。解法のアプローチこの問題は、以下の式を使って答えを直接計算することで解けます。return x + y + min(|x - y

問題概要N個の要素を持つ配列 A と、ある整数 K が与えられます。0 以上 K 以下の範囲にある整数 X に対して、次のような関数 f(X) を定義します。f(X) = (X XOR A[1]) + (X XOR A[2]) + ... + (X XOR A[N])このとき、f(X) が取り得る最大値を求めるのがこの問題の目的です。たとえば、入力が K = 7、A = [1, 6, 3] の場合を考えてみましょう。X = 4 を選ぶと、f(4) = (4 XOR 1) + (4 XOR 6) + (4 XOR 3) = 5 + 2 + 7 = 14となり、これが最大値となります。解き方（アル

2つの数 a と b が与えられたとき、ある値 x を選んで (a XOR x) + (b XOR x) の最小値を求めることを考えます。たとえば、入力が a = 6、b = 12 の場合、出力は 10 になります。x = 4 を選ぶと、(6 XOR 4) + (12 XOR 4) = 2 + 8 = 10 となるからです。考え方各ビットの位置ごとに考えてみましょう。a と b のビットが同じ（両方とも0、または両方とも1）であれば、x のそのビットを同じ値にすることで、両方のXOR結果はその桁で0になります。a と b のビットが異なる場合は、x をどのように選んでも、必ずどちらか一方がその

問題概要 H行W列のマトリックス（グリッド）が与えられます。各セルには「.」または「#」が格納されており、「.」は通行可能なスペース、「#」は通行できないブロックを表します。 Amalは家から市場へ向かいます。家はグリッドの左上隅のセルにあり、市場は右下隅にあります。Amalは上下左右の4方向に1セルずつ移動できますが、移動先は必ず通行可能なセルである必要があります。町の外に出ることや、ブロックされたセルに入ることはできません。 ただし、Amalの体力なら、自分で選んだ2×2セルの正方形領域内にあるすべてのブロックを、わずか1回のパンチで破壊し、そのセルを通行可能にすることができます。ここで

問題概要n個の要素を持つ配列Aと、m個の要素を持つ配列Bが与えられたとします。ここで、Aからある要素aを、Bからある要素bをそれぞれ選び、その合計 a + b が配列AにもBにも存在しないようにする必要があります。例えば、入力が A = [3, 2, 2]、B = [1, 5, 7, 7, 9] の場合、出力は [3, 9] となります。これは 3 + 9 = 12 がどちらの配列にも存在しないためです（他にも有効な答えは存在します）。解法のアプローチこの問題は、非常にシンプルな発想で効率的に解くことができます。ポイントは「各配列の最大値同士を組み合わせる」ことです。すべての要素が正の整数であ

問題概要 n個の要素を持つ配列Aがあるとします。ある電器店で昨夜、強盗事件が発生しました。店内にあったすべてのキーボードには、ある整数xから始まる連番が振られていました。例えば、x=4で店に3台のキーボードがあれば、それらの番号は4、5、6です。また、x=10で7台あれば、番号は10、11、12、13、14、15、16となります。強盗の後、n台のキーボードだけが残り、その番号が配列Aに格納されています。ここで、盗まれたキーボードの最小台数を求めることが課題です。 例えば、入力が A = [10, 13, 12, 8] の場合、出力は 2 になります。これは x = 8 のとき、盗まれたキーボー

問題の概要 n個の要素を持つ配列Aがあるとします。A[i]はi番目の学生のプログラミングスキルを表しており、配列内のすべての要素は互いに異なります。これらの学生を、次の条件を満たすようにチームへ分割することを考えます。 |A[i] − A[j]| = 1 となるような2人の学生(iとj)が、同じチームに所属しないこと チームの数は可能な限り少なくすること たとえば、入力が A = [2, 3, 4, 99, 100] の場合、出力は 2 となります。スキルが連続する値(2と3、99と100など)を持つ学生同士は同じチームに入れないため、最低でも2つのチームが必要になるからです。 解法の考

問題の概要 5つの整数 n、k1、k2、w、b が与えられるとします。ここで、2 × n のマス目からなるボードを考えます。1行目の左端から k1 個のセル、2行目の左端から k2 個のセルは白色に塗られており、残りのセルはすべて黒色です。さらに、白いドミノ w 個と黒いドミノ b 個(いずれも 2 × 1 のサイズ)を持っています。 白いドミノは、その両方のセルが白色であり、かつ他のドミノに占有されていない場合にのみ配置できます。同様に、黒いドミノは、両方のセルが黒色で未占有の場合にのみ配置できます。ドミノは縦方向・横方向どちらにも置けるものとして、与えられた w + b 個のドミノをすべて