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

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

ABC-F

AtCoder ABC 169 F - Knapsack for All Subsets (600 点)

どこかでめっちゃ似たのを解いたことあると思ったらコレだった! drken1215.hatenablog.com 問題へのリンク 問題概要 長さ の正の整数列 と、正の整数 が与えられる。 個の整数 の空でない部分集合 は 通りあるが、そのそれぞれについて、 = の部分集合のう…

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

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

AtCoder ABC 159 F - Knapsack for All Segments (600 点)

ごちゃごちゃとばぐらせながら何とか通した... 問題へのリンク 問題概要 要素の数列 が与えられる。この数列の 通りの区間それぞれについての 区間内の要素の部分集合であって総和が であるものの個数 の総和を求め、998244353 で割ったあまりを求めよ。 制…

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

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

AtCoder ABC 154 F - Many Many Paths (600 点)

すっごく色んな方法がありそう!!! 問題へのリンク 問題概要 正の整数 が与えられる。, を満たすすべての整数 についての の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと とりあえず二項係数の計算自体は、適切に前処理をしておけば、 で…

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

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

AtCoder ABC 152 F - Tree and Constraints (600 点)

包除原理をとても素朴な状態で問いかける問題!!! 問題へのリンク 問題概要 頂点のツリーが与えられる。ツリーの各辺を白色または黒色に塗る 通りの方法のうち、以下の 個の制約をすべて満たすものの個数を求めよ。 個目の制約は 2 頂点 が指定され、 と …

AtCoder ABC 151 F - Enclose All (最小包含円、600 点)

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

AtCoder ABC 150 F - Xor Shift (600 点)

バチャやった。13 位相当で割とよかった。 ロリハした。 問題へのリンク 問題概要 長さ の整数列 , が与えられる。以下の条件を満たす 以上 以下の整数 と、整数 の組をすべて求めよ。 = が成立する 制約 考えたこと 整数列 を circular shift した上で、 と…

AtCoder ABC 143 F - Distinct Numbers (600 点)

かなり辛いことを頑張ったけど、本当はすごく明快な問題だった!! 問題へのリンク 問題概要 個の整数 がある。各 に対して、以下の答えを求めよ。 残っている整数から、どの 2 つも互いに異なる 個の整数を選んで抜き取ることを繰り返したい 抜き取れる回数…

AtCoder ABC 142 F - Pure (600 点)

色んな方法がありそう。 問題へのリンク 問題概要 頂点数 、辺数 の単純な有向グラフが与えられる。なお各有向辺の向きをなくして得られる無向グラフも単純であるとする (有向辺 (u, v) があったら辺 (v, u) はない)。 このグラフの有向サイクルであって、有…

AtCoder ABC 141 F - Xor Sum 3 (600 点)

Xor Sum シリーズしゃん。典型てんこ盛り!!! XOR は各桁ごとに独立に考えるとよい XOR に関する問題は mod. 2 での方程式みたいになることも多い であることから上位の桁から辞書順的に優先で考えるような貪欲が決まる などなど。 問題へのリンク 問題概…

AtCoder ABC 132 F - Small Products (600 点)

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

AtCoder ABC 131 F - Must Be Rectangular! (600 点)

なんか既視感があった。それがどこから来たのか、いまだよくわからない。。。 問題へのリンク あと、今回のような二部グラフの作り方はあり本 P.205 の POJ 3041 Asteroids あたりもそんな感じ。こういうのを一度見ておくと、この二部グラフ作りは定石になる…

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

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

AtCoder ABC 128 F - Frog Jump (600 点)

ジャンプの過程を無視して、最終的に出来上がるものがどうなるかを考えて、それをわかりやすく特徴づける 調和級数になるタイプの全探索 というタイプの問題。結構重たい。AGC なら C 問題でありそう。 問題へのリンク 問題概要 個の地点 にそれぞれ のスコ…

AtCoder ABC 127 F - Absolute Minima (600 点)

超絶苦手系。でもこういうのパッとできるようにせな。 問題へのリンク 問題概要 関数 があります。 はじめ、これは定数関数 です。 個のクエリが与えられるので、順番に処理してください。クエリは 2 種類あり、入力形式とクエリの内容は以下の通りです。 更…

AtCoder ABC 129 F - Takahashi's Basics in Education and Learning (600 点)

重たい。。。 でも例えば行列 に対して の計算を行列累乗に帰着させるテクニックは、蟻本中級編の行列累乗のところに載っていたりする。それを膨らませると みたいな計算も、行列累乗でできそうという気持ちには確かになるよね。。。(なったけど昨日間に合わ…