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

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

探索候補を絞る

AtCoder AGC 037 A - Dividing a String (灰色, 300 点)

意外とすぐにわからなかったんやけど... 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。以下の条件をみたす最大の正整数 を求めよ。 を空でない 個の文字列へと分割したとき、連続する文字列は相異なる 制約 Greedy は嘘 パッと思い浮かぶ …

AOJ 1350 There is No Alternative (ICPC アジア 2014 F) (450 点)

これ好き!!! 問題へのリンク 問題概要 頂点数 、辺数 の、連結な重み付き無向単純グラフ が与えられる。 このグラフの「最小全域木」はさまざまなものが考えられるが、そのすべてに含まれるような辺の集合を考える。 その集合の要素数と、その集合に含ま…

AOJ 3049 A Polygon And Circles (ACPC 2018 day2-K)

ボロノイ図!! 問題へのリンク editorial 問題概要 頂点の凸多角形と、 個の点が与えられる。以下の条件を満たす最小の正の実数 を求めよ。 個の点を中心とした半径 の円を考える 凸多角形の周および内部のどの点も、いずれかの円に包含される 制約 考えた…

AOJ 3167 Many Points (HUPC 2020 day1-D)

面白かった! 問題へのリンク editorial 問題概要 次の問題が ケース分与えられる。 二次元平面上に 個の格子点が与えられる。これらに対し、以下の条件を満たす直線 が存在するかどうかを判定せよ。 どの点に対しても、 との距離が等しい 制約 考えたこと …

AOJ 3181 Proper Instructions (HUPC 2020 day3-J)

比較的素直な考察で解ける問題 問題へのリンク 問題概要 umgくんは 1 次元上の座標 0 にいます。今は時刻 0 です。時刻が 1 進むごとに、今いる座標より 1 大きい座標に移動するか、 1 小さい座標に移動するか、その座標にとどまるかという行動ができます。 …

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

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

AtCoder AGC 019 A - Ice Tea Store (茶色, 300 点)

丁寧に簡潔に 問題へのリンク 問題概要 合計で グラム買いたい。 0.25 グラフで 円のセット 0.5 グラムで 円のセット 1 グラムで 円のセット 2 グラムで 円のセット がある。これらのセットを組み合わせて グラム買うための最小金額を求めよ。 考えたこと 0.…

Codeforces Round #489 (Div. 2) D. Nastya and a Game (R2100)

方針立ってからも、ちょっと実装辛い ^^; 問題へのリンク 問題概要 長さ の正の整数列 と、正の整数 が与えられる。 正数列の連続する部分列であって、その積が、和の 倍となっているものが何通りあるかを求めよ。 制約 考えたこと パッと思うことは、積の中…

AtCoder ABC 161 F - Division or Substraction (水色, 600 点)

めちゃくちゃ面白かった!!! 問題へのリンク 問題概要 整数 が与えられる。以下の条件を満たす 以上 以下の整数 の個数を求めよ。 整数 を用いて、 に対して操作を行っていく が で割り切れるならば を で置き換えて、そうでない場合には を に置き換える…

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

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

yukicoder No.972 選び方のスコア

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

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

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

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

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

AOJ 1132 Circle and Points (ICPC 国内予選 2004 D) (450 点)

最小包含円と似て異なる問題。 問題へのリンク 問題概要 二次元平面上に 個の点がある。 半径 1 の円を上手に配置したときに、その中に含めることにできる点の個数の最大値を求めよ。 制約 考えたこと 「 点のうち 2 点を通る半径 1 の円」に探索候補を絞っ…

AtCoder ABC 151 F - Enclose All (青色, 600 点)

幾何だ!!!!! そして、こういうので「ギリギリを考える」というのは典型な感じ。 なお、僕は最小包含円のことを知らず、アドホックに解いたけど、ライブラリ貼るだけだったらしい... (その方が計算量も少ない) 他にも、三分探索でも解ける!!! 問題へ…

Xmas Contest 2019 J - Sub-Post Correspondence Problem

信じる心が大切ですね 問題へのリンク 問題概要 組の文字列 が与えられる。 これらの組を好きな順序で好きな回数だけ選んで、 側と 側とをそれぞれ連結した文字列 ができる。 このとき、 が の部分文字列 (連続でなくてよい) とすることができるかどうかを判…

Educational Codeforces Round 73 E. Game With String (R2400)

