問題 atcoder.jp 解法 区間DPで解く。 区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。 𝑑𝑝[𝑙][𝑟] := 区間 [ l, r ) について、最適な状況下での何かしらの値 dp[0][0]から、幅0でdp[0][0], dp[1][1], dp[2][2] ....と計算していく。 先攻後攻…

問題 atcoder.jp 解法 K個の石の山に対して、 dp[k] := k個の石からなる山で先手が勝ち状態か(=1なら勝ち状態） というdpを設計。 数が小さい方から、Kまでの石の山をシミュレーションしてdpの数値を埋めていく。 まずはk = 0と非常に単純な状態から調べてい…

問題 atcoder.jp 解法 DP（動的計画法）で解く。 公式動画で最初に説明されている、貰うDPのパターンで実装してみた。 dp[i][j]を、「Sのi文字目までを使って、chokudaiのj文字目まで選択する方法」と定義。 dpを解いていく。 実装 参考 www.youtube.com atc…

問題 atcoder.jp 難しい問題。 解法 動的計画法で解く。 線路のコスト計算はC x (|i - i'| + |j - j'|)円。 この計算式から絶対値を外していく。 i' <= i, J' <= jとすれば C x i - C x i' + C x j - C x j' = C x i + C x j - C x i' - C x j' = C ( i + j …

問題概要 N 個の料理があり，それぞれ作るためにオーブンを使う時間はTiである。2つのオーブンを用いてすべての料理を作るのにかかる時間は最短何分か。 1≤N≤100 0≤Ti≤103 atcoder.jp 実装方針 公式解説の説明がわかりやすい。 atcoder.jp 2つのオーブンのど…

コンテストで出来なかった問題を復習してみました。 atcoder.jp もっとも参考にした解説 この問題は、はまやんさんの解説が一番わかりやすいと感じたので、これをメインの参考に。 blog.hamayanhamayan.com 実装方針としては、動的計画法で解く問題とのこと…