mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ 問題 https://www.facebook.com/hackercup/problem/1640119959603837/ 解法 まず, はしごを座標順にソートして, よくある stack のアレを使います。 mayokoex.hatenablog.com この記事のテクニックを使えば, O(N) であるハシゴからどこまで蛇が繋がれるのかがわかります。dp[i] = (i 番目のはしごと, i 番目のはしごと高さの等しい, 蛇がつながることの出来る i 番目未満のはしごの間における, 蛇の長さの二乗の和) とします。例えば問題文の Case #3 だと, dp[0] = 0 dp[1] =… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F01%2F24%2F094908" title="Facebook Hacker Cup 2016 Round 2 Snakes and Ladders - mayoko’s diary" 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 2016-01-24 09:49:08 rich https://mayokoex.hatenablog.com/entry/2016/01/24/094908 1.0 100%