C++

整数 n が与えられたとき、n を正整数の非増加列(前の要素が後の要素以上となる並び)に分解することを考えます。このとき、各要素の合計は必ず n と一致します。分割の「重み」とは、その分割の中で最初の要素と同じ値を持つ要素の個数のことです。例えば、分割 [1, 1, 1, 1, 1] の重みは 5、分割 [5, 5, 3, 3, 3] の重みは 2、そして分割 [9] の重みは 1 となります。この記事では、n のあらゆる分割において現れうる「異なる重み」の種類数を求める方法を解説します。例として、入力が n = 7 の場合を見てみましょう。このときの出力は 4 になります。これは、次の 4

問題概要 n文字の文字列Sがあるとします。Sは、英大文字・小文字で構成された単語が半角スペース1つずつで区切られたテキストです。 ここで、単語のボリュームとは、その単語に含まれる大文字の数を指し、テキストのボリュームとは、テキスト内のすべての単語の中で最も大きいボリュームのことです。この記事では、与えられたテキストのボリュームを求めるC++プログラムを紹介します。 解法のアプローチ この問題は、文字列を先頭から1文字ずつ走査することで効率的に解けます。基本的な考え方は以下の通りです。 現在見ている単語内の大文字の数をカウントする変数を用意する スペースに到達した時点で、それまでのカウント

