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

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

二分探索

AtCoder ABC 077 C - Snuke Festival (緑色, 300 点)

lower_bound の練習に!!! あと、「3 つのものを考えるときは、真ん中を固定して考える」という考え方の典型。 問題へのリンク 問題概要 3 つの数列 (長さ ) が与えられる。各数列から要素 を選ぶ方法のうち、 を満たすものの個数を求めよ。 制約 考えたこ…

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

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

AtCoder ABC 134 E - Sequence Decomposing (水色, 500 点)

実は双対性が深く絡んでるけど、割と素直な Greedy でも解ける 問題へのリンク 問題概要 要素からなる整数列 が与えられる。これらの要素をいくつかの色に塗り分けたい。ただし、同じ色で塗られた要素は狭義単調増加になるようにしなければならない。 このよ…

JOI 二次予選 2021 C - イベント巡り (AOJ ????, 難易度 8)

これはアレだ!!! DP の最適値そのものの値を利用して次の遷移を作る系。フクロモモンガなんかもそういう系の問題だった覚えがある。 問題へのリンク 問題概要 2 つの町 (1 と 2) がある。 個のイベントがあって、それぞれ町 において発生し、時刻 に始ま…

JOI 本選 2009 B - ピザ (AOJ 0539, 難易度 6)

ひょっとしたら難易度 5 との境界の問題だったかもしれない。lower_bound() を試すいい感じの例題。 ジャッジページへのリンク 問題文 editorial 問題概要 一周の長さが であるような周回コースがあって、コース上に 個の店舗がある。コース上の 1 点の座標…

AOJ 1208 Rational Irrationals (ICPC アジア 1999 A)

Stern-Brocot 木がちょうどよく使える 問題へのリンク 問題概要 正の整数 が与えられる。分子・分母がともに 以下の正の整数であって、既約分数であるような分数の集合を と表すことにする。 を満たす最大の の要素 を満たす最小の の要素 をそれぞれ求めよ…

AOJ 3212 Intimate Slimes (OUPC 2020 D)

|x-a| + |x-b| + ... + |x-z| を最小にする x が a, b, ..., z のメディアンになる話は有名で、それを拡張すると仕組みがわかった! 問題へのリンク editorial 問題概要 体のスライムがいて、それぞれの強さは となっている。以下の操作を行うことができる …

JOI 本選 2008 C - ダーツ (AOJ 0529, 難易度 6)

