シミュレーション
ランレングス圧縮で解いた 問題へのリンク 問題概要 0 と 1 からなる長さ の文字列 が与えられる。この文字列の中での「1 の塊」のうち、左から 番目のものを、 番目のものの右に移動させよ。 例："010011100011001" → "010011111000001" 制約 考えたこと ま…
初歩的な構文解析問題 問題へのリンク 問題概要 "|---|-|----|-|-----|" のような、文字 '-' を文字 '|' で separate された文字列 が与えられる。 各 '-' 区間の '-' の個数を順に出力せよ。 制約 考えたこと ここでは for 文で解いてみよう。次の変数を管…
「全体に足す」のは難しいから、足す値を別途持っておくというスキル！！！ 問題へのリンク 問題概要 以下の 個のクエリに答えよ。 クエリタイプ 1：新たに要素 0 を挿入する（重複もあり） クエリタイプ 2：すでに挿入されているすべての要素に を足す クエ…
いかにも stack が登場しそうな問題！ 問題へのリンク 問題概要 下の図のように、高さが の仕切りが等間隔に並んでいて、その間と両端の カ所のスペースを表す番号を とする。これらは幅が等しい。 今、スペース 0 に水を入れていく。1 個分のスペースについ…
「前回の値」を保持しながらシミュレーションする系 問題へのリンク 問題概要 ボタンを押すと、1 個の飴がもらえるが、前回飴をもらってから 秒間はもらえない。 高橋君は 回ボタンを押した。それぞれ 秒後に押した（これらは単調増加）。 何回飴をもらえた…
これ結構難しくて、嵌まる人は嵌まってしまうと思う！！ 問題へのリンク 問題概要 ダンジョンには、ポーション と、敵 がいる。 今、ダンジョンで 個のイベントが起こる。イベント は 2 つの整数 で表される。 のとき：ポーション が現れる それを拾うかどう…
スタックによるシミュレーション問題！ 問題へのリンク 問題概要 整合のとれたカッコ列に対して、英小文字がいくつか挿入されてできる文字列が与えられる (たとえば、"(a(ba))c")。 このような文字列に対して、高橋君が気絶するかどうかを判定したい。次のよ…
愚直シミュレーションをする問題。ただ、ある程度は計算量を知らないとドツボにハマる可能性がある。 問題へのリンク 問題概要 あるシャワーは、スイッチを押すとその後 秒間お湯が出る (延長するわけではない)。 時刻 (単調増加) にスイッチを押したとする…
mod の練習。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 最初、黒板に 0 という数が書かれている。以下の 回の操作を実行せよ。各操作では文字 と数 が与えられる。 = '+' のとき：黒板に書かれた数を、 を足した数に書き直す = '-' のとき…
各文字がどこにあるのかを求めると楽になる。 問題へのリンク 問題概要 'A' から 'Z' までの文字を 1 つずつ含む文字列 が与えられる。 内部での 'A' から 'B' への移動距離 (index の差分) 'B' から 'C' への移動距離 (index の差分) 'C' から 'D' への移動…
すごろくを題材にした問題。すごろくの各マスには「oo マス進む」などの指示がある。これを上手に管理しよう。 問題へのリンク 問題概要 マス からなる双六が与えられる。マス 1 がスタート、マス 以上がゴールである。 回サイコロを振って、 回目には目 だ…
スタックのいい練習問題！ 問題へのリンク 問題概要 空の列と 個のボールがある。 番目のボールの大きさは である。これから 回の操作を行う。 回目の操作では、 個目のボールを列の一番右に付け加えた後、次の手順を繰り返す。 列にあるボールが 1 つ以下な…
まともに計算すると桁数がとんでもないことになるので、「LU で消す」「RU で消す」を活用しよう！ 問題へのリンク 問題概要 頂点数が十分多い完全二分木が与えられる。根の番号は 1 であり、一般に頂点 の左子頂点の番号は 、右子頂点の番号は である。 最…
キューの使い方の確認！ 問題へのリンク 問題概要 以下の 3 種類のクエリ ( 個) を高速に処理するプログラムを実装せよ。行列管理システムを模している。 クエリタイプ 1：行列の最後尾に さんが並ぶ クエリタイプ 2：行列の先頭にいる人の名前を答える クエ…
スタックを用いたシミュレーション問題！ 問題へのリンク 問題概要 最初、本は積まれていない。次の 回のクエリに答えよ 【クエリ】 各クエリでは文字列 が与えられる。 が "READ" ではないとき、タイトルが である本が新たに上に積まれる が "READ" である…
バケットを活用する練習問題！ 問題へのリンク 問題概要 AtCoder 王国には 家がある。どこかの家で順に 人の赤子が生まれた。 人目の赤子は家 で生まれ、性別は （'M' または 'F'）であった。 各赤子が長男であるかどうかを判定せよ。 制約 考えたこと 人目…
問題文の理解が大変かもしれない 問題へのリンク 問題概要（意訳） 2 つの正の整数 を次のように 回更新していく。最初、 である。 回目の更新では 2 つの互いに素な正の整数 が与えられるので、 を満たすような 2 つの正の整数 を 1 つ求めて、 をそれぞれ …
シミュレーションするか、ソートするかによって解ける典型問題！ 問題へのリンク 問題概要 人の髪の長さは最初 であった。 各人の髪の長さは 1 日に 1 ずつ伸びる。 初めて髪の長さが 以上の人が 人以上となるのは何日後かを求めよ。 制約 解法 (1)：シミュ…
問題文がやたら難読すぎる！！！ 問題へのリンク 問題概要（意訳） 個の文字列 が与えられる。これに対して、次のように縦横をひっくり返して、隙間を文字 * で埋めたようなものを出力せよ。 before red orang blue yellow green gray skyblue black after b…
こういう値を順次更新していくようなシミュレーションは慣れておきたい！ 問題へのリンク 問題概要 元素 がある。 元素 を合成すると、 のときは元素 になり、 のときは元素 になる。 元素 に対して、元素 を順に合成していったとき、最終的にできあがる元素…
愚直シミュレーション問題！ 問題へのリンク 問題概要 A さん、B さん、C さんの 3 人が以下のようなカードゲームをプレイしています。 最初、3 人はそれぞれ 'a', 'b', 'c' いずれかの文字が書かれたカードを、何枚か持っている。これらは入力で与えられた…
シミュレーションと呼ばれるジャンルの中では、最も重たい部類の問題 問題へのリンク 問題概要 1 から までの整数の書かれたカードがこの順に並んでいる。このカード列に以下の 回の操作を行う。 回目の操作は、整数 （）によって表される。操作前のカードの…
このようなシミュレーションをサッと書けるようになりたいところ！ 問題へのリンク 問題概要 横一列に 100 個の鍵盤からなるピアノがある。各鍵盤には順に と番号が振られている。 鍵盤を 回押す。 回目の鍵盤の位置は であり、 = 'L' のとき左手で押し、 = …
if 文や else if 文の練習！ 問題へのリンク 問題概要 高橋君は 枚、青木君は 枚のクッキーをもっている。 高橋君は 回次の行動をとる。 自分のクッキーが残っていたら、それを 1 枚食べる 残っていなくて、青木君のクッキーが残っていたら、それを 1 枚食べ…
for 文のいい練習問題！ 問題へのリンク 問題概要 高橋君は 問のクイズに答える。最初 点であり、正解すると 1 点増加する。不正解だと 1 点減少するが、不正解前に 0 点である場合は減らない。 高橋君が各問題に正解したかどうかを表す文字列 が与えられる…
シミュレーションを冷静に実装しよう！ 問題へのリンク 問題概要 マス があって、マス 1 はスタート、マス 2019 はゴールである。 個のコマがあり、それぞれ 番目にマスに置かれている。 次の 回の操作を実行する。 回目の操作ではコマ を動かそうとする も…
結構頭がこんがらがる問題だと思う。 問題へのリンク 問題概要 あるソーシャルゲームでは、1 日につき 1 回までログインすることができ、ログインするたびに 枚のコインが得られる。 さらに、月曜日から日曜日まで 7 日連続でログインすると、そのたびに、追…
二次元グリッド上で、マス の上下左右のマスがなんであるかを学ぶ問題！ 問題へのリンク 問題概要 の二次元グリッドが与えられる。グリッドの各マスは '.'（通路）または '#'（壁）である。 はじめ高橋くんはマス にいる。これから高橋君に 回の命令がくだる…
完全な愚直シミュレーションでは通らなくて、割り算で繰り返し回数を求める系の問題！ 問題へのリンク 問題概要 体の敵を順に倒す。 体目の敵の HP は である。 あなたは に初期化された変数 を管理している。敵を攻撃するとき、次のようにする。 を 1 増や…
問題の条件をいかにうまく言い換えるか！ 問題へのリンク 問題概要 2 つの整数 が与えられる（）。 を小数点第四位を四捨五入して、小数点第三位まで表した結果を求めよ。 考えたこと を整数型ではなく、浮動小数点型として受け取って、B / A を計算して小数…
