ツバサの備忘録

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

動的計画法(DP)

AGC032 D - Rotation Sort

問題 提出コード 解法 シフトという操作が少しわかりづらいのですが、結局は 任意の要素を取り出し、別の任意の位置に挿入する(現時点より左に挿入するならコストは、右であれば) という操作ができることになります。 ので、それぞれの要素を、 右側に移動し…

Typical DP Contest I - イウィ

問題 提出コード 解法 操作をいろいろ試してみると、一連の操作で消すことができる部分というのは区間になっていることがわかります。 の区間の文字全てを消すことができるかどうか という区間DPを考えます。が3の倍数でない時はもちろんNOです。 を全て消去…

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning

問題 提出コード 解法 が回文になる条件は、a ~ zについて、に含まれる個数が全て偶数になる、もしくはどれか1つのみが奇数になる、のどちらかです。 a, b, ..., zとします。 先頭の文字から番目の文字までを見て、奇数個になる文字について、を計算したもの…

Typical DP Contest G - 辞書順

問題 提出コード 解法 まず、 文字目の次にという文字が現れるインデックスの最小値 を計算します。 これは、という更新を行えばよいです。 さて、 文字目を先頭で使った際にできる、部分文字列の種類数 というDPを考えます。 文字目を使った際に考えられる…

Waseda Orientation Programming Contest 2020 J - トレジャーハンター

問題概要 解法 Med Large 1つめ:01ナップサックに帰着 2つめ:個数制限なしナップサック 3つめ:ダイクストラ法 おまけ(Med解以外の想定TLE,MLE解法) コード 問題概要 種類のはしごがあり、番目のはしごの長さはです。 以上以下の値で、以下の条件を満たさない…

AOJ 2611 - 順位付け

問題 提出コード 解法 木の2乗DPとかなんとか言われてるやつです。 問題文をじっくり読むと、入力が木になっていて、そのなかで順位付けをしていくことがわかります。木全体の根は、入力時点で一番高さが高かった頂点です。 木の高さがすべて異なる場合は簡…

MIS.W新歓コンテスト2020

自分の大学にあるサークルが主催するコンテストに参加しました。 自分のコードはまとめてここに上げてあります。問題の前から順番にa,b,...と振ってあります。自分のコードを動かすことができるeの入力データも添えました。 長いのでかなり端折る部分があり…

AOJ 2703 - サイコロスタンプ

問題 提出コード 解法 あらかじめ、番目のサイコロが転がった結果記される数字と座標のペアリストを作成しておきます。 サイコロの集合について、これらを最適な順番で転がした際に得ることができる得点の最大値 とすると、答えはです。 の求め方について考…

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をしました。 の上から桁目をとします。 となるが存在した場合、をすると繰り上がりが発生するので、となります。逆に、それ以外のはどれを使用してても問題の条件を満たします。 …