ツバサの備忘録

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

動的計画法(DP)

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 集合写真 線香 最短経路は何本ありますか ガソリンスタンド 射的 感想 …

BAPC2019 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で毎回出てくる、以下が確定しているかどうか、です。 今回は、が大きい方から見ていきます。そして、現時点での答え、すなわ…

Educational DP Contest / DP まとめコンテスト K - Stones

問題 提出コード 解法 素直にグランディ数を求めれば良いです。例によってグランディ数についてはこちらがわかりやすいかと思います。 グランディ数 - zukky162のブログ 今回は、重要なのがグランディ数は0であるか1であるか、なので2以上の場合も1にしてし…

Educational DP Contest / DP まとめコンテスト J - Sushi

問題 提出コード Sushi問題は難しいことで有名です(要出典) 解法 ループする系の期待値は、こんな感じで立式すると見えてきます。 今回は、お皿にのっているお寿司の数を利用します。 3個のっている寿司が皿、2個が皿、1個が皿だとして、そこから全ての寿…

Educational DP Contest / DP まとめコンテスト I - Coins

問題 提出コード 解法 確率です。 番目までのコインを投げて、表が回出る確率、とします。 もちろん、です。 答えは、 (ただし、 )の総和になります。 番目までのコインを投げて回表が出ていた場合、番目のコインを投げると表の回数がになるか、になります。…

Educational DP Contest / DP まとめコンテスト H - Grid 1

問題 提出コード 解法 マスに移動する方法数 とします。 すると、に移動するには、もしくはを通るしかないので、 ならば、 そうでなければ となります。 答えはを見ればわかります。

Educational DP Contest / DP まとめコンテスト G - Longest Path

問題 提出コード あきらかにこれで使えそうな問題ですね… 解法 グラフにおいて、スタート地点(入次数が0である頂点)に近い方から順番に、その頂点がゴールだったと仮定した場合における最長の距離を確定させていきます。 幅優先探索のようなものをします。…

Educational DP Contest / DP まとめコンテスト F - LCS

問題 提出コード 明らかにMLEを起こしそうなコードを提出するのはやめましょう。 解法 求める文字列の長さだけなら、よくある問題です。 ですが、今回は文字列自体も求めなければいけないので、DPの遷移の際に、たどってきた1つ手前の値を一緒に記録してあげ…

Educational DP Contest / DP まとめコンテスト E - Knapsack 2

問題 提出コード 解法 番目までの品物を利用して合計が価値がとなるような組み合わせの中での合計重量の最小値 とします。 となります。あとは、をで、を0で初期化し、このDPを解くことで、となるの最大値を求めれば、これが答えになります。

Educational DP Contest / DP まとめコンテスト D - Knapsack 1

問題 提出コード 解法 こちらと全く同じです。 動的計画法(ナップサック問題について) - ツバサの備忘録 番目までの品物を使って、重さの合計がとなるような組み合わせの中での価値の最大値 とすると、 となります。 答えはの最大値です。

Educational DP Contest / DP まとめコンテスト C - Vacation

問題 提出コード 解法 日目に行動を選択(0:A,1:B,2:C)したときの~日までの幸福度の合計の最大値 とします。 すると、 のとき のとき のとき となります。 あとは、これをもとに計算をし、の最大値を選べば答えになります。

Educational DP Contest / DP まとめコンテスト A - Frog 1,B - Frog 2

問題(A) 問題(B) 提出コード(B) Bの問題においてK=2とすればAの問題と同じになります。 解法 個目の足場に行くための最小コスト、とします。すると、 が答えになります。 あとは、 となります。ここで、は1以上以下かつ、が0以上となるような数字です。 今回…

Typical DP Contest バチャ

ということで、5日のDPまとめコンテストの予行練習も兼ねてTypical DP Contestを埋めていきました。解いた感想を書いていこうかなと思います。 AtCoder Virtual Contest 目次 目次 A - コンテスト B - ゲーム C - トーナメント D - サイコロ E - 数 F - 準急…

Typical DP Contest M - 家

問題 提出コード 解法 bitDPです。だんだん詰め合わせ感が増えてきました。 同じ階層でからに移動するパターン数 とすると、これをの行列に見立てて乗すると、が答えになります。 を求めることさえできれば、あとはこの行列式のを求めていき、程度で答えが求…

Typical DP Contest K - ターゲット

問題 提出コード 解法 区間スケジューリングのように、区間の終わりの部分に注目すると、LISに帰着させることができます。 まず、中心座標はx軸上に存在しているので、それぞれの円について、中心座標とがわかっているとき、円と軸が接する2点は、とになりま…

Typical DP Contest J - ボール

問題 提出コード 解法 bitDPです。 期待値の考え方については、こちらの問題のおかげですんなりいきました。 ARC085 C - HSI - ツバサの備忘録 座標においてある物の状態がである場合に、そこから全ての物を倒すまでに投げるボールの回数の期待値 とします。…

Typical DP Contest H - ナップザック

問題 提出コード 解法 基本的な考え方は普段のナップサックと同じで、ある重さになるような荷物の選び方の中での価値の最大値、を求めていきます。 今回、荷物には色が塗られており、種類以下でナップサックに荷物をつめなければなりません。 ということで、…