問題ページ Problem - D - Codeforces 考えたこと 頂点iに住んでいる人が2往復以上したほうがいいことはない 日付について区間[l,l+k]で議論をすると考える lより前の最も安いチケットで頂点0へ行き、l+kよりもあとの最も安いチケットで頂点0から出発する 各…

問題ページ Problem - C - Codeforces 考えたこと 順列を全部試すのが無理なのはそれはそう 制約がだいぶでかいのでdpはつらそう 隣同士をswapするとコストがどう変化するかを考える i,i+1をswapするとコストが +c[i]-c[i+1] 変化する sortするような感じで…

問題ページ Problem - D - Codeforces sparseTableのverifyとして解いた。 解法 区間の左端lを固定して考えてみる 区間[l,r]についてmax(a) - min(b)を考えると単調に増えていく max(a) - min(b) の数列は [-2, -1, -1, 0, 0, 0, 0, 1, 2, 3] みたいな単調増…