C++

 Computer >> コンピューター >  >> プログラミング >> C++
  1. C++で第2党が選挙に勝利するための最小投票数kを求める方法

    問題概要n個の要素を持つ配列Aがあるとします。ある学校にはn人の生徒がおり、それぞれがちょうどk票を持っていて、すべての票を使い切らなければなりません。政党は2つあります。A[i]は、i番目の生徒が第1党にA[i]票を投じたことを表し、その結果、第2党には残りのk − A[i]票が入ります。第2党が選挙に勝てるようにkを設定したい場合、kとして取り得る最小値を求めるのがこの問題です。例えば、入力が A = [2, 2, 3, 2, 2] の場合、出力は5になります。第1党は 2 + 2 + 3 + 2 + 2 = 11 票を獲得しますが、k = 5 と設定すれば第2党は 3 + 3 + 2 +

  2. C++で石積みの数を検証する方法：翌日の状態が有効かどうかを判定する

    問題の概要 同じサイズを持つ2つの配列 X と Y があるとします。1日目の時点で、i番目の場所には X[i] 個の石が積まれた山があります。そして2日目には、同じ場所に Y[i] 個の石が積まれています。 1日目に多くのメンバーが訪れ、彼らは次のいずれかの行動を取ったと考えられます。 何もしない いくつかの山に石を追加する ある山から別の山へ石を移し替える このとき、Y が X から導ける正当な状態かどうかを判定する必要があります。 たとえば、入力が X = [1, 2, 3, 4, 5]、Y = [2, 1, 4, 3, 5] の場合、出力は True になります。なぜなら、2番目の山

  3. 【C++】nより大きくkで割り切れる最小の整数を見つける方法

    2つの整数 n と k が与えられたとします。このとき、n より大きく、かつ k で割り切れる最小の整数 x を求める必要があります。 例えば、入力が n = 5、k = 3 の場合、出力は 6 となります。6 は 5 より大きい数の中で、3 で割り切れる最小の整数だからです。 解法のアプローチ この問題は、ループで候補を順番に調べることなく、次のシンプルな式を使うことで O(1) の計算量で解くことができます。 return n + k - (n % k) なぜこの式が成り立つのか n % k(n を k で割った余り)を引いてから k を足し戻すことで、n を超える最初の k の倍数が得ら

  4. C++で黒く塗られた正方形の中心を見つける方法

    n × m のサイズを持つ行列を考えます。各セルは白を表す「W」または黒を表す「B」のいずれかです。この表の中には、奇数の辺の長さを持つ正方形が黒く塗られており、その正方形の中心を見つけることが課題となります。 問題の例 例えば、以下のような入力が与えられたとします。 WWBBBWWWBBBWWWBBBWWWWWWWWWWWWW この場合、出力は (3, 1) となります。これは、黒い正方形の中心セルが「1行目・3列目」に位置しているためで、結果は（列, 行）の順で出力されます。 解法のアプローチ この問題は、黒いセル（B）の座標の平均を計算することで解けます。黒く塗られた正方形は上下左右に対

  5. C++で質問文の最後の文字が母音かどうかを判定して答えを導くコード

    問題の概要文字列 S が与えられ、Amal と Bimal があるゲームを行います。ゲームのルールは次のとおりです。先にプレイする Amal は探偵役となり、「事件」を調査して原因を突き止める必要があります。彼は答えが「Yes」か「No」のどちらかになる質問を自由に行うことができます。そして、質問文の最後の文字が母音であれば「Yes」、そうでなければ「No」と回答します。ここで扱う母音は A、E、I、O、U、Y の6種類です。文字列 S を質問として受け取り、その答えを求めるのがこの問題の目的です。例えば、入力が S = Is it in university? の場合、出力は「Yes」になり

  6. C++でバイナリ文字列から最小の正しい文字列を求める方法を解説

    n ビットの2進数文字列 S があるとします。ただし、余分な先頭のゼロは含まれていないものとします。この文字列 S に対して、次の2種類の操作を実行することができます。隣接する任意の2ビットを入れ替えるすべての「11」を「1」に置き換えるval(S) を S の10進数表現とします。そして、正しい文字列 A が別の正しい文字列 B よりも小さいとは、val(A) < val(B) が成り立つときであると定義します。この条件下で、最小の正しい文字列を求めるのが本問題の目的です。具体例たとえば、入力が S = 1001 の場合を考えてみましょう。このときの出力は「100」となります。次のよう

  7. C++で与えられた行列が有効な縞模様の旗かどうかを判定するコード

    ここでは、サイズ n × m の行列を考えます。各セルには 0 から 9 までのいずれかの値が格納され、その値がセルの「色」を表します。この行列は縞模様の旗として成立していなければならず、次の 2 つの条件を満たす必要があります。 旗の各行（横方向の並び）は、すべて同じ色のマスで構成されていること 上下に隣接する行同士の色は互いに異なること 与えられた行列がこれらの条件を満たす「有効な旗」であるかどうかを判定するのが本記事の目的です。 入力例 000111333 この行列の場合、1 行目はすべて 0、2 行目はすべて 1、3 行目はすべて 3 となっており、隣接する行の色もすべて異なるた

  8. 環状線の駅間の最短距離を求めるC++コード

    2つの整数 s と t、さらに n 個の要素を持つ配列 D が与えられているとします。ドリームランド地下鉄の環状線には n 個の異なる駅があります。隣接する駅同士の距離はすべて分かっており、D[i] は駅 i と駅 i+1 の間の距離、D[n-1] は駅 (n-1) と駅 0 の間の距離を表します。このとき、駅 s から駅 t までの最短距離を求める必要があります。 例えば、入力が s = 1、t = 3、D = [2, 3, 4, 9] の場合、出力は 5 になります。 解法の手順 この問題は、以下の手順に従って解くことができます。 n := D のサイズ (n + 1) サイズの配列 a

  9. ロボットの移動文字列を圧縮して最短化するC++コードの解説

    長さnの文字列Sを考えます。各文字は「R」または「U」のいずれかです。2次元平面上では、ロボットは右または上に移動でき、「R」なら右へ1マス、「U」なら上へ1マス進みます。しかし、文字列が大きすぎる場合には、これをより短く圧縮したいと考えます。隣接する「RU」や「UR」のようなペアは、斜め移動を表す1文字「D」に置き換えることができます。このとき、最終的に圧縮された文字列の長さを求めるのが本記事の目的です。例えば、入力が S = RUURU の場合を考えてみましょう。先頭の「RU」は「D」に、続く「UR」も「D」に置き換えられ、最後の「U」はそのまま残るため、結果の文字列は「DUD」となります

  10. 文字列Sを部分列として含む回文文字列を求めるC++プログラム

    長さnの文字列Sが与えられたとします。このとき、Tが回文であり、かつSがTの部分列(サブシーケンス)となるような文字列Tを見つける必要があります。例えば、入力が S = "ab" の場合、出力は "abba" となります(他にも "aabaa" など、複数の正解が存在します)。解法のアプローチこの問題は、非常にシンプルな発想で解くことができます。以下の手順に従います。結果の文字列resをSで初期化します。文字列Sを反転します。resに反転したSを連結します。resを返します。つまり、元の文字列とその逆順の文字列を連結するだけで、必ず回

  11. C++で配列内の局所的な極値（極大値・極小値）を数える方法

    要素数 n の配列 A が与えられたとします。配列の要素 A[i] が、両隣の要素（A[i-1] と A[i+1]）のどちらよりも厳密に小さい場合、その要素は「局所的な極小値（local minimum）」と呼ばれます。逆に、両隣のどちらよりも厳密に大きい場合は「局所的な極大値（local maximum）」となります。なお、配列の先頭要素 A[0] と末尾要素 A[n-1] は隣接要素が1つしか存在しないため、極大値にも極小値にもなりません。この記事では、与えられた配列に含まれる局所的な極値（極大値と極小値の合計）の個数を求める方法を解説します。具体例例として、入力が A = [1, 5,

  12. 本を読み終えるまでの日数を求めるC++プログラムの解説

    n個の要素を持つ配列Aと整数tが与えられているとします。i日目にはAmalは仕事にA[i]秒を費やし、その空いた時間に本を読みます。本全体を読み終えるのに必要な時間はt秒です。ここで、本を最後まで読み終えるまでに何日かかるかを求めるのがこの問題です。 たとえば、入力がA = [86400, 86398]、t = 2である場合、出力は2になります。1日は86400秒ですが、初日は仕事で丸々埋まってしまい、読書できる時間がありません。2日目には2秒の自由時間が生まれ、そこで本を読み切ることができるためです。 解法のアプローチ この問題は、各日の自由時間（86400秒から仕事時間を引いた秒数）を順番

  13. C++で3人チームの最大結成数をカウントする方法【アルゴリズムと実装例】

    問題概要n 個の要素を持つ配列 A があるとします。これは n 個の学生グループを表しています。各グループは次のいずれかのタイプです。誰とでもチームを組むことができる 1 人の学生必ず同じチームでコードを書きたい 2 人の学生しかし、メンターはちょうど 3 人ずつのチームを結成することにしました。ここで求めたいのは、メンターが結成できる 3 人チームの最大数です。なお、2 人グループについては「2 人そろって参加する」か「2 人そろって不参加」のどちらかしか選べず、参加する場合は必ず同じチームに所属しなければなりません。たとえば、入力が A = [2, 2, 2, 1, 1, 1, 1] の場

  14. カエルが家にたどり着くための最小ジャンプ回数を求めるC++コード

    長さnの2進文字列Sと整数dが与えられます。数直線上で、カエルは地点1から出発し、地点nへの到達を目指しています。カエルは1回のジャンプでd以下の距離だけ右方向へ移動できます。地点1からnまでの各地点には、スイレンの花が咲いていれば「1」、なければ「0」が記されており、カエルはスイレンのある地点にしか着地できません。カエルが地点nに到達するために必要な最小ジャンプ回数を求めましょう。到達が不可能な場合は-1を返します。 例えば、入力が S = 10010101、d = 4 の場合、出力は 2 になります。これは、位置1(インデックス0)からインデックス4へジャンプし、続けてインデックス7(n

  15. 2つのプレスの間で人が生き延びられる時間を求めるC++プログラム

    本記事では、相向かって移動する2つのプレスの間で、人があとどれだけの時間生き延びられるかを計算するC++プログラムを紹介します。問題の概要4つの数値 d、L、v1、v2 が与えられます。2つのプレスは、それぞれ初期位置 0 と L にあります。2つのプレスは、それぞれ速度 v1 と v2 で互いに向かって移動します。人の幅は d であり、2つのプレスの間隔が d よりも狭くなった時点で、人は押しつぶされてしまいます。このとき、人が生きていられる時間（生存時間）を求める必要があります。入力例例えば、入力が次のようだったとします。d = 1; L = 9; v1 = 1; v2 = 2;この場合、

  16. 【C++】石を渡すことができる最大回数を求めるアルゴリズム

    整数 n が与えられた場面を考えてみましょう。Amalは Bimal に対して何度でも石を渡すことができますが、ある手番で k 個の石を渡した場合、その直後の手番で同じく k 個の石を渡すことはできません。つまり、連続する2つの手番では必ず異なる個数の石を渡す必要があるというルールです。 この条件下で、Amalが Bimal に石を渡せる回数は最大で何回になるのかを求めるのが本記事の目的です。 具体例 入力が n = 4 の場合を考えます。 「1個 → 2個 → 1個」の順で石を渡せば、合計4個を3回の手番で渡すことができます。これ以上回数を増やすことはできないため、出力は 3 となります。

  17. 時刻tで立っている観客の人数を求めるC++プログラム

    3つの整数 n、k、t が与えられたとします。Amalは「メキシカンウェーブ」を分析しています。1番からn番までのn人の観客がおり、時刻0から動き始めます。時刻1で1番目の観客が立ち、時刻2で2番目の観客が立ちます。時刻kでk番目の観客が立ち、時刻(k+1)では(k+1)番目の観客が立つと同時に1番目の観客が座ります。さらに時刻(k+2)では(k+2)番目の観客が立ち、2番目の観客が座ります。このように進み、時刻nではn番目の観客が立ち、(n−k)番目の観客が座ります。時刻(n+1)以降も、(n+1−k)番目の観客が座るといった具合に波が続いていきます。ここで求めたいのは、時刻tにおいて立って

  18. C++でnピクセルのディスプレイサイズを求めるアルゴリズム

    ある数 n が与えられ、これがディスプレイ上のピクセル総数だとします。このとき、条件を満たす長方形ディスプレイのサイズ（行数と列数）を求めるのが本記事の目的です。問題の条件行数 a は列数 b を超えない（a <= b）b − a の差はできるだけ小さくなるようにする例えば、入力が n = 12 の場合、出力は (3, 4) となります。3 × 4 = 12 ピクセルであり、行数が列数以下で、かつ差が最小になる組み合わせだからです。解き方の手順この問題は、n の平方根から始めて、n を割り切れる最大の約数を見つけることで効率的に解けます。手順は以下の通りです。i := n の平方根 wh

  19. 紙飛行機に必要な紙のパック数を計算するC++プログラムの解説

    問題の概要4つの整数 k、n、s、p が与えられます。紙飛行機を作るには、長方形の紙を使用します。標準サイズの紙1枚からは、s 機の紙飛行機を作ることができます。k 人のグループが、それぞれ n 機ずつ紙飛行機を作ることにしました。彼らは p 枚入りの紙のパックを何個か購入し、その紙をグループのメンバー全員に分配します。各人が n 機の紙飛行機を作れるだけの枚数を確保できるようにするには、パックを何個購入すればよいでしょうか?例えば、入力が k = 5、n = 3、s = 2、p = 3 の場合、出力は 4 になります。1人あたり2枚の紙が必要となり、合計で12枚必要になるため、3枚入りのパッ

  20. C++で解く！面白い瞬間の間隔から試合の視聴時間を求めるアルゴリズム

    n個の要素を持つ配列Aがあるとしましょう。Amalは90分間の試合を観戦したいと考えており、試合中に休憩はありません。試合の各1分は「面白い」または「退屈な」のどちらかに分類され、15分連続して退屈な時間が続くと、Amalは直ちにテレビの電源を切ります。配列Aには、面白くなる瞬間の経過時間（分）がn個記録されています。このとき、Amalが合計で何分間試合を視聴することになるのかを求めます。例えば、入力が A = [7, 20, 88] の場合、出力は 35 になります。20分までは面白い瞬間が15分以内の間隔で訪れるため視聴を続けられますが、その後88分まで次の面白い瞬間が訪れないため、20

Total 5990 -コンピューター  FirstPage PreviousPage NextPage LastPage CurrentPage:299/300  20-コンピューター/Page Goto:1 293 294 295 296 297 298 299 300