C++

n × 4 のサイズを持つ 2 次元配列（成績表）を考えてみましょう。n 人の学生がおり、各学生には 0 から n-1 までの ID が割り当てられています。すべての学生は、英語・地理・数学・歴史という 4 科目の得点を持っています。 この成績表では、学生は合計点の降順に並べられます。また、合計点が同じ学生が複数存在する場合は、ID の昇順に並べ替えられます。今回の目的は、この並び順の中で「ID が 0 の学生」が何位になるかを求めることです。 入力例 10098100100100100100100909990100100986099 この場合の出力は 2 となります。 実際に合計点を計算して

問題概要3つの整数 a、b、c が与えられます。それぞれ「レモンが a 個」「リンゴが b 個」「洋梨が c 個」あることを表します。コンポートを作るには、果物の比率を 1 : 2 : 4（レモン：リンゴ：洋梨）にする必要があります。また、果物を切って使うことはできません。この条件のもとで、コンポートを作るために使える果物の合計数の最大値を求めます。1つも作れない場合は 0 を返します。入力例例えば、a = 4、b = 7、c = 13 の場合、出力は 21 になります。これは、レモン3個、リンゴ6個、洋梨12個を使用でき、3 + 6 + 12 = 21 となるためです。解法のアプローチこの問

n個の小文字の英字からなる文字列Sが与えられたとします。このとき、Sの文字を並べ替えて、結果の文字列の中に「trygub」が部分列(subsequence)として含まれないようにする必要があります。たとえば、入力が S = pintontrygubabc の場合、出力は abbcginnoprttuy となります。解法のアプローチこの問題は驚くほどシンプルで、以下の手順だけで解決できます。文字列Sを昇順(アルファベット順)にソートするソートした結果をそのまま返すなぜソートするだけで良いのか?文字列を昇順にソートすると、すべての「b」が先頭側に集まり、「t」「r」「y」「g」「u」はそれより後ろ

問題概要3つの整数 y、b、r が与えられます。装飾用の飾りとして、黄色い飾りが y 個、青い飾りが b 個、赤い飾りが r 個あります。使用する青い飾りの数が黄色い飾りの数よりちょうど1個多く、赤い飾りの数が青い飾りの数よりちょうど1個多い場合、その装飾は「美しい」とみなされます。できるだけ多くの飾りを使いたい一方で、装飾も美しく仕上げたいと考えています。このとき、美しい装飾に使用できる飾りの最大数を求めるのが本問題の目的です。たとえば、入力が y = 8、b = 13、r = 9 の場合、出力は 24 になります。これは黄色7個・青8個・赤9個を使用すると 7 + 8 + 9 = 24 と

問題の概要 小文字の英字からなる長さ n の文字列 S が与えられたとします。このとき、次の条件をすべて満たす文字列を「多様な文字列（diverse string）」と呼びます。 アルファベットが連続して並んでいること それぞれの文字がちょうど1回だけ出現すること なお、「a」と「z」は隣接しているものとはみなさない この記事では、与えられた文字列 S が多様な文字列であるかどうかを C++ で判定する方法を解説します。 例えば、入力が S = fced の場合、文字を並べ替えると c, d, e, f となり、アルファベットが連続しているため、出力は True（1）になります。 解き方

ある整数 n が与えられたとします。ここで、a + b + c = n を満たし、かつ3つの数 a、b、c のいずれも3の倍数にならないような組み合わせを見つけることを考えます。例えば、入力が n = 233 の場合、出力は「1, 2, 230」のようになります。実際に確認すると、1 + 2 + 230 = 233 であり、どの数も3の倍数ではありません。解法のアプローチこの問題は、以下の手順に従って解くことができます。if ((n - 2) mod 3 == 0) then: return 1, 2, n - 3 otherwise: return 1, 1, n - 2なぜ

問題の概要 整数 x が与えられているとします。手元にあるのは、各面に 2 から 7 までの数字が書かれた 6 面体サイコロです。目標は、サイコロを振って出た目の合計をちょうど x にすることです。 ここでポイントになるのは、振る回数は自由という点です。合計がちょうど x になるような投擲回数が 1 つ分かれば十分で、その結果が出る確率が 0 でない限り、幸運にも実際にその通りの出目を得られるものとします。つまり、条件を満たす任意の回数を 1 つ答えればよいのです。 考え方 この問題を解くカギは、サイコロの最小の出目が 2 であることに着目することです。 x が偶数の場合： 毎回 2 を出

