C++

問題概要 5つの整数 b、p、f、h、c が与えられます。レストランでは2種類のバーガーを販売しており、それぞれ次の材料が必要です。 ハンバーガー： パン2個＋ビーフパティ1枚 → h ルピーで販売 チキンバーガー： パン2個＋チキンカツ1枚 → c ルピーで販売 現在の在庫は、パンが b 個、ビーフパティが p 枚、チキンカツが f 枚です。この条件下で、売上の最大値（最大利益）を求めます。 例えば、b = 7、p = 5、f = 2、h = 10、c = 12 の場合、出力は 34 になります。これは、ハンバーガー1個とチキンバーガー2個を作ると、収入が 1×10 ＋ 2×12 ＝ 3

問題概要 n個の要素からなる配列Aがあるとします。1回の操作では、配列Aの中から任意の1つの要素を選び、その値に1を加えることができます。このとき、配列内の全要素の合計と積の両方をゼロ以外の値にするには、最小で何回の操作が必要かを求めるのがこの問題です。 例として、入力が A = [-1, 0, 0, 1] の場合を考えてみましょう。初期状態では合計も積も 0 になっているため、出力は 2 となります。2番目と3番目の要素（いずれも 0）にそれぞれ1を加えて配列を [-1, 1, 1, 1] にすれば、合計は 2、積は -1 となり、どちらもゼロ以外の値になります。 解法の考え方 この問題は

要素数nの配列Aと、3つの値 l・r・k が与えられているとします。Amalはチョコレートを購入したいのですが、高すぎるチョコレートも安すぎるチョコレートも買いません。店にはn種類のチョコレートバーが並んでおり、それぞれの価格は配列Aで表されています。ここで、価格が r より大きいものは「高すぎる」、l より小さいものは「安すぎる」と定義します。また、Amalが使える金額は最大でもkルピーです。このとき、彼が購入できるチョコレートの最大個数を求めるのが本問題です。入力例と出力例たとえば、入力が A = [1, 2, 3, 4, 5, 6]、l = 3、r = 5、k = 10 の場合、出力は

問題概要 2つの整数 r、c と、n × m のサイズを持つグリッドが与えられます。グリッドには黒く塗られたセルと、白いままのセルが混在しています。1回の操作では、任意の黒いセルを1つ選び、次の2つのうちどちらか一方を必ず実行します。 そのセルが属する行全体を黒に塗る そのセルが属する列全体を黒に塗る このとき、r行目とc列目のセルを黒にするために必要な最小の操作回数を求めます。どうしても実現できない場合は -1 を返してください。 たとえば、入力が次のようなグリッドだったとします。 WBWWW BBBWB WWBBB r = 0、c = 3 のとき、出力は 1 になります。これは、1

要素数 n の配列 A と、もう一つの値 c が与えられているとします。システムには「クレイジーなワードプロセッサ」が存在し、文字を入力することはできますが、連続して c 秒間入力を行わないと、それまでに書いたすべての文字が消去されてしまいます。A[i] は i 番目の文字を入力した時刻を表します。このとき、n 文字すべてを入力し終えた後、画面に残る文字数の合計を求める必要があります。例えば、入力が A = [1, 3, 8, 14, 19, 20]、c = 5 の場合、出力は 3 になります。時刻 8 の時点では画面上に 3 文字が表示されていますが、その後時刻 13 ですべての文字が消去さ

N個の要素を持つ配列Aと、ある数値Tがあるとします。Amalはプログラミングコンテストへの参加を考えています。コンテストの制限時間はT分間で、全部でN問の問題が出題されます。i番目の問題を解くにはA[i]分の時間がかかります。彼はN問の中から0問以上を選んで解きますが、選んだ問題を解くのにかかる合計時間はT分を超えてはなりません。このとき、選択した問題の合計時間として実現できる最長の時間を求めます。 たとえば、入力がT = 17、A = [2, 3, 5, 7, 11]である場合、出力は17になります。これは、最初の4問を選ぶと2 + 3 + 5 + 7 = 17分となり、これがT分を超えな

