C++

問題概要整数の順列 seq と、0 から n-1 までの整数を含むサイズ m の整数ペアの配列 pairs が与えられます。seq[i] = i（0 ≤ i < n） となる要素の数を最大化するため、次の操作を可能な限り何度でも実行できます。整数 j（0 ≤ j < m）を 1 つ選び、seq[pairs[j] の最初の値] と seq[pairs[j] の 2 番目の値] を入れ替える。操作を複数回行った後、seq[i] = i を満たす i の個数の最大値を求めてください。入力例と出力例たとえば、入力が n = 4、m = 2、seq = {0, 3, 2, 1}、pairs

問題の概要n個の都市と、それらを結ぶm本の道路があるとします。各道路は一方通行であり、出発都市から目的地の都市まで移動するには一定の時間がかかります。道路の情報は配列 roads として与えられ、各要素は (出発地, 目的地, 時間) という形式で表されます。ここで、ある人物がある都市を出発し、1本以上の道路を通って再び出発した都市へ戻ってくる旅を「周回旅行(ラウンドトリップ)」と定義します。各都市について、その都市を起点とした周回旅行が可能かどうかを判定してください。可能であれば周回に必要な時間を出力し、不可能な場合は -1 を出力します。たとえば、入力が n = 4、m = 4、roads

問題文 あるメーカーが特定の製品向けに部品を製造しているとします。このメーカーは n 種類の異なる部品を保有しており、各部品は3つの基準で評価されます。n 個の部品の評価は配列 ratings として与えられ、各要素は (A, B, C) という形式で表されます。ここで A、B、C はそれぞれ異なる評価基準のスコアです。 さて、ある OEM(相手先ブランド製造企業)が、このメーカーから自社製品のために m 個の部品を購入したいと考えています。OEM は以下の条件を満たす部品を選択します。 同じ部品を2個以上購入してはならない。 V = |Aの評価値の合計| + |Bの評価値の合計| + |

問題の概要文字列Sが与えられます。Sの各文字は「0」「1」または「?」のいずれかです。それぞれの「?」を0または1に置き換えることで、新しい文字列Tを作成することを考えます。Tのアンバランス度とは、0 ≤ l ≤ r < |S| を満たすすべての区間 [l, r] について、その範囲内に出現する0の個数と1の個数の差の絶対値を計算し、その中の最大値を取ったものです。ここで、Tのアンバランス度としてあり得る最小値を求めることが目標です。例えば、入力が S = "0??0" の場合、出力は 2 になります。解法のアプローチこの問題は、二分探索と貪欲法を組み合わせることで効

