kmjp https://blog.hatena.ne.jp/kmjp/ kmjp's blog https://kmjp.hatenablog.jp/ Codeforces さて本番解けなかった問題D。 周りを見ても、EよりDの方が正解者が少ないようだ。 http://www.codeforces.com/contest/268/problem/D 問題 中央の棒を取り囲むように４本の脚がある遊具がある。 1～Nの高さで、それぞれ１本ずつ中央といずれかの脚に棒を渡す。 遊具は４本の脚のいずれかが棒同士がH+1以上離れていないような構成を取れる、棒の配置の数を答える。 解法 最初４本の脚それぞれでH+1以上離れたかどうかおよび一番近い棒の高さを覚えてDPしようとした。 でも、４本の脚で棒の高さを覚えると１回O(H^4)の計算が必要なので、全部でO(NH^4)とTLE… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkmjp.hatenablog.jp%2Fentry%2F2013%2F02%2F03%2F0900" title="Codeforces #164 Div2. D. Wall Bars - kmjp&#39;s blog" 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 2013-02-03 09:00:00 rich https://kmjp.hatenablog.jp/entry/2013/02/03/0900 1.0 100%