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

スタックを用いると楽に構文解析できる！ 問題へのリンク 問題概要 +(1,+(+(2,3)),+(4,+(5))) のような形式の入力を (1+((2+3))+(4+(5))) のように変換せよ (詳しくは問題文参照)。 制約 考えたこと スタックを用いて「演算子」を格納しておく。 ',' が来た…

木上で bit DP する感じ 問題へのリンク 問題概要 頂点数 の根付き木が与えられる。各頂点 には重み が付されている。 この根付き木はタスクの依存関係を表している。各頂点に対して、対応するタスクの「実行」と「削除」ができる。 頂点 のタスクを実行する…

分割数のいい感じの問題！ 問題へのリンク 問題概要 長さ の数列 killA, killB が与えられる。この 2 つの広義単調減少である。 次の条件を満たす長さ の数列 deathA, deathB の組の個数を 1000000007 で割ったあまりを求めよ。 killA の総和 = deathB の総…

重心分解！ 問題へのリンク 問題概要 (インタラクティブ) 頂点の木が与えられる。なお、この木はどの頂点の次数も 以下であることが保証されている。 A さんは、この木のいずれかの頂点 を考えている。その頂点 を当てるゲームを行う。 あなたは最大 14 回の…

久しぶりに bit ベクター高速化を使った。デバッグがしんどかった。 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。今、次の操作をちょうど 回実行する と を選ぶ と とを swap する 操作実行後の の値の最大値を求めよ。 制約 考えた…

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

とても面白かった。文字列に操作を 回施して、操作後の文字列の辞書順最小のものを求める問題。Suffix Array のよい練習問題でもある。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。この文字列に対して、以下のいずれかの作業…

面白かった 問題へのリンク 問題概要 要素からなる正の整数列 が与えられる。以下の 個のクエリに答えよ 各クエリは整数 が与えられる の順に、 という更新を行う 初めて となる瞬間の を求めよ 最終結果が 1 より大きいときは、その値を答えよ 制約 解法 (1…

操作を言い換えるところは楽しいけど、BinaryTrie が必要ということで、必死に整備した。 問題へのリンク 問題概要 要素の非負整数列 が与えられる。以下の操作を好きな回数だけ行える。行なった結果得られる数列のうち、辞書順最小のものを求めよ。 index …

面白かったけど、実際に実装するのは辛かった。 問題へのリンク 問題概要 のグリッドが与えられる。各マスを 2 または 5 で埋めたい。ただし以下の条件を満たすようにしたい。 2 が書かれたマスだけに着目し、上下左右斜め に隣接するマス同士に辺を張ったグ…

「二部グラフの最大安定集合問題」について知っていれば典型問題ですね。 問題へのリンク 問題概要 のグリッドがあります。各マスは白黒に塗られています。今、白いマスにできるだけ多くのコマを置きたいものとします。 各マスに 1 個のみコマを置ける コマ…

頑張った 問題概要 個の文字列が与えられて そのうちの指定された 個についてについては、その prefix となっている 指定されていない 個については prefix にはなっていない ような最短の文字列を求めよ。存在しない場合は -1 とせよ。 制約 個の文字列の長…

区間分割系問題 問題へのリンク 問題概要 文字列が与えられる。文字列を最小個数の連続区間に分割して、各区間の先頭文字がその区間内の他の任意の文字よりも辞書順で小さくなるようにせよ。 考えたこと Greedy に区間を分割していけば OK。 区間を分割して…

さ、300 点！？ 問題へのリンク 問題概要 個の中からランダムに選ぶ試行を 回行う。それぞれのものが出た回数が 回になる確率を としたとき、 を満たすような最小の を求めよ。 制約 考えたこと 確率を求めること自体は難しくなくて、 で求められる。が、こ…

300 点！？？？ 問題へのリンク 問題概要 '0' 〜 '9' および '?' からなる文字列 S が与えられる。 文字列のニコニコレベルとは、連続部分列であって "2525... 25" となっているものの最長の長さとして定義される。 S の '?' に '0' 〜 '9' を当てはめる方法…

今なら解ける！！！ 問題へのリンク 問題概要 人を何チームかに分けたい (チーム同士は区別しない)。 人目の人は 人以下のチームに入るようにする必要がある。そのようなチームの分け方は何通りあるか、 で割ったあまりを求めよ。 制約 考えたこと もし無制…

各地点に早くたどり着いておくに越したこと無い系問題！！ atcoder.jp 問題概要 のグリッドがあってスタートからゴールへと行きたい。壁のあるマスは通れない。 ただし毎秒ごとに移動できる方向に制限がある。 で割ったあまりがそれぞれの場合についてどの方…

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

ここでは行列の掃き出し法で殴ってみる 問題へのリンク 問題概要 個の正の整数 が与えられる。これらのうち 個以上選んで、その XOR 和が となるようにしたい。そのような選び方が何通りあるか、1000000007 で割った余りを求めよ。 制約 考えたこと 実は本番…

きれい 問題へのリンク 問題概要 枚のコインがあります。高橋君と青木君は、以下の操作を高橋君から始めて交互に繰り返します。 0 以上の整数 を選び、コインを 枚取り除く。 先に操作を行えなくなった者の負けです。両者が最適に行動するとき、どちらが勝つ…

比較的普通の問題っぽい 問題へのリンク 問題概要 文字列 が与えられる。 に含まれる文字をそれぞれ一度ずつ使い、何個かの回文を作ることを考えます。文字は自由な順序で使用することができ、 に複数回現れる文字は合計でその回数だけ使用します。 長さ の…

一発芸問題 問題へのリンク 問題概要 整数 に対し、 のとき それ以外で のとき それ以外で が偶数のとき それ以外で が奇数のとき で定義される。 整数 が与えられます。となるような 以下の正整数 をいずれか 1 つ出力してください。 ただし、 であることが…

積分した 問題へのリンク 問題概要 サイズ の長方形の紙と、それよりサイズの小さいサイズ の長方形の紙が 2 枚あります。 2 枚の小さいサイズの紙を、それぞれ、大きいサイズの紙の中に包含される範囲内でランダムに配置します (その位置は連続量)。 このと…

700 点は絶対落とさないようにしたい！！！ 本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。 問題へのリンク 問題概要 長さ の区間があ…

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

こういうのを爆速で書けるようになりたい。問題としては マンハッタン距離に関する問題では x 軸方向と y 軸方向とで独立に考えればよいことになるケースが多い (マンハッタンに限らず、各要素ごとに独立にならないかを考察することは重要) の最小値を与える…

累積和の練習 問題へのリンク 問題概要 個の整数 が与えられる。 各 に対して、数列の 個の連続する区間の値の和の最大値を求めよ。 制約 考えたこと 愚直にやると計算量は の値が 通り考える必要があって 各 に対して 個の区間があって 各区間に対して 個の…

解説は三進法でやってたけど、二進法でもできた 問題へのリンク 問題概要 次をすべて満たすようなマス目を構成せよ。 マス目の各マスは白か黒で塗られている マス目の縦横の長さをそれぞれ N,M としたとき、N,M は 1 以上 100 以下である 一番左上のマスから…

少し重たい 問題へのリンク 問題概要 長さ の整数列 が与えられます。 この数列に以下の操作をちょうど 回施します。 添字 を一つ選んで、 を 2 で割る (小数点以下切り捨て) 回の操作のあとの数列としてありうるものの個数を 109+7 で割ったあまりを求めよ…