C++

問題の概要 配列numsにn個の整数が与えられていると仮定します。この中から2つの数値を選んでペアを作りますが、その際「2つの要素の配列内における位置の差が、2つの数値の合計と等しい」という条件を満たす必要があります。n個の要素から選べるペアの総数は n(n − 1) / 2 通りであり、その中から条件を満たすペアの個数を求めるのが本記事のテーマです。 例えば、入力が n = 8、nums = {4, 2, 1, 0, 1, 2, 3, 3} である場合、出力は 13 になります。つまり、この配列には条件を満たすペアが13個存在します。 解法のアプローチ すべてのペアを総当たりで確認する方法

h × w のサイズのグリッドが与えられます。グリッドには「白」と「黒」の2種類のセルがあり、白いセルは「.」、黒いセルは「#」で表されます。グリッド内の複数の黒いセルがひとつのポリゴン(多角形)を形成しており、そのポリゴンが持つ辺の数を求めるのがこの問題の目的です。なお、グリッドの最も外側のセルは必ず白であると仮定して構いません。例えば、入力が h = 4、w = 4、grid = {...., .##., .##., ....} の場合、出力は 4 になります。これは、黒いセルが正方形を形成しており、正方形には4つの辺があるためです。解法のアプローチこの問題は、グリッド上のセルの境界(交点

ブリッジエッジ（橋）とは？ 重みなし無向グラフにおけるブリッジエッジ（橋）とは、その辺を取り除いたときにグラフが非連結（複数の連結成分に分断される）となるような辺のことです。本記事では、n個の頂点とm個の辺からなるグラフが与えられたとき、その中に含まれるブリッジの数を求めるC++プログラムを紹介します。なお、対象となるグラフには平行辺や自己ループは含まれないものとします。 問題の例 例として、n = 5、m = 6、edges = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}} という入力が与えられた場合を考えてみましょう。この場合の出力は

問題の概要 ここでは、縦 h × 横 w のサイズを持つグリッドが与えられたとき、光で照らされているセルの数を求めるC++プログラムを紹介します。グリッドのセルには「電球」または「障害物」が置かれています。電球のあるセルは、そのセル自身と上下左右のセルを照らし、光は障害物に遮られない限りまっすぐ伝わっていきます。一方、障害物のあるセルは照らされることがなく、電球の光を遮って他のセルへ光が届かないようにします。電球の位置を配列 bulb、障害物の位置を配列 obstacles として受け取り、グリッド全体で照らされているセルの合計数を求めます。 たとえば、入力が h = 4、w = 4、bulb

問題の概要 高さ h × 幅 w のグリッドが与えられます。グリッドの各セルには電球または障害物が置かれており、電球のあるセルは上下左右のセルを照らします。光は障害物に遮られない限りまっすぐ進みますが、障害物のセル自体は照らすことができず、電球の光が他のセルへ届くのも遮ります。グリッドは文字列の配列として渡され、「#」が障害物、「.」が空きセルを表します。手持ちの電球は1つだけなので、グリッド内の最適な位置に配置したときに照らせるセルの最大数を求める必要があります。 たとえば、入力が h = 4、w = 4、grid = {"#...", "...."

問題概要n個の駅がm本の路線で結ばれているとします。駅には1からnまでの番号が付けられており、すべての路線は双方向に通行可能です。ここで、出発駅srcから目的駅dstへ移動することを考えます。i番目の路線の両端の駅は配列「roads」で与えられ、roads[i]は{station1, station2}という形式で表されます。各駅からは、その駅と接続しているすべての駅へ向かう列車が、時間kjの倍数の時刻に発車します。また、各列車が接続先の駅に到達するまでにはtjの時間がかかります。これらの値は配列「departure」で与えられ、各要素は{tj, kj}という形式です。求めるのは、srcからd

問題の概要 2つの整数 n と m、さらに4つの整数 {ai, bi, ci, di} を含む k 個のタプルが与えられているとします。配列 a、b、c、d の4つが入力として渡され、a[i] は i 番目のタプルの a の値を表します。 ここで、n 個の正の整数からなる狭義単調増加の数列 dp(1 ≤ dp[1] < dp[2] < … < dp[n] ≤ m)を考えます。「集計(tally)」という指標を次のように定義します。 集計 = 条件 dp[b[i]] − dp[a[i]] = c[i] を満たすすべての添字 i における d[i] の総和 該当する i がひとつ

