ツバサの備忘録

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

動的計画法(DP)

Educational DP Contest / DP まとめコンテスト Z - Frog 3

問題 提出コード 解法 番目の足場へ行く最小コスト とします。すると、 となります。 これを式変形すると、 となります。は最後に足して問題ないことがわかります。 とすると、 という式になり、調べたいのは、 のの際の最小値 となります。 これは直線の式…

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

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

Educational DP Contest / DP まとめコンテスト X - Tower

問題 提出コード 解法 現在、積まれているブロックの重さの総和をとします。 ここに、2種類のブロックを、どちらの順番で新しく下に置くかを考えます。 の方がより上にくる場合 の方がより上にくる場合 1つめの条件は、結局2つのブロックを乗せることにした…

Educational DP Contest / DP まとめコンテスト W - Intervals

問題 提出コード 解法 文字目を"1"にした場合に、で得られる得点の最大値 を考えます。 すると、 が間に含まれているものを除いた区間達について計算した場合の、で得られる得点の最大値に、が間に含まれている区間の得点の総和が、の値になります。 これを…

Educational DP Contest / DP まとめコンテスト V - Subtree

問題 提出コード 解法 全方位木dpをします。 初めに頂点1が根である際の値を求めます。 を根とする部分木について、を黒で塗った際の部分木の塗り方 とすると、頂点の子の集合をとして、 となります。 を根とした際の求めるべき答え とすると、 となります。…

第13回JOI予選 D - 部活のスケジュール表 (Schedule)

問題 提出コード 解法 日目に参加した部員の状態がであるような、から日目までの部員の組み合わせの通り数 とします。 すると、 の中に、責任者が含まれていなければならない という条件があるので、もしの中に責任者がいなければ、 となります。 そうでない…

ABC132 F - Small Products

問題 提出コード 解法 番目にを置くような数列の場合の数(ただし、 ) 番目に、を満たすようなを置く数列の場合の数 とします。 以下で最大の整数を、を満たすようなの個数をとすると、それぞれ次のように遷移を行うことができます。 あとは、全てΣの形になっ…

みんなのプロコン2019 D - Ears

問題 提出コード 解法 適当に実験をすると、散歩後の石の個数は、座標が小さい順に、次のような区間でわけることができます。 石が0個の区間 石の個数が2個以上の偶数の区間 石の個数が奇数の区間 石の個数が2個以上の偶数の区間 石が0個の区間 ただし、それ…

AOJ 2200 - Mr. リトー郵便局

問題 提出コード 解法 まずは、陸路と海路それぞれについて、ワーシャルフロイド法を用いて、任意の町間の最短距離を計算しておきます。町から町の最短経路について、陸路を、海路をとします。 そして、DPを行います。 回目の集配を終えた時点で、船が町にあ…

AOJ 1176 - 輪番停電計画

問題 提出コード 解法 はじめに、2次元累積和を用いて、ある長方形の範囲の需要の合計をで求めることができるようにしておきます。 ここから、DPを行います。 長方形の左上が,右下がとなるような範囲のグループの分け方の最適解 とします。最適解、なのでグ…

ABC130 E - Common Subsequence

問題 提出コード 解法 LCSや編集距離に近いものを感じたので、似たような遷移のDPを考えていきます。 までを見終えた段階でできる、問題の条件を満たす整数列の個数 とします。 初期値としては、です。いずれのパターンでも、共に1つも選ばない1通りの整数列…

ABC129 E - Sum Equals Xor

問題 提出コード 解法 制約を見ると明らかに桁DPのような匂いがするので桁DPをしました。 の上から桁目をとします。 となるが存在した場合、をすると繰り上がりが発生するので、となります。逆に、それ以外のはどれを使用してても問題の条件を満たします。 …

ABC129 C - Typical Stairs

問題 提出コード 解法 段目の階段にたどり着くには、段目もしくは段目から移動する2つの方法のどちらかを利用する必要があります。 つまり、段目に行く移動の種類数と、段目に行く移動の種類数がわかれば、段目に行く移動の種類数はその総和で表すことができ…

Educational DP Contest / DP まとめコンテスト U - Grouping

問題 提出コード 解法 制約から見てbitDPです。 現在グループを組めていないウサギの状態がのときに、それ以降のグループ分けで得ることができる得点の最大値 とします。すると、の部分集合を用いて、 と書くことができます。 ただし、は、というグループを…

Tenka1 Programmer Beginner Contest 2019 D - Three Colors

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

AOJ 2741 - インビジブル

