最適化問題
少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題！ 問題へのリンク 問題概要 頂点数 の完全グラフが与えられる。頂点 1 から頂点 へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えること…
とてもややこしくてハマってしまった......。とても教育的な Greedy 問題。 問題へのリンク 問題概要 個の商品がベルトコンベアで運ばれてくる。 番目の商品は、時刻 から時刻 の間 (両端含む) に点字できる。 点字マシンは 1 秒あたり 1 個の商品にしか点字…
会議設定時間を 0 時、1 時、2 時、...、23 時をそれぞれ全探索するのが一番分かりやすいと思う！ 問題へのリンク 問題概要 キーエンス社員の 個の拠点に対して同時に会議を設定したい。拠点 には社員が 人いて、時差 (世界標準時で 0 時のときの時刻) は で…
セグ木上で DP する問題として、人生で最初に解くべき問題と言えるかもしれない！ 問題へのリンク 問題概要 個の区間がある。各区間 は、 で重みは である。 これらの区間からいくつか選ぶ方法のうち、 全体を被覆するものについて、最小重みを求めよ。 制約…
「平均値の最小化」に基づく二分探索 + 最小全域問題 問題へのリンク 問題概要 (意訳) 頂点数 、辺数 の重み付き単純無向グラフが与えられる。各辺 は、重みが であり、長さが である。 グラフの辺集合のうち、すべての頂点を連結にするものを考える。そのよ…
「平均値の最適化」を二分探索に帰着させる系の典型問題！ 問題へのリンク 問題概要 体のモンスターがいて、それぞれ質量は 、魔力は である。 また、 体のお助けモンスターがいて、それぞれ質量は 、魔力は である。 今、これら 体のモンスターからちょうど…
とても典型的な「平均値の最大化」→「二分探索」の問題！ 問題へのリンク 問題概要 個の食塩水がある。 番目の食塩水は、重さが グラムであり、濃度 パーセントである。 これらの食塩水から 個選んで混ぜてできる食塩水の濃度の最大値を求めよ。 制約 考えた…
とても教育的問題！！ 蟻本の二分探索の節に「平均値の最大化」があるけど、まさにそれ！！！ 問題へのリンク 問題概要 頂点数 、辺数 の DAG が与えられる。各辺 について、 であることが保証される。 各辺 には、美しさ と、コスト がついている。 頂点 0 …
怒りの場合分け。ちょっと苦手系だけど一発 AC できてよかった。 問題へのリンク 問題概要 高橋君は現在 にいて、荷物は にあり、荷物を目的地 に届けたい。 高橋君は荷物のある位置に入ることはできず、荷物と隣接した状態から荷物の方向に移動すると、荷物…
素朴なシミュレーションが通るものの、それを正確に実装するのも結構大変 問題へのリンク 問題概要 種類のスライムがいる。 種類目のスライムは、サイズが であり、 体いる。 一般にサイズが であるスライムを 2 体合体させて、新たにサイズが のスライムを …
chokudai さんの思想が詰まった問題 問題へのリンク 問題概要 個の開発案がある。これらの開発案によって上昇し得るパラメータが 種類ある。 開発案 () を採用すると、パラメータ () の値が だけ上昇する。その分、 のコストがかかる。 すべてのパラメータを…
少し重たかった。でもいい問題。JOI にありそう。 問題へのリンク 問題概要 数直線上に 箇所の燃料補給所がある。 番目の補給所は次のようになっている。 座標 にある 補給すると、現在の HP が であるとき、HP が になる (コストとして を支払う) 今、高橋…
AOJ 2373 HullMarathon とよく似た問題。 問題へのリンク 問題概要 二次元平面上に 点を以下の条件を満たすように配置する。各点を とし、偏角を とする。 点 と、原点との距離は このとき、多角形 の面積の最大値を求めよ。 制約 考えたこと ほとんどこの問…
企業合コンで解いた。ギャグ系だった。 問題へのリンク 問題概要 円周上に 個の点があって、2 個ずつ 組のペアを作って線分で結ぶ。 すでに 組のペアができていて、線分が結ばれている。残りの点についてペアを作って線分を作っていったときの交差数の個数の…
面白い最適化問題！ 問題へのリンク 問題概要 二次元平面上で、原点からの距離が であるような 点の凸包の面積として考えられる最大値を求めよ。 制約 考えたこと 凸包というところが面倒だが、要は 本のうちの何本かを選んで それを適切な順序に並び替えた…
これは学びの深い DP 問題！ 問題へのリンク 問題概要 長さ の数列 がある (負値もありうる)。これらの数列をいくつかの連続する区間に分割する。 区間分割の仕方を最適化したときの、各区間における「最大値と最小値の差」の総和として、考えられる最大値を…
二重辺連結成分分解とか low-link とか色々考えたけど、結果的に最後は「ただ DFS 木を作るだけ」になるという、すごく印象的な問題！ 問題へのリンク 問題概要 以上 以下の整数からなるサイズ の 2 つの数列 、 が与えられる。 今、0 と 1 のみからなるサイ…
区間分割をしていく DP として、一番最初に解くべき問題を意図して作った！！ けんちょん本の 3 例題 (ナップサック問題、編集距離、これ) の 1 つでもある。 問題へのリンク 問題概要 個の要素が一列に並んでいる。これら 個の要素に対して、区間 のコスト…
つい最近 CodeQUEEN 決勝 E 問題でも出てきた「最大値の最大化」典型テクニック！！！！ 問題へのリンク 問題概要 長さ の 2 つの数列 と が与えられる。今、互いに disjoint な区間群 をとる ( は自由)。ただし、区間の長さの総和がちょうど となるようにす…
本当に三分探索で通るのね！ これらの問題を思い出した drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 二次元平面上に 本の線分がある。この平面上の円盤 (円周と内部を含む) のうち、 本の線分すべてと共有点をもつようなも…
ビットベクターで高速化するのは、いつも見落としてしまう！ 問題へのリンク 問題概要 円環状に 個の魔法石があり、 番目の魔法石は、価値が 、色が である。色は 1 以上 50 以下の整数で表される。 今、これらの魔法石に対して、隣り合う魔法石の色の差が …
こういうの詰めるの時間かかる。サンプルも弱いので、愚直シミュレーション解も実装して、それとの一致を確かめたりなどした！ 問題へのリンク 問題概要 '1'〜'9' のみからなる文字列 が与えられる。この文字列に対して文字列を返す関数 がある。 は次の操作…
ちゃんと証明しないと、なかなか安心して提出できない系 問題へのリンク 問題概要 整数列 が与えられる。次の操作を繰り返し行って、 の最大値と最小値の差が 1 以下となるようにしたい。実現のための操作の最小回数を求めよ。 を選んで、 に 1 を足し、 か…
トップタイがある場合に注意！ 問題へのリンク 問題概要 (0 始まりに表現改) 人の人 がいる。人 のプログラミング力は である。 人 は必要に応じてプログラミング力を鍛えることで、 人の中で単独トップになろうとしている。 そのためにプログラミング力をい…
最近話題の Functional Graph の問題！ 問題へのリンク 問題概要 人 がいる。各人 には 1 人ずつ嫌いな人 がいる。 今、彼らに順番にキャンディーを配る。ただし、各 について、もし人 よりも先に にキャンディーを配ると、不満度が だけ加算される。 キャン…
opt さん、とよさんと一緒に解いた。楽しかった！ 問題へのリンク 問題概要 数列 に対して、最大 回の操作を繰り返すことで順列 を作りたい。 回目の操作では、値 ( 以上 以下) を選ぶと、コスト がかかる 値 を選んだとき、数列の末尾 を取り出して、順番を…
ネタコンテストなのかと思いきや、問題面白くて、この D 問題は勉強になった。答え決め打ちの二分探索！ 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 この文字列について 回のクエリに答えたい。 各クエリでは整数値 が与えられ…
壁にぶつかるまで動く設定の迷路問題！ 問題へのリンク 問題概要 のグリッドがある。各マスは壁 (文字 '#') か通路 (文字 '.') かのいずれかである。グリッドの外周のマスはすべて壁であることが保証されている。 プレイヤーは最初、マス にいる (0-indexed)…
黒マスを避けながら、長方形領域の値の総和を最大化する問題として解いた！ 問題へのリンク 問題概要 のグリッドがあって、各マス には正の整数 が書かれている。 グリッドに含まれる長方形領域のうち、「長方形領域に含まれる値の総和」と「長方形領域に含…
少し前処理が面倒な DP。PCK の予選突破ライン上の問題のようですね！ 問題へのリンク 問題概要 個の整数 が黒板に書かれている (各整数は 100 桁までありうる)。 奇数の精と、偶数の精がいる。 奇数の精は、黒板に書かれている数字がすべて奇数となるように…
