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

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

ソートが必要になるところが少し難しいかもしれない。 問題へのリンク 問題概要 個の商品があって、それぞれ 円である。 またクーポンが 枚あって、1 枚のクーポンを使って次のことができる。 商品を 1 つ選ぶ その商品の価格を 円減少させる ただしもとの価…

すごい面白い！！ 問題へのリンク 問題概要 体の敵がいて、敵に付随するスコアはそれぞれ で与えられる (負数になることもある)。 これらの敵を順に倒していきたい。Boss Score, Total Score と呼ばれる値が初期状態ではともに 0 となる。敵 を倒すとき、次…

こういう数え上げ、大好きすぎる！！！ 問題へのリンク 問題概要 長さ の数列 がある。初期状態ではすべての値が 0 となっている。この数列に以下の操作をちょうど 回行って得られる数列が何通りあるか、998244353 で割ったあまりを求めよ。 となる を選んで…

こういう問題めっちゃ好き！！！ 問題へのリンク editorial 問題概要 '0' と '1' のみからなる長さ の文字列が与えられる。以下の操作を 回以上 回以下まで行うことができる。 i < j であって S[ i ] = '0'、S[ j ] = '1' であるような (i, j) を選ぶ S[ j ]…

一目二分探索ゲーだし、実際二分探索で解けるのだけど、実はもっとすごく楽に解ける！！ 問題へのリンク 問題概要 長さ の整数列 が与えられる。数列の退屈さとは「同じ値が連続している区間の長さの最大値」として定義する。 与えられた数列において、最大…

資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った！ 問題へのリンク 問題概要 個の正の整数 (総和を とする) が与えられたとき、 が最小値となる を満たすような非負整数の組 を求めよ。複数通り考えられ…

ちょっと場合分けが怖い問題だけど、最後の動きは「ちょうどゴールにならないと、上がれないすごろく」を思い出すと納得できそう！ 問題へのリンク 問題概要 現在、座標 にいる。以下のいずれかの操作をちょうど 回行う。 座標 にいるとき、 に移動する 座標…

異様に難しかった！！ 問題へのリンク 問題概要 の順列が与えられる。 順列の中の i から P[ i ] へ移動するとき、C[ P[ i ] ] だけスコアが加算される。 出発点を自由に選んで 回以上 回以下の移動を行うとき、得られるスコアの最大値を求めよ。 制約 考え…

実は、元の文字列の形はどうでもよくて、文字列の長さだけが重要という！！！ 問題へのリンク 問題概要 長さ の英子文字からなる文字列 が与えられる。これに以下の操作をちょうど 回行ってできる文字列が何通り考えられるか、1000000007 で割ったあまりを求…

ABC では数少ない発想力系。 問題へのリンク 問題概要 L と R から成る 文字の文字列 が与えられる。文字列のスコアは次のようにして決められる。 各 index i について S[ i ] = 'L' ならば、i + 1 >= 0 かつ S[ i - 1 ] = 'L' のときに限り、1 を加算 S[ i …

問題を読み替えつつ Greedy！！！ 問題へのリンク 問題概要 個の品物があって、それぞれ 円で売られている。今 枚の魔法の割引券があって、品物を買う際に割引券を好きな枚数使うことができる。 円の品物を買う際に 枚の割引券を使った場合、その品物を 円で…

こういう全探索が意外と出てこないという意見はよく聞くよね。 同時に「複数種類の操作を行える問題では、操作の流れを単純化する」という典型思考を試す問題でもある。 問題へのリンク 問題概要 あなたは誕生日プレゼントとして友人から dequeue D を貰いま…

混ぜてソートは賢すぎる！！！惚れた！！！ 問題へのリンク 問題概要 枚のカードにそれぞれ の数値が書かれている。あなたは、 について順に以下の操作を 1 回ずつ行います。 カードを 枚まで選ぶ(0 枚でもよい)。選んだカードに書かれている整数をそれぞれ …

こういう O(1) なペアリングを頑張る系の問題が本当に苦手。。。 問題へのリンク 問題概要 すぬけ君は最初、ビスケットを 1 枚持っており、日本円は持っていません。 すぬけ君は、以下の操作を好きな順に合計ちょうど K 回行います。 持っているビスケットを…

面白かった 問題へのリンク 問題概要 文字列 が与えられる。あらかじめ文字列の中の 文字を自由に変更することができる。 こうして得られた文字列と、それを反転した文字列の LCS (最長共通部分列) の長さとして考えられる最大値を求めよ。 制約 考えたこと …

問題概要 個の品物があって、それぞれ価格は である。ここから 個の品物を何回かに買いたい。ここで一回の買い物につき一回ずつ使えるクーポン券が 個あって (使わなくても良い)、各クーポンは ちょうど 個の品物を買ったならば、そのうちの安い順に 個の品…

難しくて、てんぷらたんが天才だった！！！！！！！ とにかくすごかった！！！！！ そしてすごく面白い問題だった！！！！！ 問題へのリンク 問題概要 長さ の数列 が与えられる。数列の 2 要素を選んで swap する操作を高々 回まで行うことができる。 操作…