Typical DP Contest バチャ

ということで、5日のDPまとめコンテストの予行練習も兼ねてTypical DP Contestを埋めていきました。解いた感想を書いていこうかなと思います。
AtCoder Virtual Contest

目次

A - コンテスト

解法はこちら↓
Typical DP Contest A - コンテスト - ツバサの備忘録
Aは復習問題になります。
基本的なDPだと思います、普段でいくと300点前後でしょうか？
始めたての頃はもちろん悩みに悩んだ問題なので、さらっと解けるようになっていて気持ちがいいです。

B - ゲーム

解法はこちら↓
Typical DP Contest B - ゲーム - ツバサの備忘録
Aから急激に難易度が上昇した気がします。とてつもなく時間がかかりました。
2人で最善を尽くしあうゲームの問題はとてつもなく苦手意識があります。
実装もそこそこ重たいので、苦労しながらのACでした。

C - トーナメント

解法はこちら
Typical DP Contest C - トーナメント - ツバサの備忘録
こういうことをやりたいんだろうなぁ、というものをそのままコードにした感じです。
指数部が整数値でない場合どうすればいいんだろう、と思っていたのですがpowが使えるのですね～、初めて知りました(忘れてるだけかも？)。
これまた配列の添え字関連で悩まされました。

D - サイコロ

解法はこちら↓
Typical DP Contest D - サイコロ - ツバサの備忘録
復習問題その2です。
前回解いたときは解説ACをしたので、きちんと解法の流れが頭の中に残っていたので良かった半面、MLEを一回出したので悔しいです。

E - 数

解法はこちら↓
Typical DP Contest E - 数 - ツバサの備忘録
復習問題その3です。
こちらも、前解いたときは初めての桁DPだったので解説を見ていましたが、他でも桁DPの問題を触っていたおかげで、さらっと解けるようになりました。
その割には30分かかっているのですが…
この手の問題にしては基本的な部類だと思います。

F - 準急

解法はこちら↓
Typical DP Contest F - 準急 - ツバサの備忘録
昔々、ICPCの練習会の際に先輩がこの問題を見ながら類題を解いていた記憶があります(自分も問題を読んでいたのですが、解法がさっぱりだったので投げてました)。
逆転の発想ぽいものが必要な感じだったので、時間がかかりました。

H - ナップザック

解法はこちら↓
Typical DP Contest H - ナップザック - ツバサの備忘録
ただのナップサック問題を数段レベルアップさせたような感じでした。
解法をこれだ！って決めつけていたのですが、それがうまくいってよかったです。違ったら解けてなさそうです。

J - ボール

解法はこちら↓
Typical DP Contest J - ボール - ツバサの備忘録
制約を見た時点であーこれだ、っていうのと、上の記事にも書いていますが期待値の問題で躓いた結果印象に残っている問題があり、こう計算すればいい！というのがすぐにわかったのがいい感じに動きました。
後ろの方の問題の中では現状これが一番さらっと解けたかな？と思います。と書こうとしたのですが、真ん中らへんでした(先は長いですね)。

K - ターゲット

解法はこちら↓
Typical DP Contest K - ターゲット - ツバサの備忘録
昔既読を付けたことがあるのですが、当時は解けていませんでした。なぜか解説を見ることもしていなかったようです。
時間は結構かかりましたが、無事に自力で解けました。昔解けなかったものが解けるようになるのはうれしいですね。

M - 家

解法はこちら↓
Typical DP Contest M - 家 - ツバサの備忘録
先輩が通していたので、負けないぞー！と思って解きました。
1問1問が重いので、やりきった感がでますね...代わりに疲れますけど。

ということで、最後は時間があまりない+難しくて解けないのコンボによりほぼできませんでしたが、10問ほど通すことができました。
DPの気持ちが前よりはわかるようになるといいですね～