ツバサの備忘録

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

2018-12-31から1日間の記事一覧

Typical DP Contest J - ボール

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

Typical DP Contest H - ナップザック

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

Typical DP Contest F - 準急

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

Typical DP Contest E - 数

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

Typical DP Contest D - サイコロ

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

Typical DP Contest C - トーナメント

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

Typical DP Contest B - ゲーム

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

Typical DP Contest A - コンテスト

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