問題 提出コード 解法 ゲーム系で、ぱっと貪欲な解法がなさそうだったので、メモ化再帰をすることにしました。6次元DPです。 とし、それぞれの添え字が 先手が次にスタックにカードを置くとき上から何枚目のカードを置くか 後手が次にスタックにカードを置く…

AOJ 2254 - 最短ルート

問題 提出コード 解法 制約を見ればbitDPと書いてあるのでbitDPをすることにします。 まず、番のステージをクリアした後に、再び番目のステージを行くことは考えなくていいです。2回以上同じステージに行くことで得をすることはありません。 ということで、…

エクサウィザーズ 2019 D - Modulo Operations

問題 提出コード 解法 (現在黒板に書かれている数字に影響があるような数字を取り除くことをここでは”使う”、ないような数字を取り除くことを”使わない”と表現します) まず、回目に取り除いた数字よりも大きい数字を、回目以降で取り除いても、黒板に書かれ…

ABC122 D - We Like AGC

問題 提出コード 解法 4次元DPをします。 問題の条件を満たす文字列が存在したときに、新しく最後尾に1文字加えてなお問題の条件を満たすのがどういう場合かを考えています。 追加する文字が'A'または'T'のとき がどうなっていても問題の条件を満たします。 …

AGC031 B - Reversi

問題 提出コード 解法 まずはじめに、が以降も連続していた場合、その連続している部分の石は必ず同じ色になるので、1つの石に圧縮してしまいます。 この操作を行った、残りの石の列について考えていきます。 次のような操作について考えてみます。 左側が1…

Educational DP Contest / DP まとめコンテスト T - Permutation

問題 提出コード 解法 番目までの順列が完成しているときに、番目の数字を加えて条件を満たす数列を作成することを考えます。 長さの数列で、一番後ろにを選ぶときの並べ方の通り数 とします。 を求めるために、番目の数字と番目の数字の関係をもとに場合分…

ゆるふわ競プロオンサイト参加記

2/9に東京で行われました、@matsu7874さん主催の競プロオンサイトイベント、に参加してきました! コンテスト自体は全8問で、2時間のセットでした。自分は、ABCDEGの6完でした! B式A+B 集合写真 線香 最短経路は何本ありますか ガソリンスタンド 射的 感想 …

BAPC2018 E - Entirely Unsorted Sequences

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

Educational DP Contest / DP まとめコンテスト S - Digit Sum

問題 提出コード 解法 桁DPです。というより、こちらとまったく同じ問題です。 emtubasa.hateblo.jp ただし、入力の順番だけが異なります。 感想 だいぶ前に通したコードなので、改めて書き直しました。 つい先日のABCでも桁DPが解法になりうる問題が出てい…

Educational DP Contest / DP まとめコンテスト P - Independent Set

問題 提出コード 解法 を色としたとき(1:白、0:黒)の、根とする部分木の色の決め方 とします。 全体の根はで固定します。 の子をとします。 すると、を黒で塗るには、の子はすべて白でなければならないこと、を白で塗る場合は、の色は何色でもよいことを考え…

Educational DP Contest / DP まとめコンテスト O - Matching

問題 提出コード(1) 提出コード(2) 解法 bitDPです。 番目までの男子に対してペアを作成し終えた段階で、残っている女子の状態がの際の組み合わせの数 とします。 とりあえず、女子全員が残っている状態をとします。 1人目の男子に対してペアを組める女子を1…

Educational DP Contest / DP まとめコンテスト N - Slimes

問題 提出コード 解法 とします。 体のスライムを合体していくのではなく、体の大きさのスライムを、体に分解していく、というようにして考えていきます。 このとき、大きさのスライムを分解するときのコストはになります。 区間のスライムが1体になっている…

Educational DP Contest / DP まとめコンテスト M - Candies

問題 提出コード 解法 普通にDPを考えてみます。 人目までにキャンディを配り終え、個のキャンディが残っている状態になるような場合の数 とすると、が答えとなります。 さて、人目にキャンディを配るとき、~個の中で好きな個数を選ぶことができます。つま…

Educational DP Contest / DP まとめコンテスト L - Deque

問題 提出コード 解法 区間DPです。 の区間だけ数列が存在する場合についての、お互いが最善手を尽くした際のの値 とします。答えはとなります。 メモ化DPにするとやりやすいです。 初期値は、です。 が奇数ならそのまま、偶数なら-1倍します。 あとは、以下…

ABC117 D - XXOR

問題 提出コード 解法 2進数の桁DPです。 としたとき、は現在見ている桁を表し、下から桁目、は桁目で0を使うか1を使うか、は桁DPで毎回出てくる、以下が確定しているかどうか、です。 今回は、が大きい方から見ていきます。そして、現時点での答え、すなわ…