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

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

二分探索

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

最初 DP とか考えたくなるやつ。落ち着くと見えてくる。 問題へのリンク 問題概要 "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>…

Codeforces CodeCraft-20 (Div. 2) F. Battalion Strength (R2800)

実装がエグエグのエグだけど、実はなんと、遅延評価セグ木すら必要なくて、普通のセグ木だけあれば解けてしまう! 問題へのリンク 問題概要 個の整数 に対して定まる量 を次のように定義する: の部分集合を選ぶ 通りの方法から一様ランダムに選んで、さらに…

AtCoder ABC 157 F - Yakiniku Optimization Problem (橙色, 600 点)

ABC 151 F 以来の幾何ですね。ABC 151 F の解法のうち「探索候補として交点を考える」というのが今回もいい感じに使える! drken1215.hatenablog.com 問題へのリンク 問題概要 二次元平面上に 個の点 が与えられる。それぞれの点に肉が置いてある。このうち…

Codeforces Round #625 (Div. 1) C. World of Darkraft: Battle for Azathoth (R2000)

セグ木を使って差分更新していく系、解けるけど実装が苦手すぎるので、こういうのをスパッと書けるようになりたい! 問題へのリンク 問題概要 個の武器と、 個の盾を持って、 体の敵に立ち向かう。あたなは武器の中から 1 個、盾の中から 1 個を選ぶ (初期状…

Codeforces Round #617 (Div. 3) E2. String Coloring (hard version)

これと同じでは!? atcoder.jp 問題へのリンク 問題概要 長さ の文字列 が与えられる。 いま、文字列の各 index に色を塗ることを考える。色を塗ったあと、隣接する異なる色をもつ 2 文字を swap することができる。swap した結果得られる文字列がソートさ…

AtCoder ABC 153 F - Silver Fox vs Monster (水色, 600 点)

区間加算に対応したデータ構造の出番! 問題へのリンク 問題概要 体のモンスターがいて、それぞれ座標 にいて、HP は である。すべてのモンスターを倒したい。 1 回の魔法で、座標 を指定して、[ ] の範囲内にいるモンスターの HP をすべて ずつ減少すること…

DISCO ディスカバリーチャンネル 2020 予選 E - Majority of Balls (橙色, 800 点)

の場合の場合分け中で出力時に "! " を入れるのを忘れていることにずっと気づかずに WA Rush という...ひどい......コンテスト本番じゃなくてよかった。。。 問題へのリンク 問題概要 (インタラクティブ) を奇数とする。 個のボール があって、そのうちの 個…

Codeforces Round #609 (Div. 1) C. K Integers (R2300)

とてもこどふぉっぽい問題だと思った!!!こういうのを得意になるぞー!!! 問題へのリンク 問題概要 の順列が与えられる。各 に対して、以下の問いに答えよ。 順列の隣り合う 2 要素を swap して、順列のどこかの場所で がこの順に連続で並んでいる状態に…

yukicoder No.972 選び方のスコア

すごく面白かった!!! 問題へのリンク 問題概要 長さ の数列 が与えられる。ここから何個か選ぶ。選んだ値を としたとき、そのスコアを以下のように定義する。 選んだ値のメディアンを とする 奇数個の場合は真ん中の値 偶数個の場合は真ん中の 2 つの値の…

AOJ 3034 Explosion (RUPC 2018 day2-I)

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

第5回 ドワンゴからの挑戦状 予選 2018 D - Square Rotation (赤色, 800 点)

すごく詰め切るのに時間かかった 問題へのリンク 問題概要 (意訳) 二次元平面上に 個の座標 (格子点) が与えられる。正の整数 が与えられる。 まず、各座標について「 座標を だけ増減する」「 座標を だけ増減する」という操作を好きなだけ繰り返す。ただし…

AtCoder ABC 146 C - Buy an Integer (茶色, 300 点)

二分探索の教育的問題ですね! 問題へのリンク 問題概要 正の整数 が与えられる。正の整数 に対して を の桁数とする。このとき を満たす最大の正の整数 を求めよ。 制約 考えたこと わけわからない式だし、二分探索に決まってるやろ!!!という雰囲気があ…

AtCoder ARC 099 F - Eating Symbols Hard (赤色, 1200 点)

楽しかった。こういうのでロリハ使うの楽しい。発想自体は Zero-Sum Ranges (200 点) と似てる。 問題へのリンク 問題概要 高橋君は、いつも頭の中に長さ 2000000001 の数列 と、整数値 を思い浮かべている。初期状態では、数列の各要素値と、 の値はすべて …