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

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

最大値の最小化

AtCoder ABC 320 G - Slot Strategy 2 (Hard) (橙色, 600 点)

広く捉えれば「各スロットに対して止める秒数を割り当てる」方法を考える割当問題だと言えそう。 問題へのリンク 問題概要 のグリッド が与えられる。各マスには 0 から 9 までの数字が描かれている。 今、次の条件を満たす 0 以上の整数値 を考えたとき、 …

第4回 ドワンゴからの挑戦状 予選 2018 D - ディスクの節約 (600 点)

木上で bit DP する感じ 問題へのリンク 問題概要 頂点数 の根付き木が与えられる。各頂点 には重み が付されている。 この根付き木はタスクの依存関係を表している。各頂点に対して、対応するタスクの「実行」と「削除」ができる。 頂点 のタスクを実行する…

AtCoder ABC 281 F - Xor Minimization (青色, 500 点)

数列に対して、2 進法で表して、再帰的に上位桁から 0 と 1 で分類した木を作る!!! こどふぉではよく見るやつですね。 問題へのリンク 問題概要 個の非負整数 が与えられる。ある非負整数 を上手に選んだときの、 の値の最小値を求めよ。 制約 考えたこと…

JOIG 2021 D - 展覧会 2 (AOJ 0704, 難易度 6)

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

square869120Contest #5 B - Emblem

競プロ典型90問の問題 001 の類題。「最大値の最小化」をする二分探索の典型問題ですね。 問題へのリンク 問題概要 二次元平面上に 個の円が与えられます。またそれらとは別に 個の点が与えられます。円同士は互いに交わることはなく、点が円に包含されるこ…

AtCoder ABC 023 D - 射撃王 (試験管青色)

大昔の ABC の問題ですが、今なお色あせない教育的良問。二分探索の練習問題に。 問題へのリンク 問題概要 個の風船がそれぞれ初期状態では高度 の位置にあり、1 秒ごとに ずつ上昇する。これらすべての風船を射撃によって割りたい。 競技開始時に 1 個風船…

AtCoder ARC 115 C - ℕ Coloring (茶色, 500 点)

これ茶色はさすがにびっくりした! 問題へのリンク 問題概要 整数 が与えられる。 正の整数からなる数列 であって、 が の約数であるような任意の に対して という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるよ…

JOI 二次予選 2021 D - 安全点検 (AOJ 0694, 難易度 7)

難易度 8 でもおかしくないと思った。 B や C より易しい気がしなくもないけど、本番の緊張感で B や C を飛ばして D を本気で考える決断はなかなかできなさそう。今回は B - パンケーキを見て冷静になれたか勝負だね... 問題へのリンク 問題概要 個の工場が…

JOI 本選 2014 C - バームクーヘン (AOJ 0600, 難易度 7)

以前にしゃくとり法の記事で特集した問題のひとつだった! 問題へのリンク editorial 問題概要 環状のバームクーヘンを 3 つに分けたい。 バームクーヘンは下図 (問題文から引用) のように 個のピースに分かれていて、それぞれのサイズは となっている。 バ…

AtCoder ABC 170 E - Smart Infants (水色, 500 点)

こういうの苦手すぎるので、素早く綺麗に実装できるようになりたい 問題へのリンク 問題概要 AtCoder に参加している幼児が 人おり、 から の番号が付けられている。また、幼稚園 がある。幼児 のレートは であり、はじめ幼稚園 に所属している。 これから …

AOJ 2629 Manhattan (JAG 夏合宿 2014 day2-A) (250 点)

伝説のりんごさんセットの 1 問目 問題へのリンク 問題概要 二次元座標平面上において、 座標と 座標のうちの少なくとも一方が整数であるような点からなる集合を「道路」と呼ぶ。 道路上の 2 点 のユークリッド距離が実数 で与えられる。 点 から道路のみを…

KUPC 2020 E - Sequence Partitioning

近年非常によく見る DP 高速化系問題!! 問題へのリンク 問題概要 長さ の 3 つの数列 が与えられる。 いま、数列 をいくつかの連続する部分列に分割することを考える。 分割 に対して、スコアを、各区間についての以下の値の最小値として定める。 その区間…

CPSCO2019 Session4 D - Boring Sequence (400 点設定)

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

CODE FESTIVAL 2016 Final B - Exactly N points (緑色, 300 点)

