優先度付きキューを人生で初めて試すのにいい問題。 問題へのリンク 問題概要 以下の 3 種類のクエリ ( 個) を高速に処理するプログラムを実装せよ。販売システムを模している。 クエリタイプ 1：価格が 円の商品が追加される クエリタイプ 2：今ある商品の…

キューの使い方の確認！ 問題へのリンク 問題概要 以下の 3 種類のクエリ ( 個) を高速に処理するプログラムを実装せよ。行列管理システムを模している。 クエリタイプ 1：行列の最後尾に さんが並ぶ クエリタイプ 2：行列の先頭にいる人の名前を答える クエ…

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

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

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

「いくつかの値を決めると、残りが決まっていくので、最後に整合性を check する」というのは、頻出の典型テクニック！ 問題へのリンク 問題概要 円環状に動物 がこの順に並んでいる。各動物は羊 ('S') か狼 ('W') である。ただし、各動物がいずれであるかが…

この時代多く見られた「グルーピング」の問題！ 問題へのリンク 問題概要 S 型ピース 1 個と c 型ピース 2 個を使って、下図のように Scc を 1 個作ることができる。 また、c 型ピース 2 個を使って S 型ピース 1 個を作ることもできる。 今、S 型ピースが …

mod を練習できる問題！ 問題へのリンク 問題概要 正の整数 が与えられる。 を 1000000007 で割った余りを求めよ。 考えたこと まず「1000000007 で割った余り」といったものを考えるための、基本的な知見を次の記事にまとめた。 qiita.com 結論として、 を …

少し実装が重たい全探索問題！ 問題へのリンク 問題概要 の白黒グリッド と、 の白黒グリッド が与えられる ()。 グリッド のパターンがグリッド の中に含まれるかどうかを判定せよ。 制約 考えたこと グリッド のすべてのマス について、次の判定をしていけ…

が小さいことがいかにも怪しかったので、グラフを小さくすることを考えた。 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフがある。 辺 () は、頂点 から頂点 を結ぶ ( は 0 とする) 辺 () は、頂点 から頂点 を結ぶ このグラフ上の、頂点 0 を始点と…

Union-Find を上手に使おう！ 問題へのリンク 問題概要 初期状態では頂点数 、辺数 0 のグラフがある。頂点番号は である。次の 回のクエリに答えよ。 クエリタイプ 1：頂点 間に辺を張る クエリタイプ 2：頂点 を含む連結成分に含まれる頂点の番号にうち、 …

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

差分のみ更新していく系の典型問題 問題へのリンク 問題概要 長さ の文字列 が与えられる。次の 回のクエリに答えよ。 【クエリ】 整数 と文字 が与えられるので、 を に変更する。その後の文字列 の中に、"ABC" が何個含まれるかを答えよ。 制約 考えたこと…