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

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

シミュレーション:stackの活用

AtCoder ABC 359 E - Water Tank (1D, 水色, 500 点)

いかにも stack が登場しそうな問題! 問題へのリンク 問題概要 下の図のように、高さが の仕切りが等間隔に並んでいて、その間と両端の カ所のスペースを表す番号を とする。これらは幅が等しい。 今、スペース 0 に水を入れていく。1 個分のスペースについ…

AtCoder ABC 338 E - Chords (1Q, 緑色, 500 点)

弦が交わるかどうかを判定するという、スタックの典型問題! 問題へのリンク 問題概要 次の図のように、円周上に 個の点 があり、 本の弦がある(図は のとき)。 弦に交差があるかどうかを判定せよ。 制約 考えたこと この問題は stack で解けることで有名…

Donutsプロコンチャレンジ2015 C - 行列のできるドーナツ屋 (1Q)

スタックの応用問題! ヒストグラムの最大長方形を求めるアルゴリズムと似たようなスタックの使い方をする! 問題へのリンク 問題概要 長さ の数列 が与えられる。これらの値は互いに相異なる。 各 に対して、次の条件を満たす整数 の個数を求めよ。 なる任…

AtCoder ABC 333 E - Takahashi Quest (1Q, 緑色, 450 点)

これ結構難しくて、嵌まる人は嵌まってしまうと思う!! 問題へのリンク 問題概要 ダンジョンには、ポーション と、敵 がいる。 今、ダンジョンで 個のイベントが起こる。イベント は 2 つの整数 で表される。 のとき:ポーション が現れる それを拾うかどう…

AtCoder ABC 351 C - Merge the balls (4Q, 灰色, 250 点)

スタックのいい練習問題! 問題へのリンク 問題概要 空の列と 個のボールがある。 番目のボールの大きさは である。これから 回の操作を行う。 回目の操作では、 個目のボールを列の一番右に付け加えた後、次の手順を繰り返す。 列にあるボールが 1 つ以下な…

AtCoder ABC 243 D - Moves on Binary Tree (2Q, 茶色, 400 点)

まともに計算すると桁数がとんでもないことになるので、「LU で消す」「RU で消す」を活用しよう! 問題へのリンク 問題概要 頂点数が十分多い完全二分木が与えられる。根の番号は 1 であり、一般に頂点 の左子頂点の番号は 、右子頂点の番号は である。 最…

鉄則本 A51 - Stack (4Q, ★2)

人生で最初に解きたいスタックの問題 問題へのリンク 問題概要 以下の 3 種類のクエリ ( 個) を高速に処理するプログラムを実装せよ。 クエリタイプ 1: という題名の本を机の一番上に積む クエリタイプ 2:一番上に積まれている本の題名を答えよ クエリタイ…

鉄則本 B51 - Bracket (3Q, ★4)

スタックを用いて、かっこの対応をとる問題! 問題へのリンク 問題概要 対応のとれているカッコ列 が与えられる。対応する左かっこ '(' と右かっこ ')' が、それぞれ の何番目と何番目であるかを順に求めよ。 制約 メモ 詳しい解説はここにあるのでメモ程度…

JOI 二次予選 2022 A - 図書館 2 (AOJ 0719) (4Q, 難易度 2)

スタックを用いたシミュレーション問題! 問題へのリンク 問題概要 最初、本は積まれていない。次の 回のクエリに答えよ 【クエリ】 各クエリでは文字列 が与えられる。 が "READ" ではないとき、タイトルが である本が新たに上に積まれる が "READ" である…

AtCoder ABC 372 D - Buildings (1Q, 緑色, 400 点)

この手のスタックの問題はもうすっかり常識と化した! 問題へのリンク 問題概要 ビル がこの順に並んでいる。ビル の高さは である。 各 に対して、ビル の間にビル より高いものがないような () の個数を求めよ。 制約 考えたこと いかにもスタックを使いそ…

AtCoder ABC 043 B - バイナリハックイージー (6Q, 茶色, 200 点)

制約が小さいのでなんとでもなる。C++ なら文字列の末尾を削除する関数 pop_back() を知っていると楽だと思われる。 問題へのリンク 問題概要 エディター上で、'0'、'1'、'B' という 3 種のタイピング入力を行う。 '0' と打つと、エディターに表示された文字…