C++

ここでは、n × n の正方行列が与えられた場合を考えます。この行列の中で、次に挙げる値を「特別な要素」と呼びます。 主対角線(左上から右下へ伸びる対角線)上にある値 副対角線(右上から左下へ伸びる対角線)上にある値 上にちょうど (n − 1) / 2 個の行があり、下にも同じ数の行が存在する中央の行に含まれる値 左と右にそれぞれ (n − 1) / 2 個の列が存在する中央の列に含まれる値 この記事の目的は、これらの特別な値すべての合計を求めることです。 たとえば、入力が n = 4、mat = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12},

問題概要整数 k が与えられます。すべての桁が同じ数字で構成されている数を「特殊数(スペシャルナンバー)」と呼びます。例えば、1、11、111、1111 などが特殊数に該当します。特殊数は 1, 11, 111, 1111, 2, 22, 222, 2222, 3, 33, 333, 3333, … という順序で数え上げます。このとき、k までに現れるすべての特殊数に含まれる桁数の合計を求めるのが課題です。なお、k の値は 10000 以下であるものとします。例えば、入力が k = 9999 の場合、出力は 90 になります。解き方のアプローチこの問題を解くためには、次の手順に従います。k を

問題の概要4つの商品を販売しており、i番目の商品の価格は配列「cost[i]」で与えられているとします。商品は文字列「items」に記載された順序で販売されます。このとき、販売によって得られた総売上高を求める必要があります。文字列「items」には1から4までの整数が含まれており、重複があっても構いませんし、並び順も任意です。たとえば、入力が cost = {10, 15, 10, 5}、items = 14214331 である場合、出力は 75 になります。解き方の手順この問題を解くには、以下の手順に従います。total := 0 i := 0 で初期化し、i が items のサイズ未満の

本記事では、与えられた画像がカラ―画像か白黒（モノクロ）画像かを判定するC++プログラムを紹介します。問題の概要n個のピクセルから構成される画像が与えられます。各ピクセルは以下のいずれかの色を持つとします。C（シアン）M（マゼンタ）Y（イエロー）W（ホワイト）G（グレー）B（ブラック）i番目のピクセルの色は文字列 pixels として渡されます。この文字列をもとに、その写真がカラーか白黒かを判定します。判定基準は次のとおりです。ピクセルの中に C、M、Y のいずれかが1つでも含まれていれば、それはカラー写真であり、「Color」と出力します。すべてのピクセルが W、G、B のみで構成されていれ

n行m列のグリッドに区切られた床があるとします。この床全体をランプで照らすことを考えます。ランプは2つのセル(マス)の境界に設置でき、縦方向の境界に置いた場合はその左右の2つのセルを、横方向の境界に置いた場合はその前後の2つのセルを照らします。与えられたnとmに対して、床全体を照らすために必要なランプの最小個数を求めるのがこの問題です。例えば、入力が n = 5、m = 3 の場合、出力は 8 になります。解法のアプローチこの問題は非常にシンプルな計算式で解くことができます。1つのランプが2つのセルを同時に照らせるため、必要なランプ数はセルの総数(n × m)を2で割った値になります。ただし、

すべての小文字の英字アルファベットが刻まれた回転式ダイヤルがあるとします。ダイヤルにはプリンターが取り付けられており、ポインタのある位置の文字が3秒間留まると、その文字が出力（印刷）されます。ダイヤルは初期状態では「a」を指しており、文字を出力した後も初期位置に戻ることはありません。 ここで、文字列 s が与えられるので、この文字列を出力する必要があります。ダイヤルを別の文字へ移動させるたびに、1回分の回転が発生します。与えられた文字列 s を出力するために必要な総回転数を求めてください。 例えば、入力が s = elephant の場合、出力は 63 となります。 解法のアプローチ この問題

問題の概要 3つの要素を持つ配列Aを考えます。A[0] + A[2] = 2 × A[1] が成り立つとき、A[1]はA[0]とA[2]の相加平均（算術平均）であるといえます。3つの数の算術平均偏差 d(A[0], A[1], A[2]) は、次の式で定義されます。 d(A[0], A[1], A[2]) = |A[0] + A[2] − 2 × A[1]| ここで、次の操作を何度でも実行できるものとします。インデックス {0, 1, 2} から異なる2つのインデックス i と j を選び、A[i] を1増やして A[j] を1減らします。このとき、達成できる算術平均偏差の最小値を求めてくださ

