会津合宿 2017 2 日目 G : Picnic
解法
ワーシャルフロイドと巡回セールスマン問題の bit DP で、ある町の部分集合を回って戻ってくるのにかかるコストを前計算しておく。
さらに、町の集合を の 2 つに分け、各集合のうちの部分集合を回った時に得られる幸福度を、個数制約付きナップサック問題をといて求める。
すると、 の部分集合と の部分集合を組み合わせることで、ある部分集合の最大値を求めることができる。
コード
import java.util.Scanner object Main { def main(args: Array[String]): Unit = { val in = new Scanner(System.in) val N = in.nextInt() val X = in.nextInt() val Y = in.nextInt() val foods = (for (_ <- 0 until N) yield { val K = in.nextInt() (for (_ <- 0 until K) yield { val a = in.nextInt() val b = in.nextInt() val c = in.nextInt() (a, b, c) }).toArray }).toArray val dist = (for (_ <- 0 until N) yield (for (_ <- 0 until N) yield in.nextInt()).toArray).toArray for { k <- 0 until N i <- 0 until N j <- 0 until N } dist(i)(j) = math.min(dist(i)(j), dist(i)(k) + dist(k)(j)) val cost = Array.fill(1 << (N + 1), N + 1)(Int.MaxValue / 2) cost(1)(0) = 0 for { mask <- 0 until (1 << N) current <- 0 until N next <- 1 until (N + 1) if (mask & (1 << current)) != 0 if (mask & (1 << next)) == 0 } { val nextMask = mask | (1 << next) cost(nextMask)(next) = math.min(cost(nextMask)(next), cost(mask)(current) + dist(current)(next % N)) } val bottom = N / 2 val top = N - bottom val deq = new Array[Int](1000000) val deqv = new Array[Int](1000000) def knapsack(mask: Int, dp: Array[Int]): Unit = { dp(0) = 0 for { i <- 0 until N if (mask & (1 << i)) != 0 (price, value, remain) <- foods(i) a <- 0 until price } { var s = 0 var t = 0 var num = 0 while (num * price <= (Y - a)) { val v = dp(num * price + a) - num * value while (s < t && deqv(t - 1) <= v) { t -= 1 } deq(t) = num deqv(t) = v t += 1 dp(num * price + a) = deqv(s) + num * value if (deq(s) == num - remain) { s += 1 } num += 1 } } for { i <- 1 to Y } { dp(i) = math.max(dp(i), dp(i - 1)) } } val bottomDp = Array.fill[Int](1 << bottom, Y + 1)(-1) val topDp = Array.fill[Int](1 << top, Y + 1)(-1) for (mask <- 0 until (1 << bottom)) { knapsack(mask, bottomDp(mask)) } for (mask <- 0 until (1 << top)) { knapsack(mask << bottom, topDp(mask)) } var max = 0 for { mask <- 0 until (1 << N) } { val moveCost = cost(mask | (1 << N))(N) val budget = math.min(Y, X - moveCost) val bottomMask = mask & ((1 << bottom) - 1) val topMask = mask >> bottom if (budget > 0) { for { bottomBudget <- 0 to budget } { max = math.max(max, bottomDp(bottomMask)(bottomBudget) + topDp(topMask)(budget - bottomBudget)) } } } println(max) } }
会津合宿 2017 3 日目 E : Taiyaki-Master and Eater
解法
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.nextInt() val Q = in.nextInt() var queries = new ArrayBuffer[(Int, Int, Int, Int, Int, Int)]() for (_ <- 0 until Q) { val t = in.nextInt() val c = in.nextInt() val h = in.nextInt() val w = in.nextInt() val (h2, w2) = if (c == 2) { (in.nextInt(), in.nextInt()) } else { (0, 0) } queries.append((t, c, h, w, h2, w2)) if (c == 0) { // 焼き上がり queries.append((t + T, -1, h, w, h2, w2)) } } queries = queries.sortBy(q => (q._1, q._2)) val f1 = new Fenwick2D(H, W) val f2 = new Fenwick2D(H, W) queries.foreach { case (_, c, h, w, h2, w2) => c match { case -1 => // 1->2 if (f1.get(h, w) != 0) { f1.update(h, w, 0) f2.update(h, w, 1) } case 0 => // 0->1 f1.update(h, w, 1) case 1 => // 2->0 f2.update(h, w, 0) case 2 => // count val a = f2.sum(h, w, h2, w2) val b = f1.sum(h, w, h2, w2) println(s"$a $b") } } } /** * 1-indexed 2-dimensional Fenwick's tree * * @param h height * @param w width */ class Fenwick2D(h: Int, w: Int) { val N: Int = h + 1 val M: Int = w + 1 val data: Array[Array[Long]] = Array.fill[Long](N + 1, M + 1)(0) def add(x: Int, y: Int, v: Long): Unit = { var i = x while (i <= N) { var j = y while (j <= M) { data(i)(j) += v j += j & -j } i += i & -i } } def update(x: Int, y: Int, v: Long): Unit = add(x, y, v - sum(x, y, x, y)) def get(x: Int, y: Int): Long = sum(x, y, x, y) def sum(x0: Int, y0: Int, x1: Int, y1: Int): Long = { def partialSum(x: Int, y: Int): Long = { var res = 0L var i = x while (i > 0) { var j = y while (j > 0) { res += data(i)(j) j -= j & -j } i -= i & -i } res } partialSum(x1, y1) - partialSum(x0 - 1, y1) - partialSum(x1, y0 - 1) + partialSum(x0 - 1, y0 - 1) } }
AOJ 2828: Matryoshka Doll
解法
取り込まれた人形のコストを 0 として、取り込まれていない人形のコストはそのまま結果に加えるように、最小費用流のグラフを作る。
コード
import java.util.Scanner import scala.collection.mutable import scala.collection.mutable.ArrayBuffer object Main extends App { val in = new Scanner(System.in) def solve(n: Int): Long = { val xyz = (for (_ <- 0 until n) yield { Array(in.nextInt(), in.nextInt(), in.nextInt()).sorted }).toArray val source = n * 2 val sink = source + 1 val minimumCostFlow = new MinimumCostFlow(sink + 1) for { i <- 0 until n j <- 0 until n if i != j if xyz(i)(0) < xyz(j)(0) if xyz(i)(1) < xyz(j)(1) if xyz(i)(2) < xyz(j)(2) } { minimumCostFlow.addEdge(i, n + j, 1, 0) } for (i <- 0 until n) { minimumCostFlow.addEdge(source, i, 1, 0) minimumCostFlow.addEdge(i, sink, 1, xyz(i)(0) * xyz(i)(1) * xyz(i)(2)) minimumCostFlow.addEdge(i + n, sink, 1, 0) } minimumCostFlow.calculateCost(source, sink, n) } def loop(): Unit = { while (true) { val n = in.nextInt() if (n == 0) { return } val ans = solve(n) println(ans) } } loop() } class Edge(val to: Int, var cap: Long, val cost: Long, val rev: Int) class MinimumCostFlow(V: Int) { val graph: Array[ArrayBuffer[Edge]] = (for (_ <- 0 until V) yield new ArrayBuffer[Edge]()).toArray val prevV = new Array[Int](V) val prevE = new Array[Int](V) def addEdge(from: Int, to: Int, cap: Long, cost: Long): Unit = { graph(from).append(new Edge(to, cap, cost, graph(to).size)) graph(to).append(new Edge(from, 0, -cost, graph(from).size - 1)) } def calculateCost(source: Int, sink: Int, flow: Long): Long = { val INF = Long.MaxValue / 2 var cost = 0L var residue = flow val potential = new Array[Long](V) while (residue > 0) { val dist = Array.fill[Long](V)(INF) dist(source) = 0 val queue = mutable.PriorityQueue.empty[(Long, Int)](implicitly[Ordering[(Long, Int)]].reverse) queue.enqueue((0, source)) while (queue.nonEmpty) { val p = queue.dequeue() val v = p._2 if (dist(v) >= p._1) { for (i <- graph(v).indices) { val e = graph(v)(i) val u = e.to if (e.cap > 0 && dist(u) > dist(v) + e.cost + potential(v) - potential(u)) { dist(u) = dist(v) + e.cost + potential(v) - potential(u) prevV(u) = v prevE(u) = i queue.enqueue((dist(u), u)) } } } } if (dist(sink) == INF) { return -1 } for (v <- 0 until V) { potential(v) += dist(v) } var d = residue var v = sink while (v != source) { d = math.min(d, graph(prevV(v))(prevE(v)).cap) v = prevV(v) } residue -= d cost += d * potential(sink) v = sink while (v != source) { val e = graph(prevV(v))(prevE(v)) e.cap -= d graph(v)(e.rev).cap += d v = prevV(v) } } return cost } }
ARC082 F - Sandglass
解法
解説動画の通りにやった。
最初に a 入っている時の t 秒後の砂の量は以下のように書ける。
この をシミュレーションしていけば良い。
コード
use std::io; use std::str; use std::usize; use std::cmp; static INF: i32 = 2000000000; fn main() { let x = read_values::<i32>()[0]; let k = read_values::<usize>()[0]; let r = { let mut r = read_values::<i32>(); r.push(INF); r }; let q = read_values::<usize>()[0]; let (t, a) = { let mut t = vec![INF; q + 1]; let mut a = vec![INF; q + 1]; for i in 0..q { let v = read_values::<i32>(); t[i] = v[0]; a[i] = v[1]; } (t, a) }; let mut y = 0; let mut x1 = 0; let mut x2 = x; let mut upper = true; let mut flat = false; let mut flat_height = 0; let mut r_head = 0; let mut t_head = 0; let mut prev_time = 0; while r_head < k || t_head < q { if r[r_head] < t[t_head] { // turn let time = r[r_head] - prev_time; if upper { y -= time; if y < 0 && x1 < -y { x1 = -y; } } else { y += time; if y > 0 && x2 > x - y { x2 = x - y; } } if flat { if upper { flat_height -= time; } else { flat_height += time; } flat_height = cmp::max(flat_height, 0); flat_height = cmp::min(flat_height, x); } else if x1 >= x2 { flat = true; if upper { flat_height = 0; } else { flat_height = x; } } prev_time = r[r_head]; upper = !upper; r_head += 1; } else { // query let time = t[t_head] - prev_time; let mut ans = if a[t_head] < x1 { x1 + y } else if x2 < a[t_head] { x2 + y } else { a[t_head] + y }; if upper { ans -= time; } else { ans += time; } if flat { ans = flat_height; if upper { ans -= time; } else { ans += time; } } ans = cmp::max(0, ans); ans = cmp::min(x, ans); println!("{}", ans); t_head += 1; } } } fn read_line() -> String { let stdin = io::stdin(); let mut buf = String::new(); stdin.read_line(&mut buf).unwrap(); buf } fn read_values<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug { read_line() .split(' ') .map(|a| a.trim().parse().unwrap()) .collect() }
ARC082 E - ConvexScore
解法
解説の通りにやった。
の意味するところを考える。これは凸包が S となるような部分集合の数である。
よって求める答えは各凸包について部分集合の数を数えていけば良いが、それは難しいので、全ての部分集合から、凸包が正の面積とならない部分集合を除けば良い。
コード
use std::io; use std::str; use std::usize; use std::cmp; fn mod_pow(x: i64, mut exp: i64, modulo: i64) -> i64 { let mut result = 1; let mut cur = x; while exp > 0 { if exp & 1 == 1 { result = (result * cur) % modulo; } cur = (cur * cur) % modulo; exp >>= 1; } result } fn main() { let modulo = 998244353; let n = read_values::<usize>()[0]; let (x, y) = { let mut x = vec![0; n]; let mut y = vec![0; n]; for i in 0..n { let v = read_values::<i64>(); x[i] = v[0]; y[i] = v[1]; } (x, y) }; let mut ans = mod_pow(2, n as i64, modulo); ans -= 1; ans -= n as i64; ans = (ans + modulo) % modulo; // 両端がそれぞれ i, j となるような線分に乗っている点の数を数える for i in 0..n { for j in (i + 1)..n { let dx = x[i] - x[j]; let dy = y[i] - y[j]; let mut count = 0; let mut left = i; let mut right = j; for k in 0..n { let kx = x[i] - x[k]; let ky = y[i] - y[k]; if dx * ky - kx * dy == 0 { left = cmp::min(left, k); right = cmp::max(right, k); count += 1; } } // 両端が i, j でない時はスルー if left != i || right != j { continue; } // 凸包の面積が 0 であるような部分集合のサイズ let subset = mod_pow(2, count, modulo) - count - 1; ans = (ans + modulo - subset) % modulo; } } println!("{}", ans); } fn read_line() -> String { let stdin = io::stdin(); let mut buf = String::new(); stdin.read_line(&mut buf).unwrap(); buf } fn read_values<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug { read_line() .split(' ') .map(|a| a.trim().parse().unwrap()) .collect() }
ARC080 E - Young Maids
Rust の練習
解法
逆から考えて、最後に先頭に追加される 2 つの数を考える。これらを前から順番に とすると、i は偶数、j は奇数であり、かつ、 が成り立つことがわかる。よって、この条件を満たす i, j の中で が最小になり、かつ、その中で が最小になるような i, j を決めることで、先頭の 2 つは決まる。
このような が最後に残るためには、 のいずれかを満たす が全て取り除かれている必要があるが、隣り合っている数を取り除くため、これらの各区間の中で独立に取り除くことになる。
よって、解法としては、
コード
use std::io; use std::io::{Read, Stdin}; use std::str; use std::str::FromStr; use std::usize; use std::cmp; use std::fmt::Debug; use std::i64::MAX; use std::collections::BinaryHeap; use std::cmp::Ordering; #[derive(Debug, Copy, Clone, Eq, PartialEq)] struct Candidate { minimum: i64, from: usize, until: usize, } impl Ord for Candidate { fn cmp(&self, other: &Candidate) -> Ordering { other.minimum.cmp(&self.minimum) } } impl PartialOrd for Candidate { fn partial_cmp(&self, other: &Candidate) -> Option<Ordering> { Some(self.cmp(other)) } } fn main() { let mut sc = Scanner::new(); let n = sc.parse::<usize>(); let arr = (0..n).map(|_| { sc.parse::<i64>() - 1 }).collect::<Vec<_>>(); let mut rev = vec![0; n]; for i in 0..n { rev[arr[i] as usize] = i; } let mut even_rmq = RangeMinimumQuery::new(n); let mut odd_rmq = RangeMinimumQuery::new(n); for i in 0..n { if i % 2 == 0 { even_rmq.update(i, arr[i]); } else { odd_rmq.update(i, arr[i]); } } let mut ans = Vec::new(); let mut heap = BinaryHeap::new(); heap.push(Candidate { minimum: 0, from: 0, until: n }); while !heap.is_empty() { let s: Candidate = heap.pop().unwrap(); let from = s.from; let until = s.until; let (head, tail) = { let (ref rmq1, ref rmq2) = if from % 2 == 0 { (&even_rmq, &odd_rmq) } else { (&odd_rmq, &even_rmq) }; let minimum_value = rmq1.query(from, until); let minimum_index = rev[minimum_value as usize]; let pair = rmq2.query(minimum_index + 1, until); let pair_index = rev[pair as usize]; (minimum_index, pair_index) }; ans.push(arr[head]); ans.push(arr[tail]); for &(left, right) in &[(from, head), (head + 1, tail), (tail + 1, until)] { if left >= right { continue; } let minimum = if left % 2 == 0 { even_rmq.query(left, right) } else { odd_rmq.query(left, right) }; heap.push(Candidate { minimum: minimum, from: left, until: right }); } } for t in &ans { print!("{} ", t + 1); } println!(); } pub struct RangeMinimumQuery { seg: Vec<i64>, n: usize, } impl RangeMinimumQuery { pub fn new(size: usize) -> RangeMinimumQuery { let mut m = 1; while m <= size { m *= 2; } RangeMinimumQuery { seg: vec![MAX; m * 2], n: m, } } pub fn update(&mut self, mut k: usize, value: i64) { k += self.n - 1; self.seg[k] = value; while k > 0 { k = (k - 1) / 2; self.seg[k] = cmp::min(self.seg[k * 2 + 1], self.seg[k * 2 + 2]); } } /// Get the minimum value in the array in the range [a, b) /// /// # Panics /// /// Panics if `a >= b`. pub fn query(&self, a: usize, b: usize) -> i64 { assert!(a < b); return self.query_range(a, b, 0, 0, self.n); } pub fn query_range(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> i64 { if r <= a || b <= l { return MAX; } if a <= l && r <= b { return self.seg[k]; } let x = self.query_range(a, b, k * 2 + 1, l, (l + r) / 2); let y = self.query_range(a, b, k * 2 + 2, (l + r) / 2, r); cmp::min(x, y) } } struct Scanner { stdin: Stdin, buf: Vec<u8>, } impl Scanner { fn new() -> Scanner { Scanner { stdin: io::stdin(), buf: Vec::with_capacity(256), } } fn parse<T: FromStr>(&mut self) -> T where <T as FromStr>::Err: Debug { self.buf.clear(); let mut it = self.stdin.lock().bytes(); let mut c = it.next().unwrap().unwrap(); while c == ' ' as u8 || c == '\n' as u8 { c = it.next().unwrap().unwrap(); } while !(c == ' ' as u8 || c == '\n' as u8) { self.buf.push(c); c = it.next().unwrap().unwrap(); } str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap() } }
CS Academy Round #34 Point in Kgon
復習
コード
import java.util.Scanner; public class Main { private static final int MOD = (int) (1e9 + 7); public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int K = in.nextInt(); long[] x = new long[N * 2]; long[] y = new long[N * 2]; for (int i = 0; i < N; i++) { x[i] = in.nextInt(); y[i] = in.nextInt(); } int px = in.nextInt(); int py = in.nextInt(); for (int i = 0; i < N; i++) { x[i] -= px; y[i] -= py; x[i + N] = x[i]; y[i + N] = y[i]; } Combination combination = new Combination(N, MOD); long sum = 0; int bottom = 0; for (int i = 0; i < N; i++) { while (bottom + 1 < N * 2 && x[i] * y[bottom + 1] - y[i] * x[bottom + 1] >= 0) { bottom++; } int count = bottom - i; sum += combination.get(count, K - 1); sum %= MOD; } long ans = (combination.get(N, K) - sum + MOD) % MOD; System.out.println(ans); } static class Combination { private long[] fact; private long[] invFact; private int MOD; public Combination(int max, int MOD) { this.MOD = MOD; long[] inv = new long[max + 1]; fact = new long[max + 1]; invFact = new long[max + 1]; inv[1] = 1; for (int i = 2; i <= max; i++) { inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD; } fact[0] = invFact[0] = 1; for (int i = 1; i <= max; i++) { fact[i] = fact[i - 1] * i % MOD; } for (int i = 1; i <= max; i++) { invFact[i] = invFact[i - 1] * inv[i] % MOD; } } public long get(int x, int y) { if (x < y) { return 0; } return fact[x] * invFact[y] % MOD * invFact[x - y] % MOD; } } }