問題の概要 ある建物の中心座標を (xc, yc)、高さを h とします。中心座標と高さは直接わかりませんが、x 座標・y 座標とその地点の高度値 a を含む n 個の観測情報が与えられます。 座標 (x, y) における高度は、次の式で定義されます。 a(x, y) = max(h − |x − xc| − |y − yc|, 0) この式から、建物の中心に近いほど高度が高くなり、一定以上離れると高度が 0 になることがわかります。配列 x には xi、配列 y には yi、配列 a には ai が格納されています。 たとえば、入力が n = 3、x = {3, 3, 2}、y = {4,

問題概要 ここでは、黒いセルと白いセルの2種類のセルを含むグリッドが与えられると仮定します。黒いセルは「#」、白いセルは「.」で表され、グリッドは文字列の配列として渡されます。このグリッドに対して、以下の操作を行います。 黒いセルと辺を共有している白いセルを黒に変換します。この操作を、グリッド内のすべてのセルが黒になるまで繰り返します。 すべてのセルを黒に変換するまでに要した反復回数をカウントします。なお、初期状態のグリッドには必ず1つ以上の黒いセルが含まれているものとします。 例として、h = 4、w = 4、grid = {#..., .#.., ...., ...#} という入力を

問題の概要n個の頂点を持つグラフが与えられていると仮定しましょう。頂点には1からnまでの番号が付けられており、配列「edges」に含まれる辺によって互いに接続されています。さらに、各頂点は1からnの範囲の数値である「x」という値を持ち、その値は配列「values」で与えられます。このとき、グラフの中から「スーパー頂点(super vertex)」と呼ばれる特別な頂点を見つけ出す必要があります。頂点iがスーパー頂点であるとは、頂点1から頂点iへの最短経路上に、i番目の頂点と同じ「x」の値を持つ頂点が存在しないことを意味します。この条件を満たすすべての頂点を出力してください。たとえば、入力が n

ここでは、2行 × n列のグリッドが与えられているとします。このグリッドは、n枚のボードで互いに重ならないように完全に覆われている必要があります。各ボードは赤・青・緑のいずれか1色で塗ります。ただし、隣接する2枚のボードに同じ色を使うことはできません。また、必要がなければ、3色すべてを使う必要もありません。グリッドの構成は配列 grid として与えられ、同じボードは同じ英字で、異なるボードは異なる英字で表現されます。私たちの目的は、条件を満たすボードの塗り方の総数を求めることです。例えば、入力が n = 4、grid = {abbd, accd} の場合、出力は 6 になります。つまり、与えら

問題の概要n個の都市がm本の道路で結ばれているとします。道路はすべて一方通行であり、出発地から目的地への一方向にのみ移動できます。道路の情報は配列roadsに{出発地, 目的地}という形式で与えられます。各都市では小麦の売値が異なり、その価格は配列priceに格納されています（i番目の値はi番目の都市での小麦の価格）。旅行者はどの都市でも小麦を購入でき、移動が許可されている範囲であれば任意の都市へ移動して売却することができます。このとき、小麦の売買によって旅行者が得られる最大の利益を求めるのが本問題です。例えば、入力が n = 5、m = 4、price = {4, 6, 7, 8, 5}、r

問題の概要 ここでは、h × w のサイズを持つグリッドが与えられ、各セルにはそれぞれ固有の値が割り当てられているものとします。この課題のゴールは、偶数の値を持つセルの数をできるだけ多くすることです。 そのために使える操作は次のとおりです。まだ一度も選択していないセルを1つ選び、そのセルの値を1減らし、現在のセルと上下左右で隣接する別のセルの値を1増やします。そして、実行した操作の総数と、各操作における「値を減らすセル」および「値を増やすセル」の座標を出力します。 出力は以下の形式で行います。 操作の回数 1回目：（値を減らすセルの位置） - （値を増やすセルの位置）…… n回目：（値を減

問題概要n個の頂点を含む「最小連結グラフ（木構造）」が与えられます。辺は {始点, 終点, 重み} の形式で配列として渡されます。続いて、{始点, 目的地} という形式のクエリが q 個与えられるので、各クエリに対して、始点から頂点 k を経由して目的地へ至る最短コストパスのコストを求めて出力してください。例えば、入力が n = 6, q = 3, k = 1, edges = {{1, 2, 2}, {1, 3, 4}, {3, 4, 2}, {3, 5, 3}, {5, 6, 2}}, queries = {{1, 4}, {2, 6}, {2, 5}} の場合、出力は 6 11 9 とな

n個の都市と、それらをつなぐm本の道路があるとします。各道路は {始点, 終点, 重み} という形式で配列として与えられます。ここで、3つの都市 s・t・k からなるトリプレット (s, t, k) を考えます。このとき、都市 s から都市 t へ移動するために必要な最小時間を求めます。ただし、s から t へ移動する際には、番号 1 から k までの都市だけを経由することができます。もし t に到達できない場合は 0 を返します。すべてのトリプレット (s, t, k) について最小時間を計算し、その合計を出力してください。たとえば、入力が n = 4、m = 2、edges = {{1,

問題概要 2つの整数配列 a と b が与えられ、それぞれ n 個と m 個の要素を持っているとします。これらの配列から値を取り出し、n 個または m 個のうち小さい方の数だけペアを作成します。各ペアには、必ず配列 a からの値を1つと配列 b からの値を1つ含める必要があります。そして、すべてのペアにおける2つの値の差が「最小かつ同一」になるようにペアを構成し、その差の値を出力します。 たとえば、入力が n = 4、m = 4、a = {2, 3, 4, 7}、b = {3, 4, 6, 5} の場合、出力は 1 になります。 このとき作成できるペアは以下のとおりです。 (3, 4), (

問題の概要 ある会社にはn人の従業員が在籍しており、各従業員はスキルに応じて1からkまでのいずれかのランクに分類されています。配列skillにはランクごとの従業員数が記録されており、skill[i]はランクiを持つ従業員の人数を表します。 ここで、会社に新しい支店が開設されることになり、さまざまなスキルを持つ従業員をそちらへ異動させることになりました。異動させる従業員の総数はm人です。今回の課題は、m人を適切に配置する方法を見つけ出し、次の式を最小化するような支店の従業員ランク配分表branchを求めることです。 最小化する式：max(branch[i]/m − skill[i]/n) なお

問題の概要h × w のサイズを持つ行列が与えられ、各要素には英字が格納されているとします。この行列をもとに、すべての行と列が回文となっている行列を作成することを考えます。作成にあたっては、元の行列の行や列を自由に入れ替えることは許されますが、要素そのものを書き換えることはできません。つまり、「a」を「b」に変更するような操作は禁止されています。回文行列を作成できる場合は true を、作成できない場合は false を返します。例として、入力が h = 4、w = 4、mat = {xxyy, xyxx, yxxy, xyyy} である場合、出力は true となります。解法のアプローチこの

この記事では、N×M のグリッドに対して特定の条件を満たすシーケンスのペア (A, B) の総数を求める問題を、C++ を使って効率的に解く方法を解説します。 問題の概要 3つの整数 N、M、K が与えられます。ここで、N 個の行（横方向）と M 個の列（縦方向）からなるグリッドを考えます。各セルには 1 以上 K 以下の整数を書き込むこととし、これをもとにシーケンス A と B を次のように定義します。 1 から N までの各 i について、A[i] は i 番目の行に含まれるすべての要素の最小値 1 から M までの各 j について、B[j] は j 番目の列に含まれるすべての要素の最大

問題概要 N個の要素を持つ配列Dがあるとします。あるコードフェスティバルには、Amalを含めて合計N+1人の参加者がいます。Amalが調べたところ、自分の街の地元時刻とi番目の人の街の地元時刻との時差はD[i]時間であることが分かりました。 2つの都市AとBの時差は、次のように定義されます。都市Aの地元時刻が0時である瞬間に、都市Bの地元時刻がd時だった場合、この2つの都市の時差は「d」と「24−d」のうち小さい方の値となります。ここでは24時間表記を使用します。 Amalは、N+1人の中から任意の2人を選んだすべてのペアについて、それぞれの都市間の時差を書き出しました。これらの中で最も小さ