問題 http://codeforces.com/contest/843/problem/D 解法 最初にダイクストラで距離を求めておき、各クエリごとにダイクストラで追加で増えた分の距離を計算して加算していく。各クエリごとに距離は 1 しか増えないので、キューを距離の数だけ用意すれば、ク…

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day2&pid=G 解法 ワーシャルフロイドと巡回セールスマン問題の bit DP で、ある町の部分集合を回って戻ってくるのにかかるコストを前計算しておく。さらに、町の集合を の 2 つに…

問題 AIZU ONLINE JUDGE 解法 2次元のBITを貼る。 コード import java.util.Scanner import scala.collection.mutable.ArrayBuffer object Main extends App { val in = new Scanner(System.in) val H = in.nextInt() val W = in.nextInt() val T = in.nextI…

問題 Matryoshka Doll | Aizu Online Judge 解法 取り込まれた人形のコストを 0 として、取り込まれていない人形のコストはそのまま結果に加えるように、最小費用流のグラフを作る。 コード import java.util.Scanner import scala.collection.mutable impor…

問題 https://beta.atcoder.jp/contests/arc082/tasks/arc082_d 解法 解説動画の通りにやった。最初に a 入っている時の t 秒後の砂の量は以下のように書ける。この をシミュレーションしていけば良い。 コード use std::io; use std::str; use std::usize; …

問題 https://beta.atcoder.jp/contests/arc082/tasks/arc082_c 解法 解説の通りにやった。 の意味するところを考える。これは凸包が S となるような部分集合の数である。よって求める答えは各凸包について部分集合の数を数えていけば良いが、それは難しいの…