問題：D - 映画の連続視聴 解答：Submission #15529217 - Code Formula 2014 本選 解法：それなりに探索しないといけなそう。DPを行う。 前処理として、時間0と終了時間を含む（重複のない）配列を作成しておき、また終了時間からその配列のインデックスが分…

問題：E - M's Solution 解答：Submission #15474499 - M-SOLUTIONS Programming Contest 2020 解法：追加する線路は集落を通るとしてよい。集落を通らない線路は「移動させてもコストが変わらない」「片方に移動させるとコスト増、もう片方に移動させるとコ…

問題：No.1103 Directed Length Sum - yukicoder 解答：#516999 (C++14) No.1103 Directed Length Sum - yukicoder 解法：木DP。 dp1[p]：頂点p以下の各頂点同士のパス長合計 dp2[p]：頂点p以下の頂点数合計 dp3[p]：頂点pと頂点p以下の頂点を結ぶパス長合計…

問題：C - 偶然ジェネレータ 解答：Submission #15324937 - AtCoder Regular Contest 036 解法：作成された文字列について前から文字を見てゆき、1なら+1、0なら-1する変数xを準備する。max(x) - min(x)がK以下ならその文字列は採用される。 このような文字…

問題：C - 暗闇帰り道 解答：Submission #15293678 - AtCoder Regular Contest 003 解法：「明るさの最小値をxとしてゴールまでたどり着けるか」の二分探索をやる。各試行では、グリッドグラフでダイクストラ法を行う。

問題：C - 幼稚園児高橋君 解答：Submission #15266646 - AtCoder Regular Contest 039 解法：例えば辿ったマスを記憶しておき、辿ったマスへ移動した場合はもう一回移動する、のような解法だとO(N2)でTLE。 Dancing Linksという典型的なテクニックがあるら…

問題：C - 仕事計画 解答：Submission #15233951 - AtCoder Regular Contest 032 解法：区間スケジュールで最も多くの仕事をこなすには、終了時間の速い順に仕事をソートし、貪欲に仕事を選んでゆけばよい。 ただしこの問題では、仕事の数が同数の場合は選ん…

問題：F - Intervals on Tree 解答：Submission #15077700 - AtCoder Beginner Contest 173 解法：超重要な公式として「森の連結成分 = 頂点数 - 辺数」がある。これはn個の頂点から1つずつ辺を増やすことで連結成分数が1つずつ減っていくことに対応する。ま…

問題：No.365 ジェンガソート - yukicoder 解答：#507527 (C++14) No.365 ジェンガソート - yukicoder 解法：嘘解法を量産しました。。 正解はn - 「数列を後ろから見て、n, n-1, n-2, ....と降順にとれる項数」です。 嘘解法としては、「数列を前から見て自…

問題：F - Removing Robots 解答：Submission #14877202 - AtCoder Beginner Contest 158 解法：ロボットを座標順にソートする。 f(i)：i番目のロボットを動かそうとしたとき、連鎖的にどこまでのロボットが動くか の関数とする。 このとき、iが直接動かせる…