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

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

シミュレーション問題

AtCoder ABC 123 C - Five Transportations (300 点)

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

AtCoder AGC 006 D - Median Pyramid Hard (1300 点)

一目見て、データ構造げーかな...と思ってしまった。そういう先入観を持つと危ない。実際は好みな考察で解ける問題だった。 問題へのリンク 問題概要 正の整数 と からなる順列が与えられる。いま、この順列を下図左のようにピラミッドの最底辺に書き込む。…

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

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

AOJ 1602 ICPC 計算機 (ICPC 国内予選 2015 C)

こういうのをサッと書けるようになりたいね 問題へのリンク 問題概要 ((6 + 2) + 1) + (7 * 6) + 3 のような計算式が以下のような入力フォーマットで与えられる。これを構文解析して計算結果を出力せよ。 演算子は「+」「*」のみ 数値は 1 桁のみ 10 + .+ ..…

AOJ 0655 日本沈没 (JOI 2019 予選 D)

これまたちょっと重たい。。。 問題へのリンク 問題概要 折れ線グラフが与えられる。これは に対して () を結んでいる。あらゆる水平な直線を考えたときの、折れ線グラフのうち直線の上に来ている部分を連結成分ごとに分解したとき、連結成分の個数として考…

AtCoder AGC 029 D - Grid game (800 点)

これは。。。C より先に確実にこれをとったのはよかった 問題へのリンク 問題概要 (意訳) H × W の二次元グリッドがあって、各マスは通路か壁である。壁は N 個ある。最初は (1, 1) に駒がある。 毎ターン (x, y) にある駒は (x + 1, y) に進める、ここで (x…

AtCoder AGC 008 D - K-th K (800 点)

実装は手こずったものの、それなりに自信のある Greedy を提出できて一発 AC できてよかった 問題へのリンク 問題概要 1 〜 の値を 個ずつもつ長さ の数列であって、 各 について、 番目の値が 個目の である という条件を満たすものを 1 つ構築せよ。条件を…

AOJ 3045 Painting (ACPC 2018 day2 G)

コンテスト本番、つたじぇーが頑張って通してくれた!!! 問題へのリンク 問題概要 長さ の数列 が与えられる。初期状態では の要素は全て 0 である。加えて、 個の整数のペア()が与えられる。各ペアに対し以下の操作を行い、最終的な数列 を出力せよ。 各 …

技術室奥プログラミングコンテスト #2 E - 歩くNPCたち(Walking NPCs)

えーーーこれが平方分割的解法って天才すぎでは 問題へのリンク 問題概要 人が一直線上を、初期位置 、速度 で等速直線運動を行う。以下の 個のクエリに答えよ: 秒後に座標 から座標 までの間にいる人数を数えよ 制約 考えたこと が 以下と小さいことが大き…

AtCoder ABC 106 C - To Infinity (300 点)

十分多い回数重ねるとなにかが収束する系はよく見るん 問題へのリンク 問題概要 (ABC 106 C) 1 から 9 までの数字からなる文字列 S がある。以下の操作を 5000 兆回行う: 文字列 S に含まれるそれぞれの 2 が 22, 3 が 333, 4 が 4444, 5 が 55555, 6 が 666…

Codeforces Manthan Codefest 18 D - Valid BFS?

こういうの超苦手。。。解き方はわかるけど実装を工夫する感じの。 問題へのリンク 問題概要 N 頂点のツリー (頂点番号は 1, 2, ..., N) と、(1, 2, ...., N) の順列 a が与えられる。 このツリーを頂点 1 から出発して BFS したとして、その頂点訪問順序が …

AtCoder AGC 013 C - Ants on a Circle (700 点)

蟻さんぐるぐるなのん 問題へのリンク 問題概要 (AGC 013 C) 長さ の円周上を 匹の蟻が動く。どの蟻も 1 秒間に 1 だけ動く。互いに反対方向に動いている 2 匹の蟻がぶつかったら、互いに向きを反転させて動く。 匹の蟻は最初 の地点にいた。どの蟻が最初に…

AOJ 2589 North North West

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

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

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

AOJ 2353 Four Arithmetic Operations

この問題の既存の解説記事は中国剰余定理によるものが多かったので、それ以外の方法を示すのはいいかもなん。 AOJ 2353 Four Arithmetic Operations 問題概要 有理数列 がある。各項は以下のように定義される: ただし は +、-、×、÷ のいずれかである。 を…

CS Academy 082 DIV1 C - City Break

しゃくとり法とは違うけど、区間の左端と右端とのどちらかを伸ばしていく感じはしゃくとり法に近いかもなん CS Academy 082 DIV1 C - City Break 問題概要 円環状に 個の街がある。街 i と街 i+1 との間の距離が a[i] で与えられる (i = N のときは街 N と街…