問題：E - Payment 解答：Submission #16213292 - AtCoder Beginner Contest 155 解法：dp[i][j] ：上からi桁までの支払金額が決まっていて、j=0ならぴったり支払い、j=1ならキャリーがある状態、としてDP。DPはサンプルを合わせた…

問題：C - 節制 解答：Submission #16166455 - AtCoder Beginner Contest 013 解法：普通の食事をi回する場合、質素な食事の回数jの条件は、 j < (H - (N - i) * E + i * B) / (B - D)を満たすことである。よって、各iごとにjが最大である場合のコストを比較…

問題：D - Match Matching Python解答：Submission #16067781 - AtCoder Beginner Contest 118 Python解法：dp[i]：残りマッチ棒がi本の時に作れる最大の数字 として配るDPをする。dp[0]が答え。 C++解答：Submission #16083490 - AtCoder Beginner Contest …

問題：https://atcoder.jp/contests/abc054/tasks/abc054_d 解答：Submission #16049869 - AtCoder Beginner Contest 054 解法：薬品量の最大値は薬品A, Bともに400グラムであるため、以下のDPが間に合う。 dp[i][j][k] : i番目のお店の混合液までで、薬品Ａ…

問題：D - 語呂合わせ 解答：Submission #15893924 - AtCoder Beginner Contest 031 解法：各数字に対し、対応する単語の文字長を決めると、各v[i], w[i]の対応においてどの数字がどの単語にあたるかが一意に決まる。よって各数字に対応する単語の文字長（1…

問題：E - Common Subsequence 解答：Submission #15893522 - AtCoder Beginner Contest 130 解法：dp[i][j] ： sのi番目、tのj番目を最後に使うときの共通部分列の個数（空集合は除く）、 sm[i][j]：dpの二次元累積和 とすると、s[i] == t[j]の場合にdp[i+1…

問題：D - 徒競走 解答：Submission #15838027 - AtCoder Beginner Contest 041 解法： bitDPでトポロジカルソートの通り数を数える。 考え方としては、「すでに使用した頂点集合」をbitとして持たせてDPする。すなわち入次数の小さい頂点から推移させていく…

問題：C - たんごたくさん 解答：Submission #15800122 - 天下一プログラマーコンテスト2016本戦（オープンコンテスト） 解法：トライ木を使用する。 ei1333.github.io dp[i]：Sのi文字目までの単語の重みの最大値とする。 あらかじめ各単語をトライ木に格納…