AtCoder 版蟻本記事で、登竜門として紹介している問題。 ずばり「半分全列挙 + 二分探索」です! 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらの整数のうちから重複を許して 4 個まで選んで総和をとる (1 …

JOI 春合宿 2011 day4-3 IOI (難易度 6)

lower_bound を上手に駆使する系 ジャッジページへのリンク 問題概要 人の選手が、コンテストに参加している。各選手の現在の得点は である。 どの選手についても、今後加算される可能性のある得点は、 点以上 点以下となっている ( 問中 問の競技が終了して…

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

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

AtCoder ARC 109 B - log (茶色, 400 点)

二分探索でやればよさそう。本当は でもできるのかも。 問題へのリンク 問題概要 正の整数 が与えられる。 整数 のうち、いくつか選んだものが以下の条件を満たすようにしたい。そのような選び方のうち、選ぶ個数の最小値を求めよ。 選んだ整数はいくつかの…

JOI 予選 2016 D - JOI国のお散歩事情 (AOJ 0622, 難易度 6)

手を動かしてみると、どうなってるかが見えてくる! 問題へのリンク 問題概要 人がそれぞれ座標 に並んでいる (単調増加、負もありうる、各 は偶数)。そして時刻 0 において、 人はそれぞれ正の方向 ( で与えられる) または負の方向 ( で与えられる) に 1 秒…

JOI 本選 2020 B - JJOOII 2 (AOJ ????, 難易度 6)

最初 DP とか考えたくなるやつ。落ち着くと見えてくる。 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられる。ところで、レベル の JOI 文字列とは、"JJ...JOO...OII...I" (それぞれ 個…

AtCoder ABC 184 F - Programming Contest (水色, 600 点)

まさかの超典型な半分全列挙!!!(蟻本にもほぼ同じ問題あり!!) 問題へのリンク 問題概要 個の正の整数 と、正の整数 が与えられる。 個の整数の中からいくつか選んで総和をとる。その値が より大きくならない範囲内での、その値の最大値を求めよ。 制約 …

AtCoder ABC 181 E - Transformable Teacher (緑色, 500 点)

頭整理が大変だけど、考え方はわかる。 問題へのリンク 問題概要 は正の奇数である。 個の整数 が与えられる。以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる 個の整数 を 2 個ずつペアにして 組のペアを作る それぞれのペアの「数値の差」の総…

AtCoder ABC 181 F - Silver Woods (黄色, 600 点)

条件反射で二分探索してしまった!!!この問題めっちゃ面白くて好き!!! 問題へのリンク editorial 問題概要 平面上に 2 直線 で囲まれた通路がある。この通路の中の の部分に 本の大きさの無視できる釘が打たれており、 本目の釘の座標は である。 高橋…

AOJ ???? GRIDMST (KUPC 2020 F)

愚直にやると 本の辺がある問題に対して、上手にやる系の問題 問題へのリンク 問題概要 グリッドグラフがある。 広義単調増加な正整数列 があり、それぞれの長さは となっている。 頂点 と頂点 は、重みが である無向辺で結ばれている 頂点 と頂点 は、重み…

AOJ ???? Sequence Partitioning (KUPC 2020 E)

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

AOJ ???? Numbers on Papers (KUPC 2020 B)

DP 高速化系問題 問題へのリンク 問題概要 のグリッドが与えられる。各マス には数値 が書かれている。 各行から 1 個ずつ数値を選んで行順に並べてできる数列を考える。そのような数列は 通り考えられるが、そのうち広義単調増加なものが何通りあるか、1000…

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

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

AtCoder ARC 106 E - Medals (赤色, 700 点)

高速ゼータ変換を思いつくのに時間かかった 問題へのリンク editorial 問題概要 あなたは 人の従業員を持つ店の店長です。 番目の従業員は今日から「 日連続で働いた後 日連続で休む」ことを繰り返します。 あなたは今日から毎日出勤し、その日に出勤してい…

AtCoder ABC 056 D - No Need (ARC 070 D) (黄色, 600 点)

めっちゃいろんな解法がある! 各 i に対して i 番目を抜いた部分の解を求める系 左右から累積和 戻す DP 単調性を見抜いて二分探索 問題へのリンク 問題概要 個の整数 がある。これらの整数の部分集合のうち、数の総和が 以上になるものをよい集合と呼びま…

AOJ 3189 Mod Rush (HUPC 2020 day3-E)

これ好き!楽しい!! 問題へのリンク 問題概要 長さ の数列 で定義される、全 ステップの操作が与えられる。操作は整数 に対して行うものであり、 回目の操作は次のものである: を % で置き換える 個の整数 それぞれに対して ステップの操作を行って得られ…

AOJ 3170 Freqs (HUPC 2020 day1-G)

難しかったー!!平方分割かな...とまでは思ったので、もっと粘り強く考えられるようにならないと...! 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の 4 種類のクエリを 回処理してください。 クエリ 1: が与えられるので、 () を に更新する…

AtCoder ABC 144 D - Water Bottle (茶色, 400 点)

これかーーー数学ゲーじゃないかと物議を醸した問題。でも普通にいい問題だと思う!! 問題へのリンク 問題概要 底面が一辺 cm の正方形であり、高さが cm であるような直方体型の水筒に、体積 cm3 の水を入れる。 底面の正方形の一辺を軸として、この水筒を…

AtCoder ABC 155 D - Pairs (青色, 400 点)

最初は、問題を見た瞬間に「にぶたんだ...」となったので、青 diff に驚いたのだった。でもいざ実装を始めると、頭壊れる問題ですね。。。^^; 問題へのリンク 問題概要 個の整数 が与えられる。これらから 2 つを選んで積をとって得られる 個の整数のうち、…

Judge System Update Test Contest 202004 D - Calculating GCD (400 点)

面白かった 問題へのリンク 問題概要 要素からなる正の整数列 が与えられる。以下の 個のクエリに答えよ 各クエリは整数 が与えられる の順に、 という更新を行う 初めて となる瞬間の を求めよ 最終結果が 1 より大きいときは、その値を答えよ 制約 解法 (1…

AtCoder ABC 161 D - Lunlun Number (緑色, 400 点)

この手の DFS、一時期全然見なかったけど、最近復活してきた! 問題へのリンク 問題概要 1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。 番目に小さいルンルン数を求めよ。 制約 考えたこと さて、「 番目に小さ…

AtCoder Petrozavodsk Contest 001 C - Vacant Seat (緑色, 500 点)

インタラクティブ...でも問題自体は「単調性が成り立たなくても二分探索できるよ!」という教育的なものだった! 問題へのリンク 問題概要 円形状に並んだ 個の椅子がある ( は奇数)。各椅子は 男性がいる 女性がいる 空席 のいずれかである。どの隣り合う 2…

Codeforces Round #626 (Div. 1) B. Present (R2100)

確かに AtCoder で完全既出だった! drken1215.hatenablog.com 問題へのリンク 問題概要 要素の数列 が与えられる。これらから 2 つ選んで和をとって得られる 個の整数の XOR 和を求めよ。 制約 #include <bits/stdc++.h> using namespace std; const int INF = 1<<30; int </bits/stdc++.h>…