問題概要「X」と「.」から構成される 3 × 3 の行列を考えます。このパターンが中心対称(点対称)であるかどうかを判定します。中心対称とは、図形の中心点を基準に 180 度回転させても元の形と完全に重なるような対称性のことです。たとえば、次のような入力が与えられた場合を考えてみましょう。XX.....XXこの場合、出力は True(真)になります。各マスを中心に対して反転させると、すべての要素が一致するためです。解法のステップこの問題を解くには、以下の条件でチェックを行います。M[0, 0] == M[2, 2] かつ M[0, 1] == M[2, 1] かつ M[0, 2] == M[2

要素数 n の配列 A と整数 d が与えられたとします。ドリームランド軍の規定では、偵察部隊はちょうど 2 名の兵士で構成しなければならず、さらに 2 人の身長差は d センチメートル以内でなければなりません。n 人の兵士の身長は配列 A に格納されており、同じ身長の兵士が複数いる場合もあります。この記事では、この n 人の兵士から偵察部隊を結成する方法が何通りあるかを求める問題を解説します。 たとえば、入力が A = [10, 20, 50, 60, 65]、d = 10 の場合、出力は 6 になります。これは (10, 20)、(20, 10)、(50, 60)、(60, 50)、(60

数値 p と、n 個の要素を持つ配列 X があるとします。ここで、バケット（格納領域）を p 個持つハッシュテーブルを考えます。各バケットには 0 から p-1 までの番号が振られており、配列 X の n 個の数値を順番に挿入していきます。X[i] の挿入先はハッシュ関数 h(X[i]) によって決まります。ここでは h(k) = k mod p と定義されています。なお、1 つのバケットに格納できる要素は最大 1 つです。すでに要素が入っているバケットに新しい数値を挿入しようとした場合、「衝突（コリジョン）」が発生したとみなします。求められるのは、衝突が発生した際の挿入元のインデックスを返す

n個の要素を持つ配列Aと、数値sが与えられます。テーブルの上には、空のコップが1つと、水の入ったコップがn個置かれています。このゲームには複数のプレイヤーが参加し、各ターンでプレイヤーは水の入ったコップを1つ選び、その水をすべて空のコップに注ぎます。コップがあふれてしまった場合、そのプレイヤーは負けとなります。ここで、すべてのプレイヤーが勝者になれるかどうか(コップがあふれないかどうか)を判定する必要があります。なお、コップがすでに満杯になっている場合、次のプレイヤーは自分のターンを行いません。sは空のコップの容量を、A[i]はi番目のコップに入っている水の量を表します。例えば、入力がA =

「良い行列」とは何か n × n の行列を考えてみましょう。すべての要素のうち 1 以外の数値が、必ず「同じ行に含まれるある数」と「同じ列に含まれるある数」の和として表せるとき、その行列を良い行列（Good Matrix）と呼びます。本記事では、与えられた行列が良い行列かどうかを判定する C++ プログラムを解説します。 たとえば、次のような行列が入力されたとします。 112231641 このときの出力は True になります。左下の 6 は、すぐ上の 2 と右隣の 4 の和（2 + 4 = 6）で表せるためです。それ以外の 1 以外の数値も、すべて同じ条件を満たしています。 アルゴリズムの考

問題の概要2つの整数 n と h、さらに m 個の三つ組からなる配列 T（T[i] = (li, ri, xi)）が与えられます。道路沿いには家を建てられる場所が n 箇所あり、それぞれ 1 から n までの番号が付けられています。各場所に建てる家の高さは 0 から h の範囲で自由に選べます。ある場所に高さ k の家を建てると、k² の利益が得られます。一方、区域ごとの高さ制限が m 個設けられています。i 番目の制限は「地点 li から ri までの区間にある家のうち、最も高いものの高さは xi 以下でなければならない」というものです。すべての制限を満たしながら利益を最大化すると

問題の概要 -1 から 1 の範囲の値を持つ n 個の要素からなる配列 A と、Q[i] = (li, ri) の形式で表される m 個のクエリ Q が与えられます。各クエリに対しては、配列の要素を並べ替えることで区間 Q[li] ～ Q[ri] の合計が 0 になるようにできる場合は 1、できない場合は 0 を答えとします。すべてのクエリに対する回答を求めましょう。 たとえば、入力が A = [-1, 1, 1, 1, -1]、Q = [[1, 1], [2, 3], [3, 5], [2, 5], [1, 5]] のとき、出力は [0, 1, 0, 1, 0] となります。 解法の考え方

2つの整数 m(月)と d(その月の1日の曜日)が与えられたとします。ここでは、曜日が列として並び、日付が各行に埋められていくカレンダーを考えます。このとき、月 m と1日の曜日 d が分かっていれば、カレンダー全体を表示するのに何列必要かを求めることができます(うるう年は考慮しないものとします)。例えば、入力が m = 11、d = 6 の場合、出力は 5 になります。11月1日が土曜日にあたり、5列あれば1か月分の日付をすべて収められるためです。解き方の手順この問題は、次の手順で解くことができます。大きさ13の配列 a を定義 := { 0, 31, 28, 31, 30, 31, 30,

問題概要すべての要素が異なる n 個の整数からなる配列 A があるとします。あるコンテストのオンサイト決勝に進んだファイナリストがおり、その予選順位が配列 A に格納されています。決勝ラウンドへの現地参加の招待を辞退した出場者の最小人数を求めるのがこの問題の目的です。オンサイトで参加できるのは全部で 25 人であり、そのうち何人かは招待を受け入れ、何人かは辞退している状況を想定します。たとえば、入力が A = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28]

n個の要素を持つ配列Aと、2つの整数kおよびxが与えられているとします。i番目のタスクを完了するには通常A[i]の時間がかかります。配列Aは非降順(昇順)にソートされているものとします。ここで、Amalは最大k個までのタスクを選び、それらを本来のA[i]の代わりにx単位の時間で実行できるものとします(ただし、xは配列内の最小値よりも小さい値です)。このとき、Amalがすべてのタスクを完了するために必要な最小時間を求めるのが目的です。なお、複数のタスクを同時に実行することはできません。例として、入力が A = [3, 6, 7, 10]、k = 2、x = 2 の場合を考えてみましょう。この場合

問題の概要ある数 n が与えられ、n 人の子供が円形に立っているとします。子供たちには時計回りに 1 から n までの番号が付けられており、最初は 1 番の子供がボールを持っています。まず 1 番の子供が、時計回りに隣にいる子供(2 番)へボールを投げます。次に 2 番の子供が、その隣の子供(4 番)へ投げ、続いて 4 番の子供が 7 番の子供へと投げます。このように、投げるたびにボールが進む距離が 1 つずつ増えていきます。ボールが投げられる際には、円の一周をまたいで先頭に戻ることもあります。ゲームの途中でボールを受け取らない子供もいるため、各投擲の後にボールを受け取る子供の番号をすべて求め

問題概要 サイズ n の2つの配列 P と T、および定数 c が与えられます。Amal と Bimal の2人が数学コンテストに参加することになりました。コンテストには n 問の問題が出題され、i 番目の問題の初期スコアは P[i]、それを解くのにかかる時間は T[i] です。P と T はどちらも昇順にソートされています。c は減点を決める定数で、ある問題をコンテスト開始 x 分後に提出した場合、その問題から得られるスコアは max(0, P[i] - c * x) となります。 Amal は問題を 1, 2, ..., n の順番で解き、Bimal は n, n-1, ..., 1 の

3つの整数 k、l、m と、n 個の要素を持つ配列 A が与えられているとします。ある強盗が銀行強盗に失敗しましたが、銀行内のすべての金庫を開けることには成功していました。そこへ別の人物が現れ、この失敗した強盗に便乗して、金庫からお金を盗み出そうと考えます。 金庫は一列に並んでおり、すべての金庫には合計で n 枚の紙幣が残っています。i 番目の紙幣は A[i] 番目の金庫の中にあります。現在、銀行の従業員は k 番目の金庫におり、警備員は2名配置されています。1人目の警備員は l（l < k）番目の金庫、すなわち従業員の左側を警備しており、もう1人の警備員は m（m > k）番目

n×n の正方形ボードがあり、Amal（アマル）と Bimal（ビマル）がゲームを行っています。二人はゲーム中、独自のルールに従ってボードの各マスに数字を書き込んでいきます。現在見えているのはゲーム終了後の盤面です。どちらが勝者かを判定するには、「勝利マス」の数を数える必要があります。あるマスが勝利マスであるかは、次のように判定します。そのマスと同じ列にあるすべての数字の合計を求めます。同じ行にあるすべての数字の合計を別途求めます。列の合計が行の合計より厳密に大きい場合、そのマスは勝利マスとなります。たとえば、次のような入力が与えられたとします。5784953216649573このときの出力は

問題概要2つの整数 n と k が与えられます。あるコンテストには n 人の学生が参加しており、そのうち何人かは記念品を、何人かは賞状を受け取り、残りの人は何も受け取りません。何かしらを受け取った人を「勝者」と呼びます。記念品と賞状の数を決める際には、以下のルールが定められています。賞状の数は、記念品の数のちょうど k 倍でなければならない勝者の総数は n/2 を超えてはならない勝者が一人も存在しない場合もあり得るこれらのルールに基づき、可能な限り多い勝者の数を求めます。そのうえで、記念品を受け取る学生の人数、賞状を受け取る学生の人数、そして勝者とならない学生の人数をそれぞれ出力します。例えば

C++のswitch文の使い方 条件分岐は、あらゆるプログラミング言語に共通する基本的な機能です。条件分岐を使うことで、プログラムの流れを制御し、特定のコードブロックを実行するタイミングを指定できます。 C++で主に使われる条件分岐には、if文とif … else文があります。さらにC++ではswitch文も利用できます。switch文は式を複数の候補（ケース）と照らし合わせて評価し、一致したケースに対応するコードブロックを実行します。その動作は、多数のif … else文を連ねたif文に似ています。 この記事では、サンプルコードとともにC++におけるswitch文の使い方を解説します。

C++のenum（列挙型）とは？基本の使い方を徹底解説 列挙型（enumerated type）は、あらかじめ定義された値の範囲の中から、いずれか一つの値だけを持つことができるユーザー定義型です。 プログラミングでは、変数が特定の値の集合の中の一つの値しか格納できないようにしたい場合によく使われます。たとえば、変数に「曜日」だけを格納したい場合などに、列挙型が役立ちます。 この記事では、C++における列挙型の基礎知識、定義方法、コードでの実際の使い方を、サンプルコードとともにわかりやすく解説します。読み終える頃には、C++のenumを使いこなせるようになっているはずです。 C++におけ

if...elseはC++における条件分岐（条件文）です。C++のif文は、条件が満たされた場合にコードブロックを実行します。if...else文も同様に機能しますが、条件が満たされなかった場合に実行される別のコードブロックを持つ点が異なります。また、if文やif...else文はネスト（入れ子）にすることも可能です。 条件分岐はなぜ重要なのか 条件分岐は、あらゆるプログラミング言語において不可欠な要素です。条件分岐を使うことで、開発者はプログラム内で特定の条件が満たされているかどうかに応じて、コードを実行するかどうかを制御できます。 C++では、if文やif...else文が条件式の真偽を