面白かったけど場合分けが怖かった 問題へのリンク 問題概要 "...X......XX..X..X.XXX...X..." のような '.' と 'X' からなる長さ の文字列が与えられる。 先手は連続する 個の '.' をすべて 'X' に置き換える 後手は連続する 個の '.' をすべて 'X' に置き…

Educational Codeforces Round 73 D. Make The Fence Great Again (R1700)

いかにも Greedy にできなさそうなので DP!!! 問題へのリンク 問題概要 長さ の整数数列 が与えられる。今、数列の各項の値を整数分だけ増加させるなどして、数列のどの隣り合う二項も値が異なるようにしたい。 項目を 1 増加させるのに要するコストは で…

Codeforces Round #584 - Dasha Code Championship E. Rotate Columns (R2400)

すんごく横長な行列に関する問題だけど、実は横の長さを縦の長さ以下にできるというタイプ。 そうすれば の問題に帰着できて、。あとは の bit DP...なのだが、TLE がとれなかった。微妙に詰めが甘かった。。。 問題へのリンク 問題概要 の行列があたえられ…

AtCoder ABC 132 F - Small Products (黄色, 600 点)

こういう風にルートが出てくるの、こどふぉだとよく見るね。 ありがちなのが、長さ の線分を整数長ごとに分割するとき、分割の中に登場する長さの種類は 通りしかないとか、そういう形でよく出てくる。 問題へのリンク 問題概要 整数 が与えれる。 長さ の正…

AtCoder ABC 130 F - Minimum Bounding Box (黄色, 600 点)

時刻 に対する面積関数 の最小化問題。 全体で三分探索をするのは嘘。 問題へのリンク 問題概要 二次元平面上に 個の点がある。各点は初期位置から出発して秒速 1 の速度で上下左右のいずれかに動いている。 このとき、 点の の値の最小値を求めよ。 制約 考…

diverta 2019_2 B - Picking Up (緑色, 300 点)

こういう全探索、意外と思い浮かぶようになるまでが遠いよね。 そして のケースが結構厄介 ^^; 問題へのリンク 問題概要 二次元平面上に 点がある。最初に整数 を自分で決める。そして、 個の点を好きな順序で順に辿っていく。このとき、 最初の点では +1 そ…

Chokudai SpeedRun 002 J - GCD β (500 点)

「探索候補は実はそう多くない」という教育的問題!!! 問題へのリンク 問題概要 組の整数ペア がある。各ペアから整数をどちらかを選ぶ。こうして選ばれた 個の整数の最大公約数の最大値を求めよ。 制約 考えたこと 約数と言われて思い浮かべるべきことの…

AtCoder AGC 008 C - Tetromino Tiling (青色, 600 点)

ペアリングを頑張る問題として高難易度なすごく楽しい問題。 結構注意力がいる。割とやばいケースがある。 問題へのリンク 問題概要 下記のテトロミノの個数がそれぞれあたえられる。これらを回転は OK で反転は NG で組み合わせて の長方形を作りたい。作れ…

diverta 2019 D - DivRem Number (緑色, 500 点)

楽しかった 問題へのリンク 問題概要 正の整数 が与えられる。 以下の条件を満たす正の整数 の個数を求めよ: を で割ったときの商と余りが一致する 制約 考えたこと とりあえず について手元で計算しているうちに、商と余りとが一致した値 として考えられる…

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

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

Codeforces 552 DIV3 F. Shovels Shop (R2300)

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

AtCoder ABC 124 D - Handstand (緑色, 400 点)

これ...以前 Twitter につぶやいた問題とよく似てた!!! 400 点くらいの問題【問題】N 要素の 0 と 1 から成る数列が与えられる。以下の操作を最大 K 回行なって錬成し得る数列が何通りあるか 10e9 で割った余りを求めよ「数列の連続する区間を選んで 0 と…

AtCoder ABC 124 A - Buttons (灰色, 100 点)

たったこれだけの問題でも、学ぶべきことがすごくあるイメージ!!! 問題へのリンク 問題概要 2 つのボタンがあってそれぞれ大きさが である。 大きさ のボタンを押すとコインが 円もらえて、ボタンの大きさが 1 減って になる。 2 回だけ好きなボタンを押…

AtCoder ABC 123 D - Cake 123 (水色, 400 点)

priority_queue で動的に 個出力する問題作りたいな〜と思ってぼんやりストックしてた問題と一緒だった!!!!!! 問題へのリンク 問題概要 個の要素からなる数列 個の要素からなる数列 個の要素からなる数列 が与えられる。 からそれぞれ 1 個ずつとりだ…