けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

愚直シミュレーション

JOIG 2023 B - 絶対階差数列 (AOJ 0758, 難易度 2)

いわゆる「愚直シミュレーション」と呼ばれる分野の問題ですね。問題文で指示されたことを、とにかく愚直に忠実に実装できるかが問われています。地味な印象を受けるかもですが、大切なスキルです! 問題へのリンク 問題概要 黒板に、はじめ 個の整数値 が書…

JOI 予選 2007 D - カードの並び替え (AOJ 0513, 難易度 3)

難しくはないけど、やることが複雑だし、問題文を読み解くのがハードな問題! この手の問題は、解けないと思ったら、実際のコードを見てしまう方が早いと思う。 問題へのリンク editorial 問題概要 正の整数 が与えられる。 1 から までの数値が書かれたカー…

AtCoder ABC 303 C - Dash (灰色, 300 点)

set をちゃんと使えるかを試す問題! 問題へのリンク 問題概要 高橋くんは最初、体力は であり、二次元平面上の座標 にいる。 高橋くんは今から 回の移動を行う。高橋くんの移動方法は長さ の文字列 で表される。1 回の移動は、上下左右のいずれかであり、そ…

DISCO presents 2016 予選 B - ディスコ社内ツアー (青色)

シミュレーションの仕方を工夫する問題。数値ごとに index をまとめあげるデータを持つとうまくいく。 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。 の順列 であって、 を満たすものを考える。そのような順列の (ただし である場合の の場合は…

AtCoder ABC 281 C - Circular Playlist (灰色, 300 点)

「割り算を使う」「ある値が 0 以下になるまで繰り返す」といった典型処理要素を詰め込んだ問題ですね! 問題へのリンク 問題概要 曲からなるプレイリストがあり、曲には の番号が付けられています。各曲の長さは です。 プレイリストを再生すると、曲 の順…

AtCoder ABC 250 C - Adjacent Swaps (茶色, 300 点)

実はアルゴ式でもよく似た問題をすでに出していました! algo-method.com 問題へのリンク 問題概要 がこの順に並んでいます。この数列に対して 回のクエリが投げられました。 各クエリでは、値 が指定されて、次の操作を実行します。 数列中の整数 に対し、…

AtCoder ABC 213 D - Takahashi Tour (茶色, 400 点)

DFS (深さ優先探索) の動きをシミュレーションする問題。 問題へのリンク 問題概要 頂点番号が であるような木が与えられます。 今このグラフにおいて、頂点 1 から出発して、次の動きを繰り返します。 いまいる頂点に隣接する頂点のうち、まだ訪れたことが…

JOI 二次予選 2021 A - 往復すごろく (AOJ 0691, 難易度 5)

結構アドホックで難しいと思った! 問題へのリンク 問題概要 マスが横一列に並んだすごろくが与えられる ( と番号づけされている)。すごろくの各マスは . と x と # のいずれかである。 マス とマス は X である 他のマスは長さ の文字列 で与えられる X は…

AOJ 2904 GuruGuru (JAG 夏合宿 2018 day3-A) (200 点)

英文だし、題意をちゃんと読み解くのがちょっと大変 問題へのリンク editorial 問題概要 L と R のみから構成された文字列 が与えられる。ロボットは最初北方向を向いている。文字列 を左から順番に読んで次のように処理していく。 L のとき、ロボットは 90 …

AtCoder ABC 151 C - Welcome to AtCoder (灰色, 300 点)

間違わないように、正確に、シミュレーションする問題。 C、大好き!!!!!!「言われたことを正確にこなせるか」というシミュレーション問題なんだけど、題材が面白い上に、配列か連想配列で情報を管理することを要求したり、少し注意力も要求する感じが…

AtCoder ABC 141 C - Attack Survival (灰色, 300 点)

ちょっと視点を変える感じ。 「反対側とか補集合とか余事象とか考えてみると解ける」という感じの問題は、300 点あたりからよく出てくる 問題へのリンク 問題概要 人がいてそれぞれ ポイントずつもっている。 これから ラウンドのクイズがあって、 ラウンド…

AtCoder AGC 002 B - Box and Ball (緑色, 400 点)

うまくシミュレーションする系 問題へのリンク 問題概要 N 個の箱があります。 箱は 1 から N まで番号が振られています。 最初、1 番目の箱には赤いボールが 1 個入っています。 また、2~N 番目の箱には白いボールが 1 個ずつ入っています。 高橋君は M 回…

AtCoder ABC 123 C - Five Transportations (茶色, 300 点)

結構難しい... 問題へのリンク 問題概要 人全員が最初都市 1 にいて、全員を都市 1 -> 2 -> 3 -> 4 -> 5 -> 6 へと順番に進んで、全員が都市 6 にいる状態にしたい。 都市 1 から都市 2 への移動手段は毎秒ごとに提供されているが、同時に 人しか行けない。…

全国統一プログラミング王決定戦 本選 D - Deforestation (500 点)

遅延評価セグメントツリーで殴った...速度重視ならそれでいい気もする 問題へのリンク 問題概要 本の竹があって、時刻 0 においてすべての竹の高さは 0 である。それぞれの竹は時刻が 1 経過するごとに高さが 1 増える。 竹を伐採するイベントが 回予定され…

AOJ 2589 North North West (JAG 模擬地区 2014 A) (200 点)

とにかく言われた通りにやる 問題へのリンク 問題概要 northnorthwest (北北西) のように言われて、それを真北方向から何度ずれているかを既約分数で表示せよ (上の例の場合は 45/2) 考えたこと 詳細仕様が問題文中にあるので、とにかく言われた通りに頑張る…

AOJ 1149 ケーキカット (ICPC 国内予選 2007 C) (300 点)

AOJ-ICPC 300 点。 問題へのリンク 問題概要 (略) ケーキをカットして行ってできるピースの面積をそれぞれ答えよ 考えたこと ケーキの中がどう分割されているかは一切関係ないので、毎回バラバラなピースがあってそこから 1 個選んで分割してそれを最後尾に…