シミュレーション
for 文のいい練習問題！ 問題へのリンク 問題概要 高橋君は 問のクイズに答える。最初 点であり、正解すると 1 点増加する。不正解だと 1 点減少するが、不正解前に 0 点である場合は減らない。 高橋君が各問題に正解したかどうかを表す文字列 が与えられる…
シミュレーションを冷静に実装しよう！ 問題へのリンク 問題概要 マス があって、マス 1 はスタート、マス 2019 はゴールである。 個のコマがあり、それぞれ 番目にマスに置かれている。 次の 回の操作を実行する。 回目の操作ではコマ を動かそうとする も…
結構頭がこんがらがる問題だと思う。 問題へのリンク 問題概要 あるソーシャルゲームでは、1 日につき 1 回までログインすることができ、ログインするたびに 枚のコインが得られる。 さらに、月曜日から日曜日まで 7 日連続でログインすると、そのたびに、追…
二次元グリッド上で、マス の上下左右のマスがなんであるかを学ぶ問題！ 問題へのリンク 問題概要 の二次元グリッドが与えられる。グリッドの各マスは '.'（通路）または '#'（壁）である。 はじめ高橋くんはマス にいる。これから高橋君に 回の命令がくだる…
完全な愚直シミュレーションでは通らなくて、割り算で繰り返し回数を求める系の問題！ 問題へのリンク 問題概要 体の敵を順に倒す。 体目の敵の HP は である。 あなたは に初期化された変数 を管理している。敵を攻撃するとき、次のようにする。 を 1 増や…
問題の条件をいかにうまく言い換えるか！ 問題へのリンク 問題概要 2 つの整数 が与えられる（）。 を小数点第四位を四捨五入して、小数点第三位まで表した結果を求めよ。 考えたこと を整数型ではなく、浮動小数点型として受け取って、B / A を計算して小数…
問題文の操作を上手に言い換えて、for 文で処理できる形にしよう！ 問題へのリンク 問題概要 長さ の数列 に対して、以下の操作を 回実施してできる数列を出力せよ。 数列の先頭の数値を削除し、末尾に 0 を挿入する 制約 考えたこと C++ では、数列は vector<int></int>…
意外と実装に手こずった人も多いかもしれない。上手に for 文で実装できる操作に言い換えていこう！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 今、 かつ をみたす 4 つの整数 が与えられる。 数列 の 番目から 番目の項までと、 番目から 番目の…
配列の中に配列型式の添字を入れるような処理（A[B[i]] のような）を書けるようになろう！ 問題へのリンク 問題概要 あるコンテストでは 問が出題され、配点はそれぞれ 点であった。 参加者のすぬけ君は、このうちの 問 問を解いた。 すぬけ君の得点はいくら…
言われた通りに処理していくだけだが、最初は意外と手こずるかもしれない。 問題へのリンク 問題概要 英小文字からなる長さ偶数の文字列 が与えられる。 の順に、 と を入れ替える。 操作後の文字列を出力せよ。 考えたこと C++ では文字列の最初の文字は 0 …
for 文で、隣接する要素も見ながら走査していく系の問題！ 問題へのリンク 問題概要 高橋君は時刻 0 にパソコンを起動し、時刻 にクリックをした。 となるとき、クリック はダブルクリックが成立したという。 ダブルクリックが最初に成立した時刻を求めよ。…
言われた通りにシミュレーションする問題！ 問題へのリンク 問題概要 長さ の正の整数からなる数列 が与えられる。この数列に対して 降順にソートする から 1 を引く という操作を「数列に含まれる正の数が 1 個以下」になるまで繰り返す。操作は何回行うこ…
for 文を工夫しよう 問題へのリンク 問題概要 長さ の数列 が与えられる。 この数列の末尾の 個の要素を順序を保ったまま先頭に持ってきて得られる数列を出力せよ。 制約 考えたこと 次のように考え直すとよい。なお、0-indexed で考えている。 数列の 番目…
ちょっと実装が大変なので、頑張って実装しよう！ 問題へのリンク 問題概要 太郎君と花子さんが大富豪を模したゲームをする。 の書かれたカードを、 枚ずつ、太郎君と花子さんに配る。太郎君に配られたカードに書かれた 個の数値が与えられる。2 人で次のよ…
小数点以下の「0」を除外する問題 問題へのリンク 問題概要 小数点第三位まで記述された数 が与えられる。次のようにせよ。 小数点以下の部分について、末尾に 0 を付けない 末尾に過剰な小数点を付けない 制約 考えたこと 末尾の 0 を除外していけば良い。…
今や超有名な Greedy 問題「コインの枚数最小化問題」 問題へのリンク 問題概要 JOI 雑貨店には硬貨は 500 円、100 円、50 円、10 円、5 円、1 円の硬貨が十分な枚数ある。 円の買い物をして 1000 円を支払った太郎くんに、硬貨の枚数が最小となるようにお釣…
for 文を使って、等差数列を実現する！ 問題へのリンク 問題概要 初項が 、末項が 、公差が であるような等差数列を出力せよ。 なお、そのような等差数列が存在する入力のみが与えられる。 考えたこと 等差数列の中でも、次のようなものは我々はいつも実装し…
これ結構難しい気がする！ グラフの問題の一種。 問題へのリンク 問題概要 人 がいる。高橋君（ 人のいずれとも異なる）は、自分の秘密を、この中の人 に知られてしまった。 一般に、人 は新たに秘密を知ったときには、人 にも伝えてしまう。 高橋君の秘密は…
1 秒ごとにシミュレーションする方法と、数学的に 2 人の休憩時間をそれぞれ求める方法とがある。どちらもできるようにしておきたい！ ここでは、数学的に処理する方法を書く。 問題へのリンク 問題概要 高橋君は「 秒間秒速 メートルで歩き、 秒間休む」こ…
制約が小さいのでなんとでもなる。C++ なら文字列の末尾を削除する関数 pop_back() を知っていると楽だと思われる。 問題へのリンク 問題概要 エディター上で、'0'、'1'、'B' という 3 種のタイピング入力を行う。 '0' と打つと、エディターに表示された文字…
文字列の部分文字列を取得する関数 substr() (C++) を用いるか、for 文で書こう。 問題へのリンク 問題概要 文字列 "atcoder" について、 文字目から 文字目までを出力せよ。 制約 解法 (1)：関数 substr() を使う。 文字列 S に対して、 S.substr(i, l) は…
シミュレーションで解くか、数学的に解こう！ 問題へのリンク 問題概要 シャンプーが mL 余っている。 F さん、M さん、T さんが順に mL ずつ使っていく。最初にシャンプーが足りなくなる人が誰になるかを求めよ。 解法 (1)：シミュレーション まずは、シャ…
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 よりも前にある…
どのようにデータを管理すればよいか、難しいと感じるかもしれない。 問題へのリンク 問題概要 最初、箱 にそれぞれボール が入っている。 次の 回の操作を行う。 回目の操作では、ボール が入っている箱から、ボール を取り出して、それを箱 に入れる。 操…