この記事では、1・2・3のいずれかの値で構成される数列をもとに、隣接要素の差の絶対値を繰り返し計算して最終的に残る値を求めるC++プログラムを紹介します。単純なシミュレーションではなく、二項係数の偶奇(パリティ)を利用した効率的な解法を解説します。 問題概要 1、2、または3のいずれかの値を持つN個の要素からなる数列Aがあるとします。これをもとに、次のように二次元配列Xを定義します。 X[1][j] = A[j](ただし j は 1 以上 N 以下) X[i][j] = |X[i-1][j] − X[i-1][j+1]|(ただし i は 2 以上 N 以下、j は 1 以上 N+1−i 以

問題の概要N個の要素を持つ配列Aがあるとしましょう。N個の箱が円状に並べられており、i番目の箱にはA[i]個の石が入っています。以下の操作を繰り返し行うことで、すべての箱から石を取り除くことができるかどうかを判定する必要があります。操作の内容： 箱を1つ選択します(これをi番目の箱と呼びます)。jを1からNまで変化させながら、各ステップで(i+j)番目の箱からちょうどj個の石を取り除きます。なお、(N+k)番目の箱はk番目の箱として扱われます。選ばれた箱に十分な数の石が残っていない場合、この操作は実行できません。例えば、入力が A = [4, 5, 1, 2, 3] の場合、出力は True

ある数値 N が与えられたとします。ケーキ売り場では、ケーキが1つ40ルピー、ドーナツが1つ70ルピーで販売されています。このとき、所持金 N ルピーを使って、これらの商品をちょうど N ルピ―ぴったりで購入できるかどうかを判定します。 例えば、N = 110 の場合、40 + 70 = 110 となるため、出力は True（購入可能）になります。 解決のアプローチ この問題は、深さ優先探索（DFS）を用いて解くことができます。基本的な考え方は以下の通りです。 現在の合計金額 i を引数として DFS を実行します。 i が n より大きければ、その経路は失敗なので false を返します。

問題の概要 N個の要素を持つ配列Aがあるとします。ここにN匹の猫がいて、1からNまでの番号が付けられています。すべての猫は帽子を被っており、i番目の猫は「自分以外のN−1匹の猫が被っている帽子の中には、ちょうどA[i]種類の異なる色が存在する」と発言します。このとき、すべての猫の発言と矛盾しない帽子の色の割り当てが存在するかどうかを判定するのがこの問題です。 たとえば、入力が A = [1, 2, 2] の場合、答えは True（真）になります。猫1・猫2・猫3がそれぞれ「赤・青・青」の帽子を被ることで、全員の発言と整合するためです。 解法のアプローチ この問題は、配列内の最小値・最大値とそ

問題概要ある通信事業者が「オールインワン」というサービスを導入したとします。このサービスは、n社のOTTコンテンツプロバイダすべてにアクセスできるようになり、固定料金はkドルです。一方、各OTTプラットフォームに直接契約する場合は、それぞれ個別の料金を支払う必要があります。しかし、毎月すべてのプラットフォームが必要になるとは限りません。そこで、必要な期間だけ賢くサービスを利用し、コストを最小限に抑える方法を考えることになります。プラットフォームiの利用開始月は配列 start_month に、利用終了月は配列 end_month に格納されています。また、各プラットフォームの契約料金は配列 p

問題概要ここでは、x × y のサイズを持つグリッドが与えられるとします。グリッドには「ブロックされたセル」と「通行可能なセル」の2種類が存在し、ブロックされたセルには進入できません。グリッドは2次元配列として表現され、ブロックされたセルは #、通行可能なセルは . で表されます。目標は、左上のセル (0, 0) から右下のセル (x-1, y-1) へ移動することです。ただし、移動は「右へ進む」か「下へ進む」の2種類のみが許されており、通れるのは通行可能なセルだけです。なお、始点と終点はどちらも通行可能であることが保証されています。仮に現状のままでは目的地へ到達できない場合でも、ブロックされ

ナイフを武器に敵と戦うアクションゲームを想像してみてください。主人公はナイフで敵を斬ることも、投げつけることもできます。ただし、一度投げたナイフは二度と手元に戻ってきません。i 番目のナイフのダメージ情報は配列 knives に {斬撃ダメージ, 投擲ダメージ} というペアの形式で与えられます。「斬撃(slash)」はそのナイフで敵を切りつけた際に与えるダメージ、「投擲(throw)」はそのナイフを敵に投げた際に与えるダメージです。斬撃は何度でも繰り返し実行できますが、投擲は各ナイフにつき1回しか行えません。ここで、体力 h を持つ敵が現れます。敵の体力を 0 にして倒すまでに必要な操作回数(

問題の概要高さ h × 幅 w のグリッドが与えられます。グリッドには「ブロックされたセル（壁）」と「ブロックされていないセル（通路）」の2種類があり、2次元配列として表現されます。ブロックされたセルは #、ブロックされていないセルは . で示されます。このグリッド上で、ある通路セルから別の通路セルへ移動することを考えます。移動できるのは上下左右の4方向のみで、斜め移動は禁止されています。また、通過できるのは . のセルだけです。この条件のもとで、あるセルから別のセルへ到達するために必要な最大の移動回数を求めるのが本記事の目的です。入力例たとえば、h = 4、w = 4、grid = {..#

問題の概要2次元平面上に2つの点 a と b があり、それぞれ座標 (x1, y1)、(x2, y2) を持っているとします。現在位置は点 a で、1回の移動ごとに上下左右のいずれかの方向へちょうど距離1だけ進むことができます。ここで、点 a から点 b へ移動し、その後点 a に戻り、さらに再度点 b へ向かうという一連の移動を行います。ただし、点 a と点 b 以外の同じ座標点を2回以上通ることは禁止されています。この旅全体で行う移動手順を求めて出力してください。移動方向は、右なら「R」、左なら「L」、上なら「U」、下なら「D」の文字で表します。なお、x2 > x1 かつ y2 &g

問題の概要空のシーケンスと、処理すべき n 個のクエリが与えられます。クエリは配列 queries に {query, data} の形式で格納されており、次の3種類があります。query = 1: 指定されたデータをシーケンスの末尾に追加する。query = 2: シーケンスの先頭にある要素を出力し、その後その要素を削除する。query = 3: シーケンスを昇順にソートする。なお、クエリタイプ2と3では常に data = 0 が渡されることに注意してください。入力例n = 9、queries = {{1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}, {2, 0}

問題の概要縦 h × 横 w のサイズを持つグリッドが与えられているとします。ロボットはセル (0, 0) の位置からスタートし、(h - 1, w - 1) の位置へ移動する必要があります。グリッドのセルには「ブロックされているセル」と「ブロックされていないセル」の2種類があり、ロボットはブロックされていないセルのみを通過できます。移動は上下左右の4方向が可能です。ロボットはあるセルから隣接するセルへ任意の方向に移動できるため、スタートからゴールまで複数の経路が存在する可能性があります。本問題では、(0, 0) から (h - 1, w - 1) までの経路を1本だけ残し、その経路に含まれな

問題概要 n 個の頂点と m 本の辺からなる重み付き無向グラフを考えます。グラフの「スコア」は、含まれるすべての辺の重みの総和として定義されます。辺の重みは負になることもあり、そのような辺を取り除くとかえってスコアが増えてしまいます。 ここで求めたいのは、グラフを連結状態に保ったまま不要な辺を削除してスコアを最小化し、「スコアを最大でどれだけ減らせるか」を計算することです。 グラフは配列 edges として与えられ、各要素は {weight, {vertex1, vertex2}}（重みと両端の頂点）という形式で表されます。 入力例と出力 たとえば n = 5、m = 6、edges = {

2つの n × n ピクセルの正方形画像 first と second が与えられたとき、second を 90 度単位で回転および平行移動させて first と一致させられるかどうかを判定する C++ プログラムを解説します。画素は黒（x）と白（.）の 2 値で表現されます。 問題の概要 入力例: n = 4 first = {..x., x.x., x.xx, xx..} second = {..xx, x.xx, .x.x, ..x.} 出力: false（0） この例では、second をどう回転・平行移動しても first と一致しないため false が返されます。 アルゴリ

問題の概要赤と青の2色の車に対する販売需要があるとします。ある自動車会社は、価格の異なる赤い車をp台、青い車をq台販売することに決めました。現在、同社の在庫には赤い車がa台、青い車がb台、そしてまだ塗装されていない無彩色の車がc台あります。各車の価値は配列A、B、Cとして与えられます。同社は1日あたりp + q台の車を販売し、そこから利益を最大化しなければなりません。無彩色の車は、赤または青のどちらの色にも塗装することが可能です。この記事では、車の販売によって得られる最大の利益を求める方法を解説します。入力例と出力たとえば、入力が p = 3、q = 3、a = 3、b = 3、c = 2、A

2n個の文字があるとします。それぞれの文字には1からnまでの整数が書かれており、同じ数字が書かれた文字は必ず2つずつ存在します。これらの文字はm個のスタックに分けて積まれており、i番目のスタックにはstack[i]の文字が格納されています。私たちの課題は、以下のルールに従ってすべてのスタックを空にできるかどうかを判定することです。任意の2つのスタックを選び、それぞれの一番上の文字を取り除きます。取り除いた2つの文字には、同じ数字が書かれている必要があります。この操作を繰り返してm個のスタックすべてを空にできればtrueを出力し、そうでなければfalseを返します。問題の例たとえば、入力が n

配列 nums に n 個の整数が与えられているとします。ここでの課題は、配列内の数が「ペアワイズ互いに素(pairwise coprime)」「集合的に互いに素(setwise coprime)」「互いに素ではない(not coprime)」のどれに分類されるかを判定することです。 互いに素の定義 ペアワイズ互いに素: 任意の2つの数 nums[i] と nums[j](i < j)について、gcd(nums[i], nums[j]) = 1 が成り立つとき、配列内の数はペアワイズ互いに素であるといいます。この条件は配列内のすべての数のペアに対して成立しなければなりません。 集合的