最適化テク：変形しても悪化しない
辞書順最小と言われたら......！！ 問題へのリンク 問題概要 文字 'd', 'p' からなる長さ の文字列 が与えられる。 この文字列のある区間をとって、その区間を 180 度回転させる（reverse した上で、'd' と 'p' を入れ替える）。 こうしてできる文字列のうち…
Euler Tour して、遅延評価セグ木（区間加算 + 区間 min）に乗せて......という解法を考えていたところに、あまりにもシンプルな想定解法を目にして、感動した！ 問題へのリンク 問題概要 頂点数 の重み付き木が与えられる。 に対して、次の問に答えよ。 個…
実はとても単純な解法に落とし込めるのだけど、発想がちょっと難しい 問題へのリンク 問題概要 AtCoder 王国の 1 週間は 日あり、最初の 日が休日、後半の 日が平日である。 高橋君は 日分の予定があり、それぞれ 日目に予定がある。 これらの予定日がすべて…
「実は各点から左右に見て最も近い点だけ見れば良い」という点気考察をする！ 問題へのリンク 問題概要 数直線上に 個の絵がある。 番目の絵のある位置の座標は であり、'J', 'O', 'I', 'G' のいずれかの文字 が書かれている。 これらの絵に対して、以下の …
すごく面白い問題！ いろんな嘘解法がありそうで怖い。 問題へのリンク 問題概要 長さ の数列 が与えられる。今、数列の 1 つの要素の値を自在に書き換えることができる。 操作後の数列の LIS の長さを求めよ。 制約 考えたこと この手の問題では、まずは操…
昔ながらの典型考察 Greedy 問題。 問題へのリンク 問題概要 本の刀がある。 刀 を振ると、敵に だけダメージを与える。何度でも振ることができる 刀 を投げると、敵に だけダメージを与える。刀 を失うので、もう投げることも振ることもできなくなる 敵に …
JOI ではお馴染みの「 個の区間を扱う問題」。ただし実装がしんどかった。僕は区間を set で管理する方法で実装した。 問題へのリンク editorials 問題概要 制約 考えたこと いかにも貪欲法の香りが漂っている問題ですね。この手の問題では、 個の区間を終端…
面白かった！ 問題へのリンク 問題概要 個の正の整数 を 個のグループに分ける。ただし、どのグループの要素数も 1 個以上 2 個以下でなければならない。 最適なグループ分けをしたときの、各グループの要素の総和の二乗の総和の最小値を求めよ。 制約 考え…
ちゃんと証明しないと、なかなか安心して提出できない系 問題へのリンク 問題概要 整数列 が与えられる。次の操作を繰り返し行って、 の最大値と最小値の差が 1 以下となるようにしたい。実現のための操作の最小回数を求めよ。 を選んで、 に 1 を足し、 か…
D 問題の MaxFlow に続いて、これまた、人生で一度は解くべき超典型問題ですね。そして、D 問題とは違うやり方で、二部グラフを作ることにも注目です！ 問題へのリンク 問題概要 のグリッドがあり、各マスには数値が書かれています。 これらのマスからいくつ…
いわゆる「木上の最大安定集合問題」です！ 超典型問題です。 問題へのリンク 問題概要 頂点数 の木が与えられます。木からいくつかの頂点を選んで削除します。その結果、木はいくつかの連結成分に分かれます。 分かれた連結成分の個数の最大値を求めてくだ…
古き良き全探索問題！！ 問題へのリンク 問題概要 二次元平面上に 個の点があります。 番目の点の座標を とします。 この二次元平面上で各辺が X 軸・Y 軸に平行であるような長方形であって、 個の点のうち 個以上の点を内部および周に含むようなものを考え…
面白かった！セグ木を使ったけど、区間を複数個にする必要がないことから、しゃくとり法で線形でできるね！ 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を繰り返すことで、単調増加となるようにしたい。 区間 の要素をすべて削除する (コスト…
これは難しい！！！ 誘惑されそうな嘘解法がたくさんある！！ 問題へのリンク 問題概要 件の日雇いアルバイトがあります。 件目の日雇いアルバイトを請けて働くと、その 日後に報酬 が得られます。 あなたは、これらの中から 1 日に 1 件まで選んで請け、働…
難易度 8 でもおかしくないと思った。 B や C より易しい気がしなくもないけど、本番の緊張感で B や C を飛ばして D を本気で考える決断はなかなかできなさそう。今回は B - パンケーキを見て冷静になれたか勝負だね... 問題へのリンク 問題概要 個の工場が…
実は双対性が深く絡んでるけど、割と素直な Greedy でも解ける 問題へのリンク 問題概要 要素からなる整数列 が与えられる。これらの要素をいくつかの色に塗り分けたい。ただし、同じ色で塗られた要素は狭義単調増加になるようにしなければならない。 このよ…
dp の値そのものを用いて現在状態を復元する系の問題。 問題へのリンク editorial 問題概要 個の木 があって、それぞれ高さは である。 フクロモモンガは最初は、木 1 の高さ の地点にいる。フクロモモンガは木を飛び移りながさ、最終的に木 の頂上にたどり…
|x-a| + |x-b| + ... + |x-z| を最小にする x が a, b, ..., z のメディアンになる話は有名で、それを拡張すると仕組みがわかった！ 問題へのリンク editorial 問題概要 体のスライムがいて、それぞれの強さは となっている。以下の操作を行うことができる …
平方分割で解法を分岐する系の問題で、そのうちの片方の問題は Easy Version として D1 で出題されてた (Easy Version は R2600) 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のみからなる 要素の数列 が与えられる。 数列の連続する区…
Greedy を考察して、さらに左右から累積和を求める！結構難しい！ 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 長さ の数列 と、長さ の数列 が与えられます。各 に対して、次の値を求めよ。 数列 から を除去してできる長さ の数…
簡単なバグを埋め込んでしまった... 問題へのリンク 問題概要 長さ の "0" と "1" のみからなる 2 つの文字列 が与えられる。 に対して以下の操作を繰り返し行うことで に一致させることができるかどうかを判定し、可能ならば最小回数を求めよ。 中の "01" …
から落とせる気がまったくしなかった... 問題へのリンク 問題概要 個の広義単調増加数列 が与えられる。 それぞれの数列から、先頭から 個ずつとってきた値の総和の最大値を求めよ。ただし でなければならないものとする。 制約 考えたこと 個数に関する con…
頭整理が大変だけど、考え方はわかる。 問題へのリンク 問題概要 は正の奇数である。 個の整数 が与えられる。以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる 個の整数 を 2 個ずつペアにして 組のペアを作る それぞれのペアの「数値の差」の総…
愚直にやると 本の辺がある問題に対して、上手にやる系の問題 問題へのリンク 問題概要 グリッドグラフがある。 広義単調増加な正整数列 があり、それぞれの長さは となっている。 頂点 と頂点 は、重みが である無向辺で結ばれている 頂点 と頂点 は、重み…
めちゃ好きだけど、実装重い 問題へのリンク 問題概要 頂点の重み付き無向完全グラフが与えられる。各 に対して、 頂点集合を 個の互いに disjoint な集合に分割する方法であって どの同族辺 (両端点が同一のグループに属する辺) の重みも、どの異族辺 (両端…
探索順序を上手に決めると、普通の DP になる系！！！ EDPC の Zubton なんかもそうやね！ 問題へのリンク 問題概要 個の正の整数 が与えられる。これらを並び替える。並び替えのスコアは以下のようにして決まる。 各 に対して、 の index が に移動するとき…
丁寧に簡潔に 問題へのリンク 問題概要 合計で グラム買いたい。 0.25 グラフで 円のセット 0.5 グラムで 円のセット 1 グラムで 円のセット 2 グラムで 円のセット がある。これらのセットを組み合わせて グラム買うための最小金額を求めよ。 考えたこと 0.…
DP 復元非本質＞＜ 問題へのリンク 問題概要 人のコンテスタントを 3 人以上を 1 チームとしたいくつかのチームに分割したい。コンテスタント のスキルは である。 チーム分けの良さを、各チームごとの「メンバーのスキルの最大値と最小値の差」の合計値とす…
ABC 151 F 以来の幾何ですね。ABC 151 F の解法のうち「探索候補として交点を考える」というのが今回もいい感じに使える！ drken1215.hatenablog.com 問題へのリンク 問題概要 二次元平面上に 個の点 が与えられる。それぞれの点に肉が置いてある。このうち…
最適解の形を丁寧に場合分けして考える系 問題へのリンク 問題概要 の板チョコレートを 3 つの長方形に割りたい。そのときの 3 つの長方形の面積の最大値と最小値の差の最小値を求めよ。 制約 考えたこと まず思ったのは、 のうちの少なくとも一方が 3 の倍…