問題概要 数字だけで構成された文字列 S と整数 M が与えられます。S に含まれる最大の桁の値を d とします。d+1 以上の整数 n を基数として選び、文字列 S を n 進法の数として解釈したとき、その値が M 以下になるような基数は何通り存在するかを求めます。 例えば、S = 999、M = 1500 という入力の場合、出力は 3 になります。10進数として解釈すると 999、11進数では 1197、12進数では 1413 となり、13進数以上では値が 1500 を超えてしまうため、条件を満たすのはこの 3 通りだけです。 アルゴリズムの考え方 基数 n が大きくなるほど、S を n

ある数 N が与えられたとします。ここで、正整数 x に対して定義される関数 gcdSum(x) は、「その整数自身」と「その整数の各桁の合計（桁和）」の最大公約数（GCD）を表します。この記事では、gcdSum(x) > 1 を満たす最小の整数 x（n 以上）を求める方法を解説します。例えば、入力が N = 31 の場合、出力は 33 になります。その理由は次の通りです。31 と (3+1)=4 の GCD は 132 と (3+2)=5 の GCD は 133 と (3+3)=6 の GCD は 3 ← 初めて 1 より大きくなるアルゴリズムの手順この問題は、n から順に候補を調べて

問題の概要 要素数Nの2つの配列AとBがあるとします。Amal（アマル）とBimal（ビマル）の2人が、1からNまでの番号が振られたマスを持つ盤面でゲームを行います。盤面にはN-1本の道があり、i番目の道はマスA[i]とマスB[i]を結んでいます。どのマスからでも、隣接するマスへの移動を繰り返すことで他のすべてのマスに到達できます。つまり、この盤面は木構造になっています。 初期状態では、マス1が黒色、マスNが白色に塗られており、それ以外のマスは無色です。Amalが先手となり、2人は交互に手番を進めます。Amalは黒いマスに隣接する無色のマスを選んで黒く塗り、Bimalは白いマスに隣接する無色

2つの整数 N と K が与えられます。ここで、N 個の頂点を持つ無向グラフについて考えます。このグラフは以下の条件をすべて満たす必要があります。グラフは単純グラフであり、かつ連結である頂点には 1 から N までの番号が付けられているグラフの辺の数を M とすると、辺には 1 から M までの番号が付けられており、各辺の長さは 1 です。辺 i は頂点 U[i] と頂点 V[i] を結びますi < j を満たす頂点のペア (i, j) のうち、2 頂点間の最短距離がちょうど 2 になるものが正確に K 組存在するこのようなグラフが存在する場合はそれを構築して出力し、存在しない場合は -

この記事では、2つの整数 l と r が与えられたとき、その範囲（両端を含む）に存在する「各桁の数字がすべて異なる」整数 x を見つけるC++のプログラムを紹介します。 例えば、入力が l = 211、r = 230 の場合、出力は 213 となります。211は「1」が重複しているため条件を満たしませんが、213は各桁（2・1・3）がすべて異なるため有効な答えです。 解法のアプローチ この問題は、以下の手順で解くことができます。 l から r までの各整数 k を順番に調べます。 k を文字列に変換します。 文字列の各文字（桁）をセット（set）に挿入します。セットは重複を許さないため、同

問題概要x軸上の2本の線分を表す2つの区間 (l1, r1) と (l2, r2) が与えられます。ここで l1 < r1、l2 < r2 が成り立ちます。これらの線分は互いに交差したり、部分的に重なったり、完全に一致したりする可能性があります。この問題では、a が区間 (l1, r1) 内に含まれ、b が区間 (l2, r2) 内に含まれ、かつ a と b が異なる値となるような2つの数 a、b を見つけることが求められます。たとえば、l1 = 2、r1 = 6、l2 = 3、r2 = 4 が入力された場合、a = 2、b = 3 を出力できます。もちろん、条件を満たす他の組み合

3つの整数 N、M、K が与えられます。ここに、一列に並んだ N 個のブロックがあります。次の2つのルールに従ってブロックを塗る方法を考えます。2つの塗り方が「異なる」とみなされるのは、対応するブロックの色が1つでも異なる場合です。 各ブロックには、M 色の中から1色を選んで塗ります(すべての色を使い切る必要はありません)。 同じ色で塗られた隣接ブロックの組は、最大で K 組まで許容されます。 答えが非常に大きくなる可能性があるため、結果は 998244353 で割った余りを返します。 たとえば、入力が N = 3、M = 2、K = 1 の場合、出力は 6 になります。「112」「12