問題概要 2つの整数 l と r が与えられます。このとき、次の条件をすべて満たすペア (x, y) を見つけることが課題です。 l <= x, y <= r:x と y はどちらも範囲 [l, r] 内に収まること x != y:x と y は互いに異なる数であること x が y を割り切ること(x が y の約数、つまり y が x の倍数) 条件を満たす答えが複数存在する場合は、その中からどれを返しても構いません。 たとえば、入力が l = 3、r = 14 の場合、出力は (3, 6) となります。もちろん (3, 9) も有効な答えのひとつです。 解法のアプローチ

S と F の2種類の文字で構成された文字列 S があるとします。S[i] が S であれば i 日目にはシアトルにいて、F であればフロリダにいることを表します。このとき、シアトルからフロリダへ飛行した回数が、フロリダからシアトルへ飛行した回数よりも多いかどうかを判定する必要があります。 例として、入力が S = "SSFFSFFSFF" の場合、出力は True になります。 判定ロジックのポイント この問題は一見、移動の履歴をすべて数える必要がありそうに思えますが、実は文字列の先頭と末尾の文字だけを見れば判定できます。都市間の移動は必ずフライトを伴うため、旅の開始時

問題の概要数値 n が与えられます。あるゲームでは、各キャラクターのヒットポイント（HP）は以下の4つのカテゴリのいずれかに分類されます。カテゴリA：HPが (4n + 1) の形式の場合カテゴリB：HPが (4n + 3) の形式の場合カテゴリC：HPが (4n + 2) の形式の場合カテゴリD：HPが 4n の形式の場合これら4つのカテゴリは A > B > C > D の順に優先度が決まっており、カテゴリAが最も高く、カテゴリDが最も低くなります。ゲーム中、プレイヤーはキャラクターのHPを増やすことが可能です。ここで、Amalは自分のHPを最大2まで（つまり0、1、また

問題概要 n個の要素からなる配列Aがあり、ボード上にn個の数値が書かれているとします。AmalとBimalが交互にターン制のゲームを行います。各ターンで、プレイヤーは数値を1つ選んでボードから取り除きます。Amalが先手です。Amalは最後にボードへ残る数をできるだけ小さくしたいと考え、一方のBimalはそれをできるだけ大きくしたいと考えています。このとき、最終的にボードに残る数を求めましょう。 例えば、入力が A = [2, 1, 3] の場合、出力は 2 になります。これは、Amalが先に 3 を取り除き、次にBimalが 1 を取り除くため、最後に残る数が 2 になるからです。 解法の

n枚のカード（番号は1〜n）を使った面白いカードゲームを考えてみましょう。プレイヤーはAmalとBimalの2人で、それぞれk1枚・k2枚のカードを持っています。ゲームは次のように進みます。各ターンで、両者は手持ちの中から好きなカードを1枚選んでテーブルに出します。このとき相手にはどのカードを出したか分かりません。その後、2枚のカードが同時に公開され、より大きい数字のカードを出したプレイヤーが両方のカードを手に入れます。ここで重要なのは同じカードは何度でも使えるというルールです。配列AはAmalの持つカード、配列BはBimalの持つカードを表します。手持ちのカードが1枚もなくなったプレイヤー

問題の概要小文字のみで構成された長さnの文字列Sが与えられます。このとき、次の条件をすべて満たす2つの空でない部分文字列PとQを見つける必要があります。PとQはどちらもSの部分列である各インデックスiについて、S[i]はPとQのどちらか一方にのみ属するPはできるだけ辞書順で最小になる例えば、入力が S = thelightsaber の場合、出力は a, thelightsber となります。文字列中で最も辞書順に小さい文字「a」をPとし、残りの文字をすべてQとすることで、条件を満たす分割が実現できるからです。解法のアプローチこの問題はシンプルな貪欲法で解くことができます。Pを辞書順最小にする

2つの整数 n と k が与えられたとします。パーティーには n 人の友人を招待する予定で、Amalさんは折り紙を使って招待状を作りたいと考えています。招待状1枚につき、赤い紙が2枚、緑の紙が5枚、青い紙が8枚必要です。各色のノートは無限にありますが、1冊のノートには1色のみで k 枚の紙が綴じられています。このとき、n 人全員を招待するためにAmalが購入すべきノートの最小冊数を求めます。例えば、入力が n = 3、k = 5 の場合、出力は 10 になります。これは、赤のノートが2冊、緑のノートが3冊、青のノートが5冊必要だからです。解法のアプローチこの問題を解くには、次の手順に従います。

