ツバサの備忘録

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

包除原理

Tenka1 Programmer Beginner Contest 2019 D - Three Colors

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

BAPC2019 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プログラミング講座 提出コード まずは動画のレートを降順でソートします。 そうしたら、大きい方から動画を見る個数だけ持ってきて、それを小さい順に見ます。 動画を見るたびに現在のレート…