しゃくとり法
面白かった！セグ木を使ったけど、区間を複数個にする必要がないことから、しゃくとり法で線形でできるね！ 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を繰り返すことで、単調増加となるようにしたい。 区間 の要素をすべて削除する (コスト…
ひょっとしたら難易度 5 との境界の問題だったかもしれない。lower_bound() を試すいい感じの例題。 ジャッジページへのリンク 問題文 editorial 問題概要 一周の長さが であるような周回コースがあって、コース上に 個の店舗がある。コース上の 1 点の座標…
区間分割していく DP を普通にやると になる (オレンジの出荷もそう)。それを累積和を用いて高速化する。 ジャッジページへのリンク 問題文へのリンク 類題とか drken1215.hatenablog.com 問題概要 (意訳) 個の正の整数 が与えられる。これらをいくつかの連…
平方分割で解法を分岐する系の問題で、そのうちの片方の問題は Easy Version として D1 で出題されてた (Easy Version は R2600) 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のみからなる 要素の数列 が与えられる。 数列の連続する区…
以前にしゃくとり法の記事で特集した問題のひとつだった！ 問題へのリンク editorial 問題概要 環状のバームクーヘンを 3 つに分けたい。 バームクーヘンは下図 (問題文から引用) のように 個のピースに分かれていて、それぞれのサイズは となっている。 バ…
最初 DP とか考えたくなるやつ。落ち着くと見えてくる。 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられる。ところで、レベル の JOI 文字列とは、"JJ...JOO...OII...I" (それぞれ 個…
まさかの超典型な半分全列挙！！！(蟻本にもほぼ同じ問題あり！！) 問題へのリンク 問題概要 個の正の整数 と、正の整数 が与えられる。 個の整数の中からいくつか選んで総和をとる。その値が より大きくならない範囲内での、その値の最大値を求めよ。 制約 …
簡単なバグを埋め込んでしまった... 問題へのリンク 問題概要 長さ の "0" と "1" のみからなる 2 つの文字列 が与えられる。 に対して以下の操作を繰り返し行うことで に一致させることができるかどうかを判定し、可能ならば最小回数を求めよ。 中の "01" …
しゃくとり法のいい練習問題！！ 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。 整数列の連続する部分列のうち、「同じ数値が 2 箇所以上登場しない」という条件を満たす最大長を求めよ。 制約 考えたこと 今回の問題には、次のような著しい構…
DP 高速化系問題 問題へのリンク 問題概要 のグリッドが与えられる。各マス には数値 が書かれている。 各行から 1 個ずつ数値を選んで行順に並べてできる数列を考える。そのような数列は 通り考えられるが、そのうち広義単調増加なものが何通りあるか、1000…
これかなりいい問題だと思う！！！ テスターをしていて、最初は 3 人じゃなくて 人だったけど、3 人にしたことでいい感じに 300 点問題になった！ 問題へのリンク 問題概要 人がいて、それぞれレーティングは となっている。 人の中から 3 人を選ぶ方法のう…
早速遅延セグ木があればできる問題来た！！ AC Library の出番かと思った！！！ 問題へのリンク 問題概要 縦 マス、横 マスのグリッドがあり、はじめグリッドの中央 マスには黒い石が 1 個ずつ置いてあり、下辺と右辺の計 マスには白い石が 1 個ずつ置いてあ…
いわゆる区間分割する系の DP。こういう系は高速化を要求するタイプの問題が多いけど、今回は素直な二乗 DP で OK！ 問題へのリンク 問題概要 直線上にカツが 個ある。 個目のカツは位置 にあり、その重さは である。これらのカツを、次のようにしてすべて回…
最初は、問題を見た瞬間に「にぶたんだ...」となったので、青 diff に驚いたのだった。でもいざ実装を始めると、頭壊れる問題ですね。。。^^; 問題へのリンク 問題概要 個の整数 が与えられる。これらから 2 つを選んで積をとって得られる 個の整数のうち、…
区間加算に対応したデータ構造の出番！ 問題へのリンク 問題概要 体のモンスターがいて、それぞれ座標 にいて、HP は である。すべてのモンスターを倒したい。 1 回の魔法で、座標 を指定して、[ ] の範囲内にいるモンスターの HP をすべて ずつ減少すること…
Deque に似てる。けど、Deque と違って、先手と後手がとりうる選択肢は常に一緒 (最初、先手は左から、後手は右からと誤読した)。 問題へのリンク 問題概要 長さ の数列に対し、先手は左から順に、後手は右から順にとっていく。どのターンもとった値の合計値…
差分更新系の代表的問題。でも頭がごっちゃになって大変だった。 問題へのリンク 問題概要 'D', 'M', 'C' からなる長さ の文字列 と正の整数 が与えられる。 の添字 であって S[ ] = 'D' S[ ] = 'M' S[ ] = 'C' を満たすものの個数を求めよ (というクエリに …
教育的ないい問題！！！！！ 問題へのリンク 問題概要 本の棒があって、それぞれ の長さをもっている。 このうちの 3 本を選ぶ方法であって、その 3 本で三角形が作れるものは何通あるか？ 制約 解法の overview ものすごく色んな解法が考えられる問題だと思…
超典型的なしゃくとり法そのものだった！！！ 問題へのリンク 問題概要 個の整数 があたえられる。数列の連続した区間であって、その総和が 以上となっているものを数え上げよ。 制約 考えたこと しゃくとり法については以前に記事を書いた。 qiita.com この…
これを解けなかったのが強い敗北感。 DP 配列が巨大になりそうなときに、最適化する対象を入れ替えるテクは今までなんども見ているのにそれが思いつかない思考の硬さを思い知らされた。 問題へのリンク 問題概要 0 と 1 のみからなる行列の複雑度を すべて同…
これ...以前 Twitter につぶやいた問題とよく似てた！！！ 400 点くらいの問題【問題】N 要素の 0 と 1 から成る数列が与えられる。以下の操作を最大 K 回行なって錬成し得る数列が何通りあるか 10e9 で割った余りを求めよ「数列の連続する区間を選んで 0 と…
しゃくとり法のいい感じの練習問題 問題へのリンク 問題概要 英小文字のみから成る文字列 が与えられる。 の連続する部分文字列のうち「同じアルファベットが2度以上使われることのない」ものが何個あるかを数えよ (空文字列は 1 個とみなす) 制約 考えたこ…
楽しいけど重くて、重いけど楽しい 問題へのリンク 問題概要 要素から成る数列 が与えられる。 個から 2 個選んでできる 通りのペア のうち、以下の条件を満たすものを数え上げよ。 容量が の容器を用意して、以下の操作によって水の量 を汲み取れる 操作 1:…
スライド最小値の練習 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 個のアイテムがって、それぞれ市場価値 と貴重度 が与えられる。 今、A さんと B さんがそれぞれアイテムのうちの何個かをとる。このとき、A さんと B さんは同じアイテム…
ができた。本番中に解き切りたかった 問題へのリンク 問題概要 個の整数 がある。整数 を 1 つ固定したとき、先手と後手は以下のようにしてゲームを進める: 先手は現在残っている整数のうち、最大のものを取って足す 後手は現在残っている整数のうち、 に最…
解き切りたかった 問題へのリンク 問題概要 オレンジが 個、みかんが 個ある。これを 人で分け合う ( が の倍数であることは保証される)。 それぞれの人 について、オレンジとみかんそれぞれ 1 個あたりの満足度が で与えられる。 うまく分けて、各人の満足…
かなり悩んだ 問題へのリンク 問題概要 (ARC 100 D / ABC 102 D) 長さ の整数列 を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を とするとき、 の最小値を求めよ。 制約 考えたこと こういうの、 連続する区間が 4 個だ…
treeone さん... 問題へのリンク 問題概要 0 と 1 からなる長さ N の文字列 S が与えられる。 どの連続する K 個の中にも 1 が 3 個以上含まれている という条件を満たすような最小の K を求めよ 制約 3 <= N <= 105 S の中に 1 は 3 個以上含まれる 解法 右…
こんなしゃくとり法もあるのんな。面白いん。 ABC 098 D Xor Sum 2 問題概要 長さ の正の整数列 が与えられる。整数列の連続する部分列のうち、「xor 和と加算和とが等しい」という条件を満たすものを数え上げよ。 制約 数値例 1) 答え: 5 (2), (2, 5), (5),…
しゃくとり法とは違うけど、区間の左端と右端とのどちらかを伸ばしていく感じはしゃくとり法に近いかもなん CS Academy 082 DIV1 C - City Break 問題概要 円環状に 個の街がある。街 i と街 i+1 との間の距離が a[i] で与えられる (i = N のときは街 N と街…
