けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

最小コスト

Codeforces Grakn Forces 2020 E. Avoid Rainbow Cycles (R2400)

むずかしい 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。これらはある操作のコストを決めるためのパラメータである。 さらに、 系列の数列が与えられる。 番目の数列の項数は で与えられる 数列の各項 は 以上 以下の値である 今、…

AOJ 3178 Katsusando (HUPC 2020 day3-G)

いわゆる区間分割する系の DP。こういう系は高速化を要求するタイプの問題が多いけど、今回は素直な二乗 DP で OK! 問題へのリンク 問題概要 直線上にカツが 個ある。 個目のカツは位置 にあり、その重さは である。これらのカツを、次のようにしてすべて回…

AtCoder ABC 175 F - Making Palindrome (橙色, 600 点)

こういう重たい実装を確実にこなせるように...なりたい! 問題へのリンク 問題概要 個の文字列 が与えられる。これらを好きな順序で好きな回数だけ concat して回文を作りたい。ただし 番目の文字列を使用するコストは 1 回あたり である。 回文を作れるかど…

AtCoder AGC 004 B - Colorful Slimes (青色, 400 点)

実装を柔軟にしたい 問題へのリンク 問題概要 体のスライムがあって、初期状態では、それぞれの色は となっている。以下の操作を繰り返すことで全てスライムを消滅させたい。そのために必要なコストの最小値を求めよ。 色 のスライムを消滅させる (コストは …

AtCoder AGC 043 A - Range Flip Find Route (緑色, 400 点)

「予め盤面をいじることができる」という設定の問題にはある程度の定石があるように思う! 問題へのリンク 問題概要 の盤面が与えられ、左上から右下まで行きたい。'#' マスは壁を表し、'.' マスは通路を表す。 予め盤面に以下の操作を行うことができる。最…

AtCoder Petrozavodsk Contest 001 D - Forest (青色, 600 点)

面白かった 問題へのリンク 問題概要 頂点 辺の森が与えられる。各頂点 には、値 が付いている。これにいくつかの辺を追加して、連結にしたい。 頂点 と頂点 とを結ぶのに必要なコストは である すでに辺がある二頂点間は結べない 一度辺を張るのに使用した…

Educational Codeforces Round 83 G. Autocompletion (R2600)

頑張って DFS だけで通した!!! 問題へのリンク 問題概要 頂点数 の Trie 木と、そのうちの 個の頂点集合 が与えられる。 の各頂点 について、トライ木の根から出発して、以下の操作によって到達するまでの最小コストを求めよ。 トライ木の辺を 1 本先に進…

Codeforces Round #626 (Div. 1) A. Unusual Competitions (R1300)

また 1 つ、カッコ列に関する問題が誕生した 問題へのリンク 問題概要 長さ のカッコ列が与えられる。カッコ列に以下の操作を好きな順序で好きな回数だけ施して「整合が取れた状態」にしたい。 カッコ列のある区間について、任意の順序に並び替える このとき…

AOJ 2581 完全順列 / Derangement (RUPC 2014 day3-G)

今の RUPC / AUPC の先駆けとなった合宿の北大セットの問題!!! このセットは、全問題のタイトルの頭文字が 'D' というセットだった セットへのリンク 北大アーカイブへのリンク 問題へのリンク 問題概要 長さ の順列 が与えらえる。これらを並び替えて完…

Educational Codeforces Round 81 E. Permutation Separation (R2200)

これを思い出して迷走してしまった (それでも通る解法には至ったけど恐ろしく煩雑なものとなってしまった)。 drken1215.hatenablog.com なぜもっとシンプルに考えられなかったのか... 問題へのリンク 問題概要 の順列 と、各要素 を動かすのに必要なコスト …

AtCoder ARC 074 F - Lotus Leaves (黄色, 800 点)

見るからに最小カットだけど、こういうの意外と詰め切るのに時間がかかるイメージがある... 問題へのリンク 問題概要 の二次元グリッドが与えられる。各マスは 'S' のマス:カエルがいる 'T' のマス:カエルがそこにいきたい 'o' のマス:葉っぱがある '.' …

CODE FESTIVAL 2016 qual C D - Friction (黄色, 800 点)

気持ち良く詰められた 問題へのリンク 問題概要 のオブジェに対し いずれかの列を選び、その列を一段沈める (このとき最下段ブロックは消える) という操作を 回繰り返してオブジェを完全に消し去りたい。1 回の操作に要するコストは、そのブロックがその時点…

AOJ 3034 Explosion (RUPC 2018 day2-I)

最小包含円シリーズ!!! 問題へのリンク 問題概要 二次元平面上に 個の点がある。これを 個の円ですべて覆うようにしたいです。 これを実現できるような 個の円の半径の最大値として考えられる最小値を求めよ。 制約 考えたこと まず要素技術として、 通り…

yukicoder No.968 引き算をして門松列(その3)

その 2 と雰囲気は似ているけど、一気に考えづらくなった! 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっている 以下のクエリに 回答…

yukicoder No.967 引き算をして門松列(その2)

ものすごく間違いやすい雰囲気だったので、探索候補を絞ってから力技で全探索した!!! 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっ…

AtCoder ABC 150 E - Change a Little Bit (青色, 500 点)

面白かった 問題へのリンク 問題概要 長さ の整数列 が与えられる。 長さ の 0 と 1 からなる文字列 に対して定まる関数 は次のようになっている。 は、次のようにして文字列 を文字列 に一致させるのに必要な最小コストとする。 回目の操作で、 の文字 を選…

AtCoder ABC 148 D - Brick Break (灰色, 400 点)

とても教育的な Greedy かもしれない! 問題へのリンク 問題概要 長さ の正の整数からなる数列 が与えられる。この数列からいくつかの値を取り除くことで、数列が となるようにしたい。 取り除くべき個数の最小値を求めよ。どのように取り除いても の形にで…

AtCoder ABC 142 E - Get Everything (水色, 500 点)

個人的には bitDP は「順列を全探索するもの」というイメージがあるけど、今回はそれとはまた違う bitDP という感じ! 問題へのリンク 問題概要 個の宝箱がある。宝箱を開けるための鍵が 個あって、それぞれの鍵はいくつかの宝箱に対応している。鍵 を用いる…

AtCoder ABC 132 E - Hopscotch Addict (青色, 500 点)

グラフの頂点を倍加するタイプの問題ですね。 問題へのリンク 問題概要 頂点 辺の有向グラフが与えらえます。頂点 から頂点 へと、けんけんぱで移動したいものとします。 1 回のけんけんぱでは、「自分の今いる頂点から出ている辺を 1 つ選んで、その辺が接…

Codeforces 500 DIV1 B. Chemical table (R1900)

確かに、ついこの間の ABC 131 F の類題だね 問題へのリンク 問題概要 のグリッドがあって、 マス分が黒く塗られている 長方形の三頂点状に並んだ黒マスの組を選んで、残りの頂点に相当する位置を黒く塗る (コスト 0) 黒くないマスを一つ選んで黒く塗る (コ…

AtCoder AGC 003 C - BBuBBBlesort! (水色, 600 点)

楽しかった 問題へのリンク 問題概要 長さ の数列 が与えられる。どの 2 要素も互いに相異なることが保証される。これに対し 隣り合う 2 要素を swap する 連続する 3 要素を反転する という操作を行ってソートしたい。ただし、1 の使用回数を最小にしたい。…

AtCoder AGC 032 D - Rotation Sort (橙色, 1000 点)

本番フローで無理矢理解いた!!! でも DP が本筋だね。 問題へのリンク 問題概要 の順列 が与えらえる。これを 整数 を選んで区間 [ ) を左シフトする、すなわち をそれぞれ へ置き換える、これにコスト がかかる 整数 を選んで区間 [ ) を右シフトする、…

Codeforces 552 DIV3 F. Shovels Shop (R2300)

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

AtCoder ABC 006 D - トランプ挿入ソート (試験管青色)

順列において、要素をどこかに挿入する系の操作をする問題は典型ではある。こういうのをしっかり押さえたい。 問題へのリンク 問題概要 の順列が与えられる。 以下の操作を繰り返してソートされた状態にしたい。最小回数を求めよ。 要素を 1 つ選んで、任意…

AtCoder ABC 124 C - Coloring Colorfully (灰色, 300 点)

一見複雑だけど、実質 2 通りしかないというやつ 問題へのリンク 問題概要 長さが の 0-1 列が与えられる。何個かについて 0 と 1 を入れ替えることで、 0 と 1 が交互に並んでいる状態 にしたい。そのようなことが可能な方法のうち、入れ替える数字の個数の…

AOJ 3055 こたつがめを燃やさないで (RUPC 2019 day2-E)

こういうの超苦手系だけど、苦手なりに解法を詰められたのは成長の証で嬉しい! olphe さん、ナンさんとチームを組んでいて、olphe さんに考察を話して、詰めてくれて、爆弾周りの見落としがあって詰まって、みんなでデバッグして...とチーム戦ならではの考…

AOJ 3054 Tunnel (RUPC 2019 day2-D)

離散量だなんて思わなかった。。。 問題へのリンク 問題概要 (略) 個の長方形からなるヒストグラム (x 座標が から の範囲に存在していて、それぞれの長方形の高さが ) が与えられて、それに合わせて折れ線を最適化する。 折れ線の始点は 正の整数 があって…

AOJ 2903 Board (AUPC 2018 day1-H)

2 変数劣モジュラ関数の和を最小カットで表すという、とても面白い問題!!! 問題へのリンク 問題概要 × の二次元ボードが与えられる。以下のような "#" のところを最小個数の長方形で敷き詰めよ。例えば 4 10 ########## ....#..... ....#..... ..........…

AOJ 2943 イルミネーション (RUPC 2019 day1-G)

燃やす埋めるは今度こそちゃんとマスターする!!! 問題へのリンク 問題概要 × の各格子点に電球がある。 が偶数となるような について、 を頂点とする正方形の中心に装置があって、各装置を押すことで四隅の電球を点灯することができる。 ただし、装置を起…

AtCoder ABC 119 C - Synthetic Kadomatsu (水色, 300 点)

最近の AtCoder は ABC でも考察重視傾向が強くて、こういうのが見落とされがちかもなのん。。。 でも ABC を競プロ入門コンテンツと見たとき、この種の出題がもっと増えると良さそう!!!!! 大事なことを再認識させてくれる感じ。 問題へのリンク 問題概…