ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

包除原理

ABC152 F - Tree and Constraints

問題 提出コード 解法 あらかじめ、頂点からへのパスに使われる辺の集合を表すビット列を、前計算で計算しておきます。これは、任意の頂点からBFSで辿っていけば良いです。 個の条件からいくつか選んだ、条件の集合に対して以下のような数を計算します。 少…

Educational DP Contest / DP まとめコンテスト Y - Grid 2

問題 提出コード 解法 包除原理を用いて解きます。 個以上の壁を通り、番目の壁に到達するような通り方の場合の数 とします。ここで、壁について、行、列の順で昇順ソートしておくと、番目の壁を通る際に、番目以降の壁を先に通ることはありえなくなるので、…

Tenka1 Programmer Beginner Contest 2019 D - Three Colors

問題 提出コード 解法 まず、三角形の成立条件を思い出すと、長さの三角形が存在するには、 が全て成立している必要があります。 逆に、が最長の辺かつを満たしているとき、三角形を作成することはできません。両辺にを追加した後に2で割ると、 という条件が…

BAPC2018 E - Entirely Unsorted Sequences

問題 提出コード 問題 個の数字が与えられるので、その数字を使って作れる数列のうち、以下のような条件を満たす数列の個数をで割った値を求めてください。 全ての数字について、その数字より左側に自分より大きいものが存在する、もしくは右側に小さいもの…

ABC020 D - LCM Rush

問題 提出コード(100点) 提出コード(満点) 100点から満点にもっていくことができず、解説を見ました… 言われれば確かにそうだけど~って感じですね。 解法 まずは100点までです。 の制約が少ないので、について何かをするんだろうな、という気持ちになります…

codeFlyer (bitFlyer Programming Contest)予選 C - 徒歩圏内

問題 提出コード これを自力で解けなかったのは結構悔しいです…最近思い通りになかなか解けないですね 解法 ,,となるようなの組を探します。 要素が3つ存在するので、まずは真ん中を決め打ちしたときののペアの個数を求めることを考えます。 あるについて、…

ARC077 D - 11

問題 提出コード 解法 ダブっている数字は数列に1つ必ず存在します。 ダブってる数字のうち左側にあるものを,右側にあるものをとしたとき、数列は次のようになっています。 ここで、はそれぞれ0個以上の要素を持っている数列です。 長さの部分列を数え上げる…

ABC005 D - おいしいたこ焼きの焼き方

D - おいしいたこ焼きの焼き方 提出コード mp[i][j] = からまでの、長方形の部分の美味しさの総和 (ただし、添え字が0以下のときは0) として、入力と同時に累積和をとっていきます。 すると、ある長方形をl,r,u,d(それぞれ長方形の左、右、上、下の辺の番号)…

ABC003 C - AtCoderプログラミング講座,D - AtCoder社の冬

今回もバチャコンで解いたC問題とD問題のメモです。 C - AtCoderプログラミング講座 提出コード まずは動画のレートを降順でソートします。 そうしたら、大きい方から動画を見る個数だけ持ってきて、それを小さい順に見ます。 動画を見るたびに現在のレート…