ツバサの備忘録

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

動的計画法(DP)

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

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 - ナップザック

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

Typical DP Contest F - 準急

問題 提出コード 解法 駅で止まるような駅までのパターン数、のようにしていきたいところですが、連続して何駅止まったか、という情報が必要になるので無理です。 逆転の発想をして、駅を通過するような駅~のパターン数、としましょう。 ダミーの駅というも…

Typical DP Contest E - 数

問題 提出コード 解法 制約をみてもわかるように桁DPです。 とします。は、上から桁目を決める段階、という意味です。は、今作成している数字の桁和をで割った余りがであるという意味です。は、今作成している数字が未満であることが確定しているかどうか、…

Typical DP Contest B - ゲーム

問題 提出コード いきなり難易度高くないですか…? 解法 左右それぞれの山に積まれている物の合計個数の偶奇によって、どちらのターンかは一意に決まります。 が偶数のとき、左右の合計が奇数であれば、次は後攻、偶数であれば先攻です。 が奇数の場合はこの…

Typical DP Contest C - トーナメント

問題 提出コード 解法 はじめに、番の人が番の人に勝つ確率、としておきます。 番目の人が、第ラウンドで勝つ確率、とします。 初期状態はであり、答えはをすべて見ればよいです。 簡単に言えば、番目の人が第ラウンドで戦う可能性のある相手の集合をとした…

Typical DP Contest D - サイコロ

問題 提出コード 復習問題だったのですが、見事MLEを吐きました。 解法 を素因数分解したときに登場する2の個数、とします(3,5も同様です)。 基本的な方針としては、 回サイコロを振ったときに、2が回、3が回、5が回登場するような確率 とします。4は2が2回…

Typical DP Contest A - コンテスト

問題 提出コード DPまとめコンテストに向けて埋め+復習をしていこうかと思います。 解法 基本的なDPの1つではないでしょうか。 問目までを解き終えた状態で、得点がになるような方法があるかどうか として、1がある、0がない、とします。初期状態はです。す…