yosupo https://blog.hatena.ne.jp/yosupo/ よすぽの日記 https://yosupo.hatenablog.com/ CF #286のDiv2C/Div1AとDiv2E/Div1Cのwriterをしていました せっかくなのでこの2問について解説を書きます Div2C/Div1A 想定より難しかったようです。ごめんなさい。M=島の数=30001とします。 O(M^2)解 dp[i][j]: 今番号iの島にいて、前回距離jジャンプを行った。ここから取れる最大のジェムの数(ただしi番目の島のジェムはまだ取っていないとする) とし、メモ化再帰or動的計画法を行います。 if (i >= M) dp[i][j] = 0 else if (j == 1) dp[i][j] = (the number of gem in … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyosupo.hatenablog.com%2Fentry%2F2015%2F01%2F19%2F184128" title="CF #286 Div2C/Div1A &amp; Div2E/Div1C解説 - よすぽの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2015-01-19 18:41:28 rich https://yosupo.hatenablog.com/entry/2015/01/19/184128 1.0 100%