探索候補を絞る
ABC 151 F 以来の幾何ですね。ABC 151 F の解法のうち「探索候補として交点を考える」というのが今回もいい感じに使える！ drken1215.hatenablog.com 問題へのリンク 問題概要 二次元平面上に 個の点 が与えられる。それぞれの点に肉が置いてある。このうち…
すごく面白かった！！！ 問題へのリンク 問題概要 長さ の数列 が与えられる。ここから何個か選ぶ。選んだ値を としたとき、そのスコアを以下のように定義する。 選んだ値のメディアンを とする 奇数個の場合は真ん中の値 偶数個の場合は真ん中の 2 つの値の…
その 2 と雰囲気は似ているけど、一気に考えづらくなった！ 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっている 以下のクエリに 回答…
ものすごく間違いやすい雰囲気だったので、探索候補を絞ってから力技で全探索した！！！ 問題へのリンク 問題概要 3 つの整数 の組が門松列であるとは、以下の条件を満たすことである。 は互いに相異なる のいずれかが、3 整数の中で 2 番目に大きな値となっ…
最小包含円と似て異なる問題。 問題へのリンク 問題概要 二次元平面上に 個の点がある。 半径 1 の円を上手に配置したときに、その中に含めることにできる点の個数の最大値を求めよ。 制約 考えたこと 「 点のうち 2 点を通る半径 1 の円」に探索候補を絞っ…
幾何だ！！！！！ そして、こういうので「ギリギリを考える」というのは典型な感じ。 なお、僕は最小包含円のことを知らず、アドホックに解いたけど、ライブラリ貼るだけだったらしい... (その方が計算量も少ない) 他にも、三分探索でも解ける！！！ 問題へ…
信じる心が大切ですね 問題へのリンク 問題概要 組の文字列 が与えられる。 これらの組を好きな順序で好きな回数だけ選んで、 側と 側とをそれぞれ連結した文字列 ができる。 このとき、 が の部分文字列 (連続でなくてよい) とすることができるかどうかを判…
面白かったけど場合分けが怖かった 問題へのリンク 問題概要 "...X......XX..X..X.XXX...X..." のような '.' と 'X' からなる長さ の文字列が与えられる。 先手は連続する 個の '.' をすべて 'X' に置き換える 後手は連続する 個の '.' をすべて 'X' に置き…
いかにも Greedy にできなさそうなので DP！！！ 問題へのリンク 問題概要 長さ の整数数列 が与えられる。今、数列の各項の値を整数分だけ増加させるなどして、数列のどの隣り合う二項も値が異なるようにしたい。 項目を 1 増加させるのに要するコストは で…
すんごく横長な行列に関する問題だけど、実は横の長さを縦の長さ以下にできるというタイプ。 そうすれば の問題に帰着できて、。あとは の bit DP...なのだが、TLE がとれなかった。微妙に詰めが甘かった。。。 問題へのリンク 問題概要 の行列があたえられ…
こういう風にルートが出てくるの、こどふぉだとよく見るね。 ありがちなのが、長さ の線分を整数長ごとに分割するとき、分割の中に登場する長さの種類は 通りしかないとか、そういう形でよく出てくる。 問題へのリンク 問題概要 整数 が与えれる。 長さ の正…
時刻 に対する面積関数 の最小化問題。 全体で三分探索をするのは嘘。 問題へのリンク 問題概要 二次元平面上に 個の点がある。各点は初期位置から出発して秒速 1 の速度で上下左右のいずれかに動いている。 このとき、 点の の値の最小値を求めよ。 制約 考…
こういう全探索、意外と思い浮かぶようになるまでが遠いよね。 そして のケースが結構厄介 ^^; 問題へのリンク 問題概要 二次元平面上に 点がある。最初に整数 を自分で決める。そして、 個の点を好きな順序で順に辿っていく。このとき、 最初の点では +1 そ…
「探索候補は実はそう多くない」という教育的問題！！！ 問題へのリンク 問題概要 組の整数ペア がある。各ペアから整数をどちらかを選ぶ。こうして選ばれた 個の整数の最大公約数の最大値を求めよ。 制約 考えたこと 約数と言われて思い浮かべるべきことの…
ペアリングを頑張る問題として高難易度なすごく楽しい問題。 結構注意力がいる。割とやばいケースがある。 問題へのリンク 問題概要 下記のテトロミノの個数がそれぞれあたえられる。これらを回転は OK で反転は NG で組み合わせて の長方形を作りたい。作れ…
楽しかった 問題へのリンク 問題概要 正の整数 が与えられる。 以下の条件を満たす正の整数 の個数を求めよ: を で割ったときの商と余りが一致する 制約 考えたこと とりあえず について手元で計算しているうちに、商と余りとが一致した値 として考えられる…
楽しかった。7 時間かかったけど自力 AC できたー！ 問題へのリンク 問題概要 正の整数 が与えられる。 個の 以上 未満の整数 を 個ずつのペアに分けたい。 各ペア に対して % の値 (これを醜さと呼ぶ) を求め、その最大値をとる。 この最大値の最小値を求め…
問題概要 個の品物があって、それぞれ価格は である。ここから 個の品物を何回かに買いたい。ここで一回の買い物につき一回ずつ使えるクーポン券が 個あって (使わなくても良い)、各クーポンは ちょうど 個の品物を買ったならば、そのうちの安い順に 個の品…
これ...以前 Twitter につぶやいた問題とよく似てた！！！ 400 点くらいの問題【問題】N 要素の 0 と 1 から成る数列が与えられる。以下の操作を最大 K 回行なって錬成し得る数列が何通りあるか 10e9 で割った余りを求めよ「数列の連続する区間を選んで 0 と…
たったこれだけの問題でも、学ぶべきことがすごくあるイメージ！！！ 問題へのリンク 問題概要 2 つのボタンがあってそれぞれ大きさが である。 大きさ のボタンを押すとコインが 円もらえて、ボタンの大きさが 1 減って になる。 2 回だけ好きなボタンを押…
priority_queue で動的に 個出力する問題作りたいな〜と思ってぼんやりストックしてた問題と一緒だった！！！！！！ 問題へのリンク 問題概要 個の要素からなる数列 個の要素からなる数列 個の要素からなる数列 が与えられる。 からそれぞれ 1 個ずつとりだ…
これも自力で解けたの、嬉しい！！！！！ 問題へのリンク 問題概要 正の整数 が与えられる。 からなる順列 に対して、以下の操作を好きな回数だけ行ってできる順列のうち、辞書順最小のものを求めよ かつ を満たす に対して、 と を swap する 制約 まずは逆…
ツリーの問題！！！！！！！！ 見るからにツリー DP っぽいのだけど、なかなかに頭が混乱する感じ。 この問題の心得は「最適解はどんな形をしているんだろう」を考えることかなと思う。それによって「こういうものだけ探索すれば良い」というのが見えて来る…
ゆかたゆたんと一緒に解いたん。 今後まだ解いてない様々な 500 点問題について何がポイントになっているのかをブログ書きながら明らかにして行きたい。500 点問題の苦手意識を克服するぞい。 問題へのリンク 問題概要 二次元平面上に 個の点が与えられる。…
めちゃいっぱい解法あってすごい！！！！！！！MST への理解が問われる。 いずれ復習をやり切ってちゃんとしたいが取り急ぎ、分割統治法 Kruskal と、想定解法のみ。 問題へのリンク 問題概要 頂点からなるパスグラフと整数 が与えられる。各頂点には重み が…
あまり良くない方針でゴリ押してしまった。でもゴリ押しで通せることの証左になるかと思って記録してみることに 問題へのリンク 問題概要 下図のような「円の列」の内部だけを通る折れ線 (最初の円の中心と、最後の円の中心とを結ぶ) の長さの最小値を求めよ…
これまたちょっと重たい。。。 問題へのリンク 問題概要 折れ線グラフが与えられる。これは に対して () を結んでいる。あらゆる水平な直線を考えたときの、折れ線グラフのうち直線の上に来ている部分を連結成分ごとに分解したとき、連結成分の個数として考…
AtCoder ではとても珍しい、注意して考えることの多い、重めの全探索な問題 問題へのリンク 問題概要 ピラミッドの高さを当てたい。 ピラミッドには 中心座標 (Cx, Cy) と 高さ H が定まっており, 座標 (X, Y) の高度は max(H−|X−CX|−|Y−CY|, 0) である。 ま…
共通接線ライブラリの整備 問題へのリンク 問題概要 互いに重ならない円が N 個ある。 直線を考えたとき、そのスコアは 各円に対して、その円と共有点を持たず、その円との距離がある一定 (円に依存して決まる値) 以下であるとき 1 を加算、そうでないとき 0…
オイラーツアーの練習に解いたけど、発想も面白いん！！！ 問題へのリンク 問題概要 頂点 1 を根とする、頂点数 N の根付き木がある。以下の Q 個のクエリに答えよ: M 個の頂点 v1, v2, ..., vM に実をつける。「その頂点を根とする部分木に含まれる実の個数…
