2018-07-29から1日間の記事一覧

ARC044-B:最短路問題

問題 https://beta.atcoder.jp/contests/arc044/tasks/arc044_b N 頂点のグラフが与えられる。頂点 1 から頂点 i への最短路を a_i とするように辺を張るとき、辺の張り方は何通りか求めよ。 考え方 自明なケースを除く。まず 1 から 1 への最短路は 0 であ…

SoundHoundコン本戦-B:Neutralize

問題 https://atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_b 考え方 の閉区間をすべて にする。という操作の性質をフルに用いる。 DPを考える。 の最大値 と定義する。このとき操作を考えて、 の更新を考える…