ツバサの備忘録

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

動的計画法(DP)

ABC160 F - Distributing Integers

問題 提出コード 解法 のみの場合について答えることができればあとはうまく伝播させて全方位木DPにしてしまえばよいので、の場合を考えます。 を根とする部分木についての、数字の配置パターン数 を根とする部分木の頂点数 とします。の計算方法については…

JOI2017/2018 予選 D - 水ようかん (Mizuyokan)

問題 提出コード 解法 番目までのようかんを切り終えて、ピースの最小値がになるように切り分けたときに取り得る"ピースの最大値"の最小値 とします。こうすることで、答えはで求めることができます。 すると、でピースを作成すると仮定した際に遷移がどうな…

AOJ 2312 - 魔法少女さやかちゃん

問題 提出コード 解法 添え字は0-indexedとします。 区間の総和は、BITや累積和を用いて高速に取得できるものとします。 とします。 仮に円環でなく直線上に音符を配置しているとした場合、明らかに音符をの昇順に配置するのが最適です。 しかし今回は、音符…

AOJ 2966 - G トレジャーハンター (Treasure Hunter)

問題文 提出コード 解法 解説の通りこちらを参考にして通しました。 再帰でDFSをしながらナップサックを解き、戻り値として、今いる頂点を使用した際の最適解配列と、使用しなかった際の最適解配列を返します。 今いる頂点をとします。子をとします。 1つめ…

AOJ 2965 - F グリッドの番号

問題 提出コード 解法 小さい順に数字を当てはめていくとき、上段の右端に配置するか、下段の右端に配置するかの二択になることを利用します。 番目までの数字を入れ終えて、上段に配置した個数が個かつ、直近手の上下の配置情報がのときの配置の通り数 とし…

2019-2020 ACM-ICPC Latin American Regional Programming Contest F. Fabricating Sculptures

リンク 問題文 解法 1段ずつ下からブロックを積んでいくことを考えます。 ある段のある区間にブロックを積んだら、それ以降はその積んだ区間に対してのみ積んでいくかどうかを考えます。 今区間の幅が残りで、ブロックの残り個数が個の際の、そこからの構築…

SWERC 2018 K. Dishonest Driver

問題文 解法 区間DPをします。 の区間に対する最小コスト とすると、 になります。 ただし、の文字列を複数回連結するとになる場合のみ、 になります。 この複数回連結、という判定はKMPの周期判定を用いると上手くできます(下のブログ参考)。 ただし、ぴっ…

2019-2020 ACM-ICPC Latin American Regional Programming Contest バチャ 参加記

Dashboard - 2019-2020 ACM-ICPC Latin American Regional Programming Contest - Codeforces なんか解法書こうと思ったんですけど時間かかりそうなのでそこは暇だったらにします しろくんとsuta君と出ました。 流れ 開始後 僕がAから、suta君がDから、しろ…

ABC153 E - Crested Ibis vs Monster

問題 提出コード(1) 提出コード(2) 解法 番目までの魔法を撃ち終えて、だけダメージを与えたときに消費する魔力の最小値 とすると、 のとき のとき となります。 初期値は、答えは、です。 見るべきの範囲は、までなので、最大でも程度になり、このDPによる…

ABC149 D - Prediction and Restriction

問題 提出コード 解法 次に出す手は、手前の手にのみ依存します。 よって、じゃんけんの出す手は、で割った余りごとに独立して考えることができます。 番目に出す手がであるときにおける、の手番についての得点の総和の最大値 とすると、答えは となります。…

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…