「競プロ典型 90 問 001 - Yokan Party」とよく似た問題！ 問題へのリンク editorial 前提知識 基本的な二分探索 問題概要 枚の絵が一直線上に順に並んでいます。 枚目の絵は座標 の位置にあり、その価値は です。 今これらの絵から 枚の絵を選びます。この…

「最小値の最大化」 (or 「最大値の最小化」) には二分探索が有効という典型ですね。 類題とか (二分探索以外の問題も含むことと、ハイレベルな問題も多いことに注意) drken1215.hatenablog.com 問題へのリンク 解説へのリンク 問題概要 長さ のようかんがあ…

自明な上界を達成できるパターンだった！ 問題へのリンク 問題概要 長さ の非負整数列 が与えられる。この数列はどの隣接する二項も値が異なる。 この数列をなるべく多くの 項の非負整数列へと分解せよ。分解とは 分解された各非負整数列の各項を足すと、も…

カッコ列系の問題！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。文字列に対して、以下の処理を繰り返し行う。操作の結果得られる文字列の長さの最小値を求めよ。 文字列中の "fox" を削除する 制約 考えたこと カッコ列でよく似た問題はすごく有…

めちゃくちゃ面白かった 問題へのリンク 問題概要 この問題では、"(", ")", "[", "]" からなる文字列を考える。 文字列 は，以下のいずれかの条件を満たすとき、良い括弧列と呼ぶ。 は空文字列である ある良い括弧列 が存在し、"(", , ")" をこの順に連結す…

面白い。けど問題文長い...。問題概要を短くまとめてみた。 問題へのリンク 問題概要 正の整数 が与えられる。 あなたは、 以上の整数を 個用意する ( とする)。この 個の整数のスコアを、以下の条件を満たす最小の整数 として定める。 は のいずれでも割り…

この手の、単純だけど for 文ネストがエグい全探索、案外 AtCoder で見ないかもしれない 問題へのリンク 問題概要 の二次元グリッドが与えられる。各グリッドには 0 以上 9 以下の整数値が書かれている。 グリッド上で、以下の条件を満たす長方形領域を考え…

DP の添字を mod をとった値にするテクニック 問題へのリンク 問題概要 個の正の整数 が与えられる。これらの中からいくつか選びたい。選んだ整数のスコアを以下で定める。 整数の総和を として + % スコアの最大値を求めよ。 制約 考えたこと そもそも「整…

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

探索順序を上手に決めると、普通の DP になる系！！！ EDPC の Zubton なんかもそうやね！ 問題へのリンク 問題概要 個の正の整数 が与えられる。これらを並び替える。並び替えのスコアは以下のようにして決まる。 各 に対して、 の index が に移動するとき…

面白かった！！！こういうのを確実に通せるようにならないと！！！ 問題へのリンク 問題概要 頂点の木が与えられる。木の各辺を のラベルをつける方法のうち、 の値の最大値を求めよ。ただし は、2 頂点 を結ぶパスに含まれる辺の値の集合を考えたときに、そ…

すごく面白かった！！！ 問題へのリンク 問題概要 長さ の数列 が与えられる。ここから何個か選ぶ。選んだ値を としたとき、そのスコアを以下のように定義する。 選んだ値のメディアンを とする 奇数個の場合は真ん中の値 偶数個の場合は真ん中の 2 つの値の…

ジャンプの過程を無視して、最終的に出来上がるものがどうなるかを考えて、それをわかりやすく特徴づける 調和級数になるタイプの全探索 というタイプの問題。結構重たい。AGC なら C 問題でありそう。 問題へのリンク 問題概要 個の地点 にそれぞれ のスコ…

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

学び多き問題。 僕にとっては後半のデータ構造パートが苦戦を強いられ、本当に勉強になった！ 問題へのリンク 問題概要 個の寿司があって、それぞれネタ と美味しさ をもっている。この中から 個の寿司を選びたい。選んだ寿司集合のスコアは 選んだ寿司の美…

部分文字列の遷移は愚直に求めた。。。 問題へのリンク 問題概要 長さ の文字列 c と、短い文字列 s, t が与えられ、'a'〜'z' と '?' からなっている。'?' を埋める方法のうち、 c の連続する部分文字列として s を含む箇所の個数から c の連続する部分文字…

操作をいい感じに言い換える感じ 問題へのリンク 問題概要 個の要素 が与えられる。これに対し、以下の操作を好きなだけ行える。 隣り合う 2 要素をともに -1 倍する 操作後の数列の値の和として考えられる最大値を求めよ。 制約 考えたこと こういう「操作…

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

これ...以前 Twitter につぶやいた問題とよく似てた！！！ 400 点くらいの問題【問題】N 要素の 0 と 1 から成る数列が与えられる。以下の操作を最大 K 回行なって錬成し得る数列が何通りあるか 10e9 で割った余りを求めよ「数列の連続する区間を選んで 0 と…

楽しかった 問題へのリンク 問題概要 個のアイテムがあって、それぞれ時間 と美しさ の属性がある。今、 個の中から 個選びたい。選んだアイテムたちのスコアは (選んだアイテムの時間の総和) × (選んだアイテムの美しさの最小値) で決まる。このスコアの最…

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

操作を逆順に見るとよいという、すごく良い例題！大好き！！！ 問題へのリンク 問題概要 要素からなる数列 が与えられる。今、以下の操作を好きな回数だけ行う。 長さが の区間を選んで、区間全体を白く塗るか、黒く塗る 操作を行った後に黒く塗られたマスの…

好き 問題へのリンク 問題概要 正の整数 が与えられる。 を満たすような 個の正の整数 の組合せをすべて考えたとき、 の最大公約数として考えられる最大値を求めよ。 考えたこと を素因数分解して、各素因子たちを に振り分けることを考える。 このとき、各…

最初は「一度選んだマスを使えない」を完全に呼び飛ばしてしまった上に、それに気づいた後も「奇数マス同士をマッチングして、うまく経路を設定する」という方向の考察をしまくって、上手くいかずに迷走した... 問題へのリンク 問題概要 (ABC 109 D) 縦 行、…

本番では回避したん。こういうのをサッサササッとバババババーンと解けるようになりたいん。 問題へのリンク 問題概要 個の数列 が与えられる。以下の操作を好きな回数だけ行って得られる数列の総和を最大化せよ。 連続する 個の区間の数列を一斉に 0 にする…