問題概要4つの要素を持つ配列 A があるとします。これは4つのキャンディーの袋を表しており、i 番目の袋には A[i] 個のキャンディーが入っています。これらの袋をすべて2人の友人のどちらかに配りたいと考えています。各袋をどちらか一方の友人に割り振るとき、2人が受け取るキャンディーの合計数を同じにできるかどうかを判定するのが課題です。例として、入力が A = [1, 7, 11, 5] の場合を考えてみましょう。この場合、出力は True になります。1番目と3番目の袋（1＋11＝12個）を1人目の友人に、2番目と4番目の袋（7＋5＝12個）を2人目の友人に渡すことで、両者とも合計12個のキャ

要素数Nの2つの配列AとBがあるとします。ここで、N台のコンピューターとN個のソケットが存在すると考えます。i番目のコンピューターの座標はA[i]、i番目のソケットの座標はB[i]であり、これら2N個の座標はすべて互いに異なるものとします。目的は、ケーブルを使って各コンピューターを1つのソケットに接続することです。ただし、1つのソケットに接続できるコンピューターは最大1台までという制約があります。このとき、ケーブルの総延長が最小となる接続方法が何通り存在するかを数える必要があります。答えが非常に大きくなる場合は、10^9 + 7で割った余りを返してください。例として、入力がA = [0, 10

この記事では、2つの整数 K と X が与えられたとき、「Amal さんが持っている 500 ルピー紙幣 K 枚の合計金額が、X ルピー以上になるかどうか」を判定する C++ プログラムを紹介します。例えば、K = 2、X = 900 が入力された場合を考えてみましょう。500 ルピー紙幣 2 枚の合計は 2 × 500 = 1000 ルピーとなり、900 ルピー以上であるため、出力は True(真) になります。解法のアプローチこの問題は非常にシンプルで、次の手順で解くことができます。= X ならば:    true を返すそうでなければ: 

この記事では、2つの整数 N と K が与えられたとき、N個のクラッカーをK人のユーザーに分配する問題を解説します。目標は、あるユーザーが受け取るクラッカーの最大数と、別のユーザーが受け取る最小数の差として考えられる最小値を求めることです。問題の例たとえば、入力が N = 7、K = 3 の場合を考えてみましょう。このとき出力は 1 になります。なぜなら、各ユーザーがそれぞれ 2個・2個・3個 のクラッカーを受け取るとき、最大数（3個）と最小数（2個）の差は 1 になるからです。解法のアプローチこの問題は非常にシンプルな論理で解くことができます。N が K で割り切れる場合：全員が同じ個数（N

小文字の英字のみで構成された文字列 S が与えられます。ここで、S にちょうど 1 つだけ文字「a」を挿入することを考えます。挿入後の文字列が回文（前から読んでも後ろから読んでも同じ並びになる文字列）ではなくなるようにできた場合は、その結果の文字列を返します。どこに挿入しても回文になってしまう場合は「Impossible」を返します。例えば、入力が S = bpapb の場合、末尾に「a」を追加した bpapba は回文ではないため、これが出力となります。解法の考え方この問題は、非常にシンプルなアプローチで解くことができます。「a」を末尾に追加した文字列と先頭に追加した文字列のそれぞれについて

問題の概要N 文字からなる文字列 S を考えます。S には「A」「B」「C」の 3 種類の文字のみが含まれており、これとは別に整数 K が与えられます。このとき、文字列 S の K 番目の文字を小文字に変換して出力するのが課題です。例えば、入力が K = 2、S = AABACC の場合、2 番目の文字「A」が小文字の「a」に変わるため、出力は AaBACC となります。解法のアプローチこの問題は、以下の手順で解決できます。S[K - 1] = S[K - 1] + 32 return Sポイントは、大文字と小文字の ASCII コードの差がちょうど 32 であるという点です。そのため、対象の

ある数値 R が与えられ、これは円形の池の半径を表しているとします。このとき、池の円周（外周）の長さを求める必要があります。たとえば、入力が R = 73 の場合、出力は 458.67252742410977361942 となります。解き方の手順この問題を解くには、以下の手順に従います。円周は「直径 × 円周率」で表されるため、半径 r を使うと 2 × r × π で計算できます。ここでは、逆余弦関数 acos(-1) の戻り値が円周率 π に等しいという性質を利用します。res := r * 2 * cos-inverse (-1) return resC++での実装例理解を深めるために、