シミュレーション
for 文で隣接する要素を見ながら処理していく系の問題 問題へのリンク 問題概要 長さ の文字列 が与えられる。 を左から見ていき、文字列 "joi" が含まれるならば、これを "JOI" に変換していく処理を繰り返す。操作後の文字列を出力せよ。 解法 次のように…
reverse する系の問題 問題へのリンク 問題概要 長さ の文字列 について、 文字目から 文字目までを反転して得られる文字列を出力せよ。 制約 解法 C++ でプログラムを書くときは、通常文字列は 0 始まりですので、 からあらかじめ 1 引いておきます。 その…
マージソートのマージの部分を実装する問題ですね。 添字を順に進めていくような処理を実装します! この実装は、のちにしゃくとり法を学ぶ際の参考にもなります。 問題へのリンク 問題概要 制約 解法 問題文が複雑で、何をすればいいのかを理解するのが大変…
少し面白い問題! 問題へのリンク 問題概要 長さが 1, 2, 3 のいずれかの文字列 が与えられる。 を繰り返して得られる文字列であって、長さが 6 であるものを答えよ。 考えたこと 次のように考えれば良い。 の長さが 1 のとき: を 6 回繰り返す の長さが 2 …
上手に解釈して問題を解こう! 問題へのリンク 問題概要 0 と 1 のみからなる長さ 4 の文字列 が与えられる。この文字列は、4 マスからなる各マスに人がいるかどうかを表す。 はそのマスに人がいることを表し、 は人がいないことを表す。 今、人がみな右へ移…
for 文の練習! 問題へのリンク 問題概要 長さ の数列 (すべての要素は互いに相異なる) について、最大値を考えたとき、その左側の総和と、右側の総和をそれぞれ求めよ。 制約 解法 この問題では、数列 の最大値だけではな、 が最大となるような も求める必…
これは面白い! 問題へのリンク 問題概要 文字 J, O, I からなる、長さ の文字列 が与えられる。 の文字を並び替えて、次の条件を満たすものを求めよ。 すべての文字 J は、すべての文字 O よりも前にある すべての文字 O は、すべての文字 I よりも前にある…
どのようにデータを管理すればよいか、難しいと感じるかもしれない。 問題へのリンク 問題概要 最初、箱 にそれぞれボール が入っている。 次の 回の操作を行う。 回目の操作では、ボール が入っている箱から、ボール を取り出して、それを箱 に入れる。 操…
シミュレーションしてもいいし、数学的に綺麗に解くこともできる! 問題へのリンク 問題概要 時計は 1 〜 12 を繰り返す。 時の 時間後は、何時であるかを答えよ。 制約 解法 (1):シミュレーション から出発して、 回以下のことを繰り返せばよい。 1 増やす…
for 文を回しながら、隣接要素を見ていく練習をしよう! 問題へのリンク 問題概要 個の整数 が与えられる。 に対して、 の値を順に求めよ。 制約 考えたこと for 文を回しながら、隣の要素も同時に見ていくスキルを習得しよう! コード #include <bits/stdc++.h> using name</bits/stdc++.h>…
for 文の練習! 問題へのリンク 問題概要 個の整数 が与えられる。 これらのうち、 で割り切れるものについて、 で割った値を順に出力せよ。 考えたこと 入力を配列 (C++ ならば vector 型など) で受け取り、for 文を使って配列の各要素にアクセスしていこう…
ooxooxooxoox... を出力する問題 問題へのリンク 問題概要 髙橋君はサッカーの試合で 回ペナルティキックを蹴る。3 の倍数回目は失敗する。 回分のキックの結果を出力せよ。 解法 for 文を用いて、 について が 3 の倍数のとき:文字 'x' を出力 そうでない…
愚直に数えるのが簡単だと思う。 問題へのリンク 問題概要 人の生徒のマラソン大会のタイム が与えられる。 各生徒の順位を求めよ。具体的には各生徒 について、( 未満のタイムの個数) + 1 を求めよ。 制約 解法 各 に対して、具体的に「( 未満のタイムの個…
意外と難しいかもしれない。for 文を回しながら、「前の文字」を見る技術を手に入れよう! 問題へのリンク 問題概要 文字 j, o, i からなる長さ の文字列 が与えられる。 この文字列をテキストエディタに打ち込むことを考える。同じ文字が 2 個連続したとき…
「検索」をしながらのシミュレーション! 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 回のゲームをする。最初の得点は 0 点である。 回目のゲームでは、得点が 点増加する。ただし、増加したあとの得点が、もし数列 の中に含まれ…
問題文に言われた通りにシミュレーションする問題! 問題へのリンク 問題概要 長さ の文字列 があって、各文字は 'L' または 'R' である。 また、1 つのボールと、ボールを入れることができる箱 があって、最初ボールは箱 1 に入っている。文字列 の文字を順…
回転寿司を題材にした、とても教育的な面白い問題! 問題へのリンク 問題概要 高橋君は料理を 皿分食べた。皿 の色は文字列 であった。 また、料理の価格は皿の色と対応し、各 について、色が文字列 の皿の料理は一皿 円である。 また、 のいずれとも異なる…
ビンゴを題材とした問題。行・列・斜めを合わせて 個のラインがあるので、各ラインの空きマス数を管理しよう。 問題へのリンク 問題概要 のグリッドがあり、上から 行目、左から 列目のマスには整数 が書かれている。 今から ターンの穴あけをする。 ターン…
元ネタのあるシミュレーション問題 問題へのリンク 問題概要 高橋君は英小文字からなる文字列 をキーボードで入力しようとしました。 高橋君は誤って別の英小文字を入力してしまったときにはその直後にバックスペースキーを押しましたが、バックスペースキー…
「グラフ」の基礎になるような、配列上のシミュレーションの問題。 問題へのリンク 問題概要 整数 が与えられる。 このとき、ボタンを押すと、画面の数値 () が に変わる。 最初の数値が 0 であるとき、ボタンを 3 回押すと、どんな数値に変わるか? 考えた…
for 文の練習問題。 問題へのリンク 問題概要 長さ の整数列 が与えられる。 この数列の 番目の要素の直後に値 を挿入して得られる数列を出力せよ。 解法 (1):関数 erase() を利用する C++ では、vector 型変数 A に対して、 番目に値 を挿入する処理は A.i…
この手のシミュレーションになれることはとても大事! 問題へのリンク 問題概要 あるチケット売り場は、待合行列がなければ、来た人の受付に 秒かかる。 人の人 は、それぞれ時刻 に到着する。まだ受付されていない人がいる場合は後ろに並ぶ。 人 がそれぞれ…
スタックを活用する系の問題! 問題へのリンク 問題概要 値 の書かれたボールをこの順に筒に挿入していく。 挿入された際に、同じ数 が 個連続したら、それらがすべて消えるものとする。 個目のボールが挿入された瞬間の、筒内のボールの個数を逐次答えよ。 …
文字列の index アクセスと、操作 swap をする問題 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。 の 文字目と 文字目を sawp して得られる文字列を答えよ。 解法 文字列 S の a 文字目は S[a-1] で取得できる。b 文字目は S[b-1] で取得…
for 文の練習! 問題へのリンク 問題概要 1 個の "L"、 個の "o"、1 個の "n"、1 個の "g" をこの順に連結して得られる文字列を出力せよ。 解法 途中の「 個の "o"」を出力する部分では for 文が使える。 コード #include <bits/stdc++.h> using namespace std; int main() </bits/stdc++.h>…
for 文の練習! 問題へのリンク 問題概要 正の整数 が与えられる。 個の 0 と 個の 1 を交互に並べた文字列を出力せよ。 解法 色んな解法が考えられるが、ここでは次のように解釈した。 "10" を 回出力する 最後に "1" を出力する コード #include <bits/stdc++.h> using na</bits/stdc++.h>…
カッコ列に関連してシミュレーションしていく問題! 問題へのリンク 問題概要 英小文字と文字 '('、')' からなる長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返す。 「文字 '(' と ')' に挟まれた部分文字列であって、カッコ文字を含ま…
いろんな方法で実装できそう! 問題へのリンク 問題概要 非負整数 に対して、レベル のカーペットを再帰的に定義する。 レベル のカーペットは、"#" からなる 1 × 1 のグリッドである に対して、レベル のカーペットは のグリッドであり、 このグリッドを の…
意外とミスりやすいかもしれない。慎重に for 文を書こう。 問題へのリンク 問題概要 個の正の整数 と、正の整数 が与えられる。 に対して、 を順に引いていく。このとき、 が負にならずに引ける最大個数を求めよ。 解法 実際に順番に から引いていって、 で…
はじめての「〜が 以下になる瞬間」を捉えるというシミュレーション問題。 問題へのリンク 問題概要 高橋君は 種類の薬を処方された。薬 は、 日目まで、毎日 錠ずつ飲むこととなる。 1 日に飲む錠剤の個数がはじめて 錠以下になる日を求めよ。 制約 考えた…