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

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

シミュレーション

Educational Codeforces 80 E. Messenger Simulator (R2100)

面白かった。 数列の区間に含まれる値の種類数を答えるクエリに素早く答える技術が必要になった。 問題へのリンク 問題概要 がこの順に並んでいる。ここから 回の操作を行う。 回目の走査は、 以上 以下の値 で表され 現在の順列のうち、値 を先頭にもってく…

AtCoder ABC 151 C - Welcome to AtCoder (300 点)

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

AtCoder ABC 148 D - Brick Break (400 点)

とても教育的な Greedy かもしれない! 問題へのリンク 問題概要 長さ の正の整数からなる数列 が与えられる。この数列からいくつかの値を取り除くことで、数列が となるようにしたい。 取り除くべき個数の最小値を求めよ。どのように取り除いても の形にで…

AtCoder ABC 061 C - Big Array (300 点)

「k 番目を求める」に関する典型的な処理を要求される問題。 問題へのリンク 問題概要 空集合 に対して、以下の 回の操作を行う: に整数 を 個挿入する 回の操作後の S において 番目に小さな値を求めよ。 制約 考えたこと この問題の注意点として、 を具体…

AtCoder ABC 141 C - Attack Survival (300 点)

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

AtCoder AGC 014 A - Cookie Exchanges (300 点)

何回も何回も操作すると同じことになる系 問題へのリンク 問題概要 3 つの整数 があたえられる。以下の操作を行えなくなるまで繰り返す: 3 つの整数の中に奇数が 1 個でもあったら終了 すべて偶数だったら を に置き換える 操作を何回行うか?無限に行う可能…

AtCoder AGC 011 D - Half Reflector (900 点)

この問題が解けた勝因は、「実験しよう」と思えたことな気がする。 問題へのリンク 問題概要 高橋君は,ある特殊な装置をたくさん持っています. この装置は筒状で,左右からボールを入れることができます. また,この装置には 2 種類の状態 A, B がありま…

AtCoder ABC 126 C - Dice and Coin (300 点)

確率を確実に 問題へのリンク 問題概要 正の整数 が与えられる。 最初に の整数値をランダムに出力する。以降コインを振って 表が出たら整数値を 2 倍する ( 以上になったら「勝ち」でゲーム終了) 裏が出たら整数値を 0 にする (こうなった時点で「負け」で…

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

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

Codeforces 552 DIV3 E. Two Teams (R1800)

超苦手タイプ 問題へのリンク 問題概要 要素からなる順列があたえられる。先手と後手が交互に 残っている中から最大要素を選び、その左右 要素を合わせて 要素を、自分のところに抜き取ってくる (左右に 要素残っていない場合はある分だけ抜き取ってくる) と…

エクサウィザーズ 2019 C - Snuke the Wizard (500 点)

頭の整理が大変!!! 問題へのリンク 問題概要 左から右に向かって 1 から N の番号がついた N 個のマスがあります。 各マスには文字が書かれており、マス i には文字 si が書かれています。また、各マスにははじめ 1 体のゴーレムがいます。 すぬけ君は Q …

Mujin 2018 D - うほょじご (400 点)

いかにもよくわからない操作問題なので、難しいことは考えずに探索に走るべきな雰囲気 atcoder.jp 問題概要 正の整数 に対し、 で を 10 進表記してできる文字列を反転したものを 10 進表記に持つ整数を表す。 正の整数 が与えられる。 なる整数の組 であっ…

AtCoder AGC 001 B - Mysterious Light (500 点)

Euclid の互除法な操作過程をたっぷりと味わえる味わい深い問題。 問題へのリンク 問題概要 一辺の長さが の正三角形の図のような の地点からビームを発射する。このとき、既にビームが通ったところは新たに壁になる。ビームは必ず元の場所に戻ることが証明…

AOJ 3052 Milk (RUPC 2019 day2-B)

難しかった 問題へのリンク 問題概要 ちょうど 本の牛乳の空き瓶を持っていくと新たに 本の牛乳の入った瓶と交換できる。 最初に 本の牛乳の入った瓶を持っているとき、最大で何本分の牛乳を飲めるかを 1000000007 で割ったあまりを求めよ。 制約 < 考えたこ…