n 個の要素を持つ配列 A と数値 m が与えられているとします。n 人の学生が試験を受けており、取りうる最高得点は m です。A[i] は i 番目の学生の得点を表します。各学生の得点は自由に変更できますが、次の条件を満たす必要があります。 どの得点も m を超えないこと すべての得点が整数であること 全学生の平均点が変化しないこと このとき、1 人目の学生の得点を最大化したい場合、割り当てられる最高得点はいくつになるでしょうか。 例 たとえば、入力が A = [1, 2, 3, 4]、m = 10 の場合を考えてみましょう。このときの出力は 10 になります。元の平均点は 2.5 です

整数 n が与えられたとき、その差がちょうど n になる2つの合成数（素数ではない数）a と b を求める問題を考えます。 例えば、入力が n = 512 の場合、出力は 5120 と 4608 となります。実際に確認すると、5120 − 4608 = 512 であり、両方とも合成数なので条件を満たしています。 解法のアプローチ この問題は一見すると探索が必要そうに思えますが、実は非常にシンプルな数学的性質を利用すれば、即座に答えを導き出せます。 答えは、10 × n と 9 × n を出力するだけです。 なぜこの方法が有効なのか？ 10 × n は必ず 10 を約数に持つため、常に合成

問題概要サイズnの2つの配列AとB、および整数xが与えられます。このとき、配列Bの要素を並べ替えることで、0以上n-1以下のすべてのiについて「A[i] + B[i] ≤ x」が成り立つようにできるかどうかを判定するのが目的です。たとえば、入力が A = [1, 2, 3]、B = [1, 1, 2]、x = 4 の場合、出力は True(真)になります。B を [1, 2, 1] のように並べ替えれば、各ペアの合計は 1 + 1 ≤ 4、2 + 2 ≤ 4、3 + 1 ≤ 4 となり、条件をすべて満たすためです。解法のアプローチこの問題は貪欲法(グリーディ法)の考え方で効率よく解けます。片方

問題概要長さnの文字列Sが与えられます。ここで、n個の数値が円状(環状)に並んでいると考えます。数値の実際の値は不明ですが、S[i] = Eであればi番目と(i+1)番目の数値が等しく、Nであれば異なることを示しています。文字列Sの情報をもとに、この数列を実際に再構成できるかどうかを判定します。例えば、入力がS = ENNEENEの場合、[15, 15, 4, 20, 20, 20, 15]という値を割り当てることができるため、出力はTrueになります。解法のポイントこの問題の鍵は、数列が円状に並んでいる点にあります。文字列中にNがちょうど1つだけ含まれるケースを考えてみましょう。この場合、残

問題概要 n個の要素を持つ配列Aと整数kが与えられます。n個のキャンディの山があり、i番目の山にはA[i]個のキャンディが入っています。ここで、2つの異なるインデックスiとj（i != j）を選んで操作を行うと、A[i]個のキャンディを別の山へ追加できます（コピー元の山は減りません）。この操作は何度でも繰り返せますが、どれか一つの山でもキャンディ数がkを厳密に超えると、それ以上操作は行えません。このとき、操作を実行できる最大回数を求めるのが目的です。 例えば、入力が A = [1, 2, 3]、k = 5 の場合、出力は 5 になります。最小の山（A[0] = 1）をコピー元として使い、j =

問題の概要 2つの整数 l と r が与えられているとします。ある店では、食品を a 個ずつまとめたパックを割引価格で販売しており、ある顧客は x 個の食品を購入したいと考えています。この顧客は次のような貪欲な戦略に従って行動します。 まず、x / a の切り捨て値に相当する数だけパックを割引価格で購入します。 その後、残りの x mod a 個の食品を1個ずつ個別に購入しようとします。 しかし、顧客は貪欲なので、残りを1個ずつ買おうとしたとき、その数（x mod a）が a / 2 以上になると、1個ずつ買うよりもパック全体をまとめて購入した方が得だと判断し、結局パックごと買ってしまいま