1, 2, ..., i のうちのいくつか選んで和を取った値は、連続した自然数を作れる 問題へのリンク 問題概要 からいくつか選んでできる総和が となるようにしたい。 選んだ数の最大値が最小となるような場合の数を求めよ。 制約 考えたこと 一般に、 によって作…

AOJ 3191 Watering (AUPC 2020 day3-G)

この問題に似てた drken1215.hatenablog.com 問題へのリンク editorial 問題概要 の順列 を最適化したい。以下の手順にしたがって、各要素 のスコアが定まる。この 個のスコアの最大値の最小値を求めよ。 値が のいずれかであるような数列 ( 項) が与えられ…

AOJ 3034 Explosion (RUPC 2018 day2-I)

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

AtCoder ABC 151 D - Maze Master (緑色, 400 点)

面白かった。BFS したり、Warshall--Floyd したり。 問題へのリンク 問題概要 の盤面が与えられる。各マスは '.' か '#' のいずれかである。それぞれ「通路」と「壁」を表している。 「通路を 2 箇所 指定したときの、上下左右に通路のみをたどって から へ…

Codeforces #613 (Div. 2) D. Dr. Evil Underscores (R1800)

こういう貪欲に突き進む処理を書くの、実はかなり苦手かもしれない 問題へのリンク 問題概要 個の 0 以上の整数 が与えられる。上手に正の整数 を選ぶことで、 XOR XOR ... XOR の値の最大値の最小値を求めよ。 制約 考えたこと 最小値を求めたいということ…

第一回日本最強プログラマー学生選手権-予選- D - Classified (青色, 600 点)

初見時は証明なしに再帰的にやった... 問題へのリンク 問題概要 頂点の完全グラフがあたえられる。 このグラフの辺に、非負整数値を付けていく方法のうち 整数値が等しい辺のみからなる部分グラフが奇数長のサイクルを含まない という条件を満たす範囲内で、…

AtCoder AGC 032 E - Modulo Pairing (銅色, 1200 点)

楽しかった。7 時間かかったけど自力 AC できたー! 問題へのリンク 問題概要 正の整数 が与えられる。 個の 以上 未満の整数 を 個ずつのペアに分けたい。 各ペア に対して % の値 (これを醜さと呼ぶ) を求め、その最大値をとる。 この最大値の最小値を求め…

AtCoder AGC 002 D - Stamp Rally (橙色, 1000 点)

部分永続 Union-Find 木の練習をした。 問題概要 N 頂点 M 辺の無向グラフがあります。 グラフは連結です。以下の Q 個のクエリに答えよ: 頂点 x, y が与えられ、「x と y を含む z 個の頂点からなる集合に含まれる頂点の番号の最大値」の最小値を求めよ 解…

JOI 本選 2012 E - JOI 国のお祭り事情 (AOJ 0575, 難易度 10)

並列二分探索が想定ではなさそうだけど、並列二分探索法で解いてみました。 問題へのリンク 解法 #include <iostream> #include <vector> #include <queue> #include <map> #include <algorithm> using namespace std; struct UnionFind { vector<int> par, rank, sz; UnionFind(int n) : par(n), rank(n, 0</int></algorithm></map></queue></vector></iostream>…

AtCoder AGC 026 F - Manju Game (銀色, 2000 点)

ふと考えてみた。区間 DP っぽく にはなるな...なんて思っていたけどそこから落とせなかった...いやこれ何を食べたらこんな二分探索思いつけるようになるの!?!?!?!??? なにかこういう場面で二分探索すると上手く行くよ、というパターン的なものが…

2016 Benelux Algorithm Programming Contest E - Charles in Charge

バチャやりました! vjudge.net E 問題で、バチャに選定した 4 問の中では 2 番目の難度、AtCoder で言うと 400 点くらいの難易度でした。 問題へのリンク 問題概要 N 頂点 M 辺の重み付き無向単純グラフが与えられる。頂点 1 から頂点 N への経路のうち、「…

競プロ典型 90 問 001 - Yokan Party(★4)

「最小値の最大化」には二分探索が有効という典型ですね。 問題へのリンク 解説へのリンク 前提知識 二分探索にまったく経験がない場合は、まずは次の記事を読んでみてください。 qiita.com 問題概要 長さ のようかんがあって、そのうち左端から の位置に切…