問題の概要 2つの座標 (x1, y1) と (x2, y2) が与えられます。ウサギは食べ物の入った箱を、長さ1単位のロープで引っ張って移動させます。 ウサギは箱を引っ張るとき、箱を自分の現在位置まで引き寄せ、その後同じ方向へ1単位だけ退避します。また、箱を引っ張らない状態であれば上下左右へ自由に1単位ずつ移動でき、このとき箱との距離が厳密に1単位である必要はありません。ただし、再び引っ張るためには箱の隣接するマスまで移動しなければなりません。ウサギは任意のマスからスタートでき、どの方向に1単位移動するにも1秒かかります。箱を出発位置から目的地まで移動させるのに必要な最小時間を求めましょう。

問題の概要整数 n が与えられ、サイズ n の配列 A を求めることを考えます。ここには n 個のテーブルがあり、それぞれのテーブルには椅子が4脚ずつ用意されています。椅子には 1 から 4n までの番号が振られています。番号 a と b（a ≠ b）の椅子に座った2人の子どもは、以下のいずれかの条件を満たすとき、騒ぎ出してしまう（悪さをしてしまう）ことが分かっています。gcd(a, b) = 1（a と b が互いに素）である場合a が b を割り切る、または b が a を割り切る場合私たちの目標は、悪さをするペアが一つも発生しないように子どもたちを着席させることです。言い換えると、条件を

2つの整数 a と b があるとします。Amalはいつもテレビの音量を「b」に設定していますが、ある日Bimalが誤って「a」に変更してしまいました。 リモコンには -5、-2、-1、1、2、5 の6つのボタンがあり、これらを使って音量を1、2、または5だけ増減できます。音量は非常に大きな値になり得ますが、負の値にはなりません。ここで、Amalが音量を再び「b」に戻すために必要な最小のボタン押下回数を求めるのがこの問題です。 問題の例 例えば、入力が a = 5、b = 14 の場合、出力は 3 になります。これは、「+5」を1回押して10にし、続いて「+2」を2回押して14に到達できるためで

問題の概要 要素数n（nは奇数）の配列Aがあるとします。Aには、最初のn個の自然数（1〜n）の順列が格納されています。 ここで、0からn-2の範囲の引数iを1つ受け取る関数f(i)を考えます。この関数は、A[i] > A[i+1]である場合に、A[i]とA[i+1]の値を入れ替える操作を行います。 私たちの目的は、配列Aが初めて完全にソートされた状態になるまでに必要な反復回数を求めることです。 入出力例 例えば、入力が A = [4, 5, 7, 1, 3, 2, 6] の場合、出力は 5 になります。これは、各反復後に配列が次のように変化していくためです。 [4, 5, 1, 7,

0〜9の数字からなる長さ n の文字列 S があるとします。部分文字列が表す数値が偶数であるとき、その部分文字列を「偶数の部分文字列」と呼びます。ここでは、文字列 S に含まれる偶数の部分文字列の総数を求める方法を解説します。たとえば、入力が S = 1234 の場合、出力は 6 になります。偶数となる部分文字列は「2」「4」「12」「34」「234」「1234」の6つ存在するためです。解法のポイント数値の偶奇は最後の桁(一の位)だけで決まります。つまり、位置 i にある桁が偶数であれば、その位置で終わるすべての部分文字列は必ず偶数になります。位置 i で終わる部分文字列は開始位置の選び方によ

3つの整数 a、b、c が与えられます。ある歌手は、1分の曲を a 曲、2分の曲を b 曲、3分の曲を c 曲持っています。歌手はすべての曲を2つのコンサートに振り分けたいと考えていますが、各曲は必ずどちらか一方のコンサートにのみ含まれる必要があります。歌手の目標は、2つのコンサートの演奏時間(それぞれのコンサートに含まれる全曲の時間の合計)の絶対差をできるだけ小さくすることです。ここで、コンサート間の演奏時間差として考えられる最小値を求めます。 具体例 入力が a = 2、b = 1、c = 3 の場合を考えてみましょう。このときの出力は 1 になります。 1つ目のコンサートに「1分の曲2本