n 個の要素を持つ配列 A と、q 個のクエリを含むリスト Q が与えられる問題を考えてみましょう。配列 A の各要素は、初期状態で 0 または 1 のいずれかです。各クエリ Query[i] はペア (x, k) で構成されており、それぞれ次のような意味を持ちます。 x = 0(更新クエリ):A[k] の値を反転します。つまり 0 なら 1 に、1 なら 0 に切り替えます。 x = 1(取得クエリ):現在の配列における「k 番目に大きい要素」を出力します。 たとえば、入力が A = [1, 1, 0, 1, 0]、Q = [[1, 2], [0, 1], [1, 2], [1, 0],

問題概要n桁の数字からなる文字列Sが与えられます。「電話番号」とは、桁数がちょうど11桁で、先頭が「8」で始まる番号として定義されます。1回の操作につき、文字列Sから1桁の数字を取り除くことができます。このとき、Sを有効な電話番号に変換できるかどうかを判定してください。例えば、入力が S = 5818005553985 の場合、出力は True となります。これは、先頭が「8」で始まる11文字の文字列「8005553985」を作り出せるためです。解法のアプローチこの問題は、以下の手順で解くことができます。m := S の長さS の末尾に 8 を挿入するもし 8 の位置 <= (m - 1

問題の概要2つの数 c と d が与えられます。Amal は初期状態として、どちらも 0 である2つの数 a と b を持っており、これらに対していくつかの操作を実行したいと考えています。各操作を実行する前に、まず正の整数 k を1つ選びます。その上で、選んだ k を用いて以下のいずれかの操作を行います。a と b の両方に k を加算するa に k を加算し、b から k を減算するb に k を加算し、a から k を減算する目標は、a を c に、b を d に一致させるために必要な最小の操作回数を求めることです。到達不可能な場合は -1 を返します。入力例例えば、入力が c = 3、d

問題概要 n個の要素を持つ2つの配列 A と B があるとします。ここで、次のような操作を考えます。 操作： 2つのインデックス i と j を選び、i 番目の要素を1減らし、j 番目の要素を1増やします。ただし、操作を行った後も配列のすべての要素は非負（0以上）でなければなりません。 この操作を繰り返して配列 A と B を同じ内容にしたい場合、必要な操作の手順（インデックスのペア）を求めてください。どうしても一致させられない場合は -1 を返します。 たとえば、入力が A = [1, 2, 3, 4]、B = [3, 1, 2, 4] のとき、出力は [(1, 0), (2, 0)] とな

問題概要n個の要素からなる配列Aがあるとします。ここでnは偶数であり、A[i]はi番目のカードに書かれた数値を表します。ゲームにはn/2人のプレイヤーが参加し、開始時に各プレイヤーは2枚のカードを受け取ります。このとき、どのプレイヤーの手元でも、2枚のカードに書かれた数値の合計が等しくなるようにカードを配分する方法を見つける必要があります。例えば、入力が A = [1, 5, 7, 4, 4, 3] の場合、出力は [(0, 2), (5, 1), (3, 4)] となります。これは A[0] + A[2] = 8、A[5] + A[1] = 8、A[3] + A[4] = 8 となり、全員の

長さ n（偶数）の文字列 S があるとします。S には「a」と「b」の2種類の文字のみが含まれており、この文字列を修正して、あらゆる長さの接頭辞（先頭から連続する部分文字列）において「a」と「b」の出現回数が等しくなるようにしたいと考えています。 このとき許される操作は、「文字列中の任意の位置を選び、その位置の文字をもう一方の文字（a→b、b→a）に置き換える」というものです。この操作は何度実行しても構いません。最終的に得られた文字列を返してください。 例として、入力が S = aabbbb の場合、出力は baabab となります。 解法のアプローチ この問題を効率的に解く鍵は、文字列を「隣

問題の概要n個の要素を持つ配列Aと、整数Hが与えられます。ここで、Hは敵の体力（HP）を表します。こちらはn個の武器を持っており、i番目の武器のダメージ力はA[i]です。これらの武器を組み合わせて敵を倒しますが、同じ武器を連続して2回使用することはできません。この制約のもとで、敵を倒すために必要な武器の使用回数の最小値を求めます。例えば、入力がA = [2, 1, 7]、H = 11の場合を考えてみましょう。このときの出力は3となります。ダメージ7の武器を使用し、続いてダメージ2の武器、そして再びダメージ7の武器を使うことで敵を倒せるからです。解法のアプローチこの問題を効率的に解くには、以下の