AtCoder Regular Contest 073 E - Ball Coloring
解法
解説のとおりだが、個人的には理解が難しかった。(分かると簡単シリーズ)
最小のボールが青、最大のボールが赤のとき
最小のボールを持つ青は、残りのボールをできるだけ小さくしたい。最大のボールを持つ赤は残りのボールをできるだけ大きくしたい。なので、各ペアの小さいボールを青に、大きいボールを赤に塗れば良い。
最小のボールも最大のボールも赤に塗られているとき
まずは各ペアの小さい方のボールを青に塗る。青側の最小値を大きく、最大値を小さくしたいお気持ちだが、最大値は小さくはならない(大きくなることはある)。なので、最小値を大きくすることだけを考える。
各ペアを、小さい方のボールの昇順にソートしたとき、 i 番目のペアでは小さいほうが青に、大きい方が赤に塗られているが、これを入れ替えることを検討する。 k 番目のペアの小さい方を青にしたままの場合、 k+1 番目以降のペアをいくら入れ替えても青側の最小値は大きくならないので、i 番目のペアを入れ替えることを検討している時は、それより前のペアは全て入れ替わっていると考えて良い。
i 番目のペアを入れ替えた場合、青側のボールは {1〜i 番目のペアの大きい方のボール}
+ {i+1〜n 番目のペアの小さい方のボール} になる。これらの最大値・最小値を求めれば、「i 番目まで入れ替えたときの求める値」が計算できるのでこれを 1 〜 n 番目まで計算すれば良い。
コード
use std::cmp; fn main() { let mut sc = Scanner::new(); let n = sc.read(); let mut x: Vec<usize> = vec![0; n]; let mut y: Vec<usize> = vec![0; n]; for i in 0..n { x[i] = sc.read(); y[i] = sc.read(); } let mut small = vec![]; let mut large = vec![]; for i in 0..n { small.push(cmp::min(x[i], y[i])); large.push(cmp::max(x[i], y[i])); } let &small_min = small.iter().min().unwrap(); let &small_max = small.iter().max().unwrap(); let &large_min = large.iter().min().unwrap(); let &large_max = large.iter().max().unwrap(); let mut ans = (small_max - small_min) * (large_max - large_min); let worst_side = large_max - small_min; let mut max = small_max; let mut min = 1e15 as usize; let mut v = vec![]; for i in 0..n { v.push((small[i], large[i])); } v.sort(); for i in 0..(n - 1) { let (_, large) = v[i]; let (next_small, _) = v[i + 1]; min = cmp::min(min, large); max = cmp::max(max, large); let tmp_min = cmp::min(min, next_small); ans = cmp::min(ans, (max - tmp_min) * worst_side); } println!("{}", ans); } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn usize_read(&mut self) -> usize { self.read() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } }
AtCoder Regular Contest 077 E - guruguru
コード
use std::cmp; use std::collections::BinaryHeap; #[derive(Copy, Clone, Eq, PartialEq, Debug)] struct Seg { head: usize, tail: usize, } impl Ord for Seg { fn cmp(&self, other: &Seg) -> cmp::Ordering { other.tail.cmp(&self.tail) } } impl PartialOrd for Seg { fn partial_cmp(&self, other: &Seg) -> Option<cmp::Ordering> { Some(self.cmp(other)) } } fn main() { let mut sc = Scanner::new(); let n = sc.read(); let m = sc.read(); let a: Vec<usize> = sc.read_vec(n); let mut tails: Vec<Vec<usize>> = vec![vec![]; m]; let mut total_distance = 0; let mut current_decrease = 0; let mut decreased_segments = BinaryHeap::new(); for i in 1..n { let from = a[i - 1] - 1; let to = a[i] - 1; let distance = (to + m - from) % m; total_distance += distance; if from > to { let warped = m - from - 1; current_decrease += warped; decreased_segments.push(Seg { head: from, tail: to, }); tails[from].push(to + m); } else { tails[from].push(to); } } let mut ans = total_distance - current_decrease; for x in 1..m { while let Some(Seg { head, tail }) = decreased_segments.pop() { if tail < x { assert!(tail == x - 1); current_decrease -= (tail + m - head) % m - 1; } else { decreased_segments.push(Seg { head: head, tail: tail, }); break; } } current_decrease += decreased_segments.len(); ans = cmp::min(ans, total_distance - current_decrease); for &tail in tails[x - 1].iter() { decreased_segments.push(Seg { head: x - 1, tail: tail, }); } } println!("{}", ans); } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn usize_read(&mut self) -> usize { self.read() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } }
C - Not Too Close SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open)
解法
解説が全く理解できなかったので下記ブログを参考にした。ありがとうございます。
http://fluffyowl.hatenablog.com/entry/2018/07/31/000800
dp[d][i][j] := 頂点 1 からの距離が d となる頂点までグラフを構築したとき、グラフの頂点数が i で、その中で頂点 1 からの距離が d となる頂点の個数が j であるグラフの組み合わせ
を考える。
距離 d-1 まで構築し終えたとして、グラフ全体の頂点数が used 個、頂点 1 からの距離が d-1 の頂点の数が last 個だとする。
このとき使われていない頂点の数 u は
と表される。(距離が D 以下なら使われていない頂点2は使われていないが、そうでない場合は使われているため。)
また、距離 d の頂点として新たにグラフに使用する頂点の数を using 個とすると、新たにグラフに使用する頂点を選ぶ組み合わせ C は
と表される。 (d=D のときは 2 を必ずグラフに使わなければならないため。)
新たにグラフに使用される using 個の頂点は距離 d となるので、 last 個の頂点のいずれかから辺が張られているはずである。よって using 個の各頂点について、 last 個の頂点への辺の貼り方はそれぞれ 通りあるはずである。 (last 個の頂点のどれに辺を張っても良いが、必ず 1 本は張らなければならないため。)なので last 個の頂点と using この頂点のみからなるサブグラフの組み合わせ E は 通りになる。
新たに追加される using この頂点の間では好きなだけ辺を張って良い。(これら using 個の頂点への頂点 1 からの最短距離は d で変わらないので。)貼りうる辺の本数は なので、組み合わせは 通りになる。
よって dp の更新式は
みたいな感じになる。(雰囲気で式を書いているので数学的な表記じゃないのは許してください)
コード
use std::ops::{Add, AddAssign, Mul, MulAssign, Rem, Sub}; const MOD: usize = 1e9 as usize + 7; fn main() { let mut sc = Scanner::new(); let n: usize = sc.read(); let d: usize = sc.read(); let combination = Combination::new(n, MOD); let mut dp = vec![vec![vec![ModInt::new(0); n + 1]; n + 1]; n]; dp[0][1][1] = ModInt::new(1); for distance in 1..n { for using in 1..(n + 1) { for used in 1..(n + 1) { if using + used > n { continue; } for last in 1..(n + 1) { let unused = if distance <= d { n - used - 1 } else { n - used }; let using_not_2 = if distance == d { using - 1 } else { using }; if unused < using_not_2 { continue; } let combination = combination.get(unused, using_not_2); let edges_from_last_to_using = mod_pow((1 << last) - 1, using); let possible_edge_num_in_using_sub_graph = using * (using - 1) / 2; let sub_graphs_of_using = mod_pow(2, possible_edge_num_in_using_sub_graph); dp[distance][using + used][using] += dp[distance - 1][used][last] * combination * edges_from_last_to_using * sub_graphs_of_using; } } } } let mut ans = ModInt::new(0); for distance in d..n { for used in (distance + 1)..(n + 1) { for last in 0..(n + 1) { let unconnected_sub_graph = if used + 1 >= n { ModInt::new(1) } else { mod_pow(2, (n - used) * (n - used - 1) / 2) }; ans += dp[distance][used][last] * unconnected_sub_graph; } } } println!("{}", ans.value); } fn mod_pow(x: usize, e: usize) -> ModInt<usize> { let mut result = ModInt::new(1); let mut cur = ModInt::new(x); let mut e = e; while e > 0 { if e & 1 != 0 { result = result * cur; } e /= 2; cur = cur * cur; } result } #[derive(Copy)] pub struct ModInt<T> { value: T, modulo: T, } impl<T> Clone for ModInt<T> where T: Copy, { fn clone(&self) -> Self { ModInt { value: self.value, modulo: self.modulo, } } fn clone_from(&mut self, source: &ModInt<T>) { self.value = source.value; self.modulo = source.modulo; } } impl<T> Add<ModInt<T>> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { type Output = ModInt<T>; fn add(self, rhs: ModInt<T>) -> ModInt<T> { self + rhs.value } } impl<T> Add<T> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { type Output = ModInt<T>; fn add(self, rhs: T) -> ModInt<T> { let m = self.modulo; let mut t = rhs + self.value; if t > m { t = t - m; } ModInt { value: t, modulo: self.modulo, } } } impl<T> Sub<T> for ModInt<T> where T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>, { type Output = ModInt<T>; fn sub(self, rhs: T) -> ModInt<T> { let rhs = if rhs >= self.modulo { rhs % self.modulo } else { rhs }; let value = if self.value < rhs { self.value + self.modulo } else { self.value }; ModInt { value: value - rhs, modulo: self.modulo, } } } impl<T> Sub<ModInt<T>> for ModInt<T> where T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>, { type Output = ModInt<T>; fn sub(self, rhs: ModInt<T>) -> ModInt<T> { self - rhs.value } } impl<T> AddAssign<T> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { fn add_assign(&mut self, other: T) { *self = *self + other; } } impl<T> AddAssign<ModInt<T>> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { fn add_assign(&mut self, other: ModInt<T>) { *self = *self + other; } } impl<T> Mul<ModInt<T>> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { type Output = ModInt<T>; fn mul(self, rhs: ModInt<T>) -> ModInt<T> { self * rhs.value } } impl<T> Mul<T> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { type Output = ModInt<T>; fn mul(self, rhs: T) -> ModInt<T> { let t = (self.value * rhs) % self.modulo; ModInt { value: t, modulo: self.modulo, } } } impl<T> MulAssign<T> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { fn mul_assign(&mut self, rhs: T) { *self = *self * rhs; } } impl<T> MulAssign<ModInt<T>> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { fn mul_assign(&mut self, rhs: ModInt<T>) { *self = *self * rhs; } } impl ModInt<usize> { pub fn new(value: usize) -> ModInt<usize> { ModInt { value: value, modulo: MOD, } } } pub struct Combination { fact: Vec<usize>, inv_fact: Vec<usize>, modulo: usize, } impl Combination { pub fn new(max: usize, modulo: usize) -> Combination { let mut inv = vec![0; max + 1]; let mut fact = vec![0; max + 1]; let mut inv_fact = vec![0; max + 1]; inv[1] = 1; for i in 2..(max + 1) { inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo; } fact[0] = 1; inv_fact[0] = 1; for i in 0..max { fact[i + 1] = fact[i] * (i + 1) % modulo; } for i in 0..max { inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo; } Combination { fact: fact, inv_fact: inv_fact, modulo: modulo, } } pub fn get(&self, x: usize, y: usize) -> ModInt<usize> { assert!(x >= y); ModInt::new( self.fact[x] * self.inv_fact[y] % self.modulo * self.inv_fact[x - y] % self.modulo, ) } } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn usize_read(&mut self) -> usize { self.read() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } }
CS Academy: Growing Segment
問題
https://csacademy.com/contest/archive/task/growing-segment/
解法
- 削除しても大丈夫な辺を下から見ていく
- x[i] -> x[i+1] を削除するときことを考える
- x[i+1] は削除して問題ないので消す。
- x[i+2] は消せるか? (x[i] をカバーしたときに自動的に x[i-2] もカバーされるか?)
- x[i+2] を消せるとき
- x[i+2] を消す
- x[i] -> x[i+3] に辺を張る
- x[i+2] が消せないとき
- x[i] を消す
- x[i-1] -> x[i+2] に辺を張る
コード
use std::collections::BTreeSet; fn main() { let mut sc = Scanner::new(); let n = sc.read(); let q = sc.read(); let mut x: Vec<i64> = vec![0]; for _ in 0..n { let t = sc.read::<i64>(); if x[x.len() - 1] == t { continue; } if x.len() >= 2 && (x[x.len() - 2] < x[x.len() - 1]) == (x[x.len() - 1] < t) { x.pop(); } x.push(t); } let mut current_difference = 0; if x.len() >= 2 && x[1] < 0 { current_difference -= x[1]; x.remove(0); for x in x.iter_mut() { *x += current_difference; } } // x[even] < x[odd] > x[even] < x[odd] ... let mut index_set = (0..x.len()).collect::<BTreeSet<_>>(); let mut edges = BTreeSet::new(); let mut distance = vec![0; x.len() - 1]; for i in 1..x.len() { distance[i - 1] = (x[i] - x[i - 1]).abs(); current_difference += distance[i - 1]; edges.insert((distance[i - 1], i - 1)); } let mut queries = vec![]; for i in 0..q { queries.push((sc.read::<i64>(), i)); } queries.sort(); let mut prev_query = 0; let mut ans = vec![0; q]; for &(query, ans_index) in queries.iter() { while let Some(&(_, edge_idx)) = edges.first() { let edge_length = distance[edge_idx]; if edge_length > query { break; } edges.remove(&(edge_length, edge_idx)); current_difference -= distance[edge_idx] - prev_query; let &next_idx = index_set.range((edge_idx + 1)..).next().unwrap(); if next_idx < *index_set.last().unwrap() { edges.remove(&(distance[next_idx], next_idx)); current_difference -= distance[next_idx] - prev_query; } index_set.remove(&next_idx); let it = index_set.range((edge_idx + 1)..).next().cloned(); if it.is_none() { continue; } let next_next_idx = it.unwrap(); assert!(edge_idx % 2 == next_next_idx % 2); if (edge_idx % 2 == 0 && x[next_next_idx] >= x[edge_idx]) || (edge_idx % 2 == 1 && x[next_next_idx] <= x[edge_idx]) { // When next_next_idx is removable, if next_next_idx < *index_set.last().unwrap() { edges.remove(&(distance[next_next_idx], next_next_idx)); current_difference -= distance[next_next_idx] - prev_query; } index_set.remove(&next_next_idx); match index_set.range((edge_idx + 1)..).next() { Some(&next_idx) => { distance[edge_idx] = (x[edge_idx] - x[next_idx]).abs(); edges.insert((distance[edge_idx], edge_idx)); current_difference += distance[edge_idx] - prev_query; } _ => {} } } else { // When next_next_idx can not be removed, assert!(index_set.remove(&edge_idx)); match index_set.range(..next_next_idx).next_back() { Some(&prev_idx) => { edges.remove(&(distance[prev_idx], prev_idx)); current_difference -= distance[prev_idx] - prev_query; distance[prev_idx] = (x[prev_idx] - x[next_next_idx]).abs(); edges.insert((distance[prev_idx], prev_idx)); current_difference += distance[prev_idx] - prev_query; } _ => { current_difference += (x[edge_idx] - x[next_next_idx]).abs(); } } } } current_difference -= (query - prev_query) * edges.len() as i64; ans[ans_index] = current_difference; prev_query = query; } for &ans in ans.iter() { println!("{}", ans); } } trait FirstLastElement<K> { fn first(&self) -> Option<&K>; fn last(&self) -> Option<&K>; } impl<K> FirstLastElement<K> for BTreeSet<K> { fn first(&self) -> Option<&K> { self.iter().next() } fn last(&self) -> Option<&K> { self.iter().next_back() } } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn usize_read(&mut self) -> usize { self.read() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } }
SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open) E - Hash Swapping
解法
セグメント木の子ノード j に を入れておき、合計値を求める際に の逆元をかけることでハッシュを取り出せるようにする。各ノードは左右の子ノードへのポインタ(ポインタ操作は Rust で安全にやろうとすると重くなるので、実際には配列のインデックス)をそれぞれ持っていて、更新範囲内に含まれていたらポインタを張り替えることで swap クエリを処理する。
コード
const EXP: usize = 1e6 as usize; const MOD: usize = 1e9 as usize + 7; #[derive(Clone, Debug)] struct Node { left: usize, right: usize, from: usize, to: usize, sum: usize, } struct SegTree { nodes: Vec<Node>, total: usize, } impl SegTree { fn new(n: usize, m: usize) -> Self { let mut size = 1; while size <= n { size *= 2; } let total = size * 2; let mut seg = vec![ Node { left: 0, right: 0, from: 0, to: 0, sum: 0 }; total * m ]; for m in 0..m { let offset = total * m; init_ptr(&mut seg, 0, offset, 0, size - 1); } SegTree { nodes: seg, total: total, } } fn update(&mut self, pos: usize, value: usize, i: usize) { if self.nodes[pos].from == self.nodes[pos].to && self.nodes[pos].from == i { self.nodes[pos].sum = value; } else if self.nodes[pos].from <= i && i <= self.nodes[pos].to { let left = self.nodes[pos].left; let right = self.nodes[pos].right; self.update(left, value, i); self.update(right, value, i); self.nodes[pos].sum = (self.nodes[left].sum + self.nodes[right].sum) % MOD; } } fn sum(&self, from: usize, to: usize, pos: usize) -> usize { if to < self.nodes[pos].from || self.nodes[pos].to < from { 0 } else if from <= self.nodes[pos].from && self.nodes[pos].to <= to { self.nodes[pos].sum } else { let left = self.sum(from, to, self.nodes[pos].left); let right = self.sum(from, to, self.nodes[pos].right); (left + right) % MOD } } fn swap(&mut self, pos1: usize, pos2: usize, from: usize, to: usize) { let ptr1 = self.nodes[pos1].left; let ptr2 = self.nodes[pos2].left; if from <= self.nodes[ptr1].from && self.nodes[ptr1].to <= to { self.nodes[pos1].left = ptr2; self.nodes[pos2].left = ptr1; } else if !(to < self.nodes[ptr1].from || self.nodes[ptr1].to < from) { self.swap(ptr1, ptr2, from, to); } let ptr1 = self.nodes[pos1].right; let ptr2 = self.nodes[pos2].right; if from <= self.nodes[ptr1].from && self.nodes[ptr1].to <= to { self.nodes[pos1].right = ptr2; self.nodes[pos2].right = ptr1; } else if !(to < self.nodes[ptr1].from || self.nodes[ptr1].to < from) { self.swap(ptr1, ptr2, from, to); } let mut update = |pos: usize| { let left = self.nodes[pos].left; let right = self.nodes[pos].right; self.nodes[pos].sum = (self.nodes[left].sum + self.nodes[right].sum) % MOD; }; update(pos1); update(pos2); } } fn init_ptr(seg: &mut Vec<Node>, k: usize, offset: usize, from: usize, to: usize) { seg[k + offset].from = from; seg[k + offset].to = to; if from != to { let width = to + 1 - from; assert_eq!(width & 1, 0); seg[k + offset].left = 2 * k + 1 + offset; seg[k + offset].right = 2 * k + 2 + offset; init_ptr(seg, 2 * k + 1, offset, from, from + width / 2 - 1); init_ptr(seg, 2 * k + 2, offset, from + width / 2, to); } } fn solve(n: usize, s: &Vec<Vec<usize>>, q: &Vec<(usize, usize, usize, usize, usize)>) { let m = s.len(); let mut mod_pow = vec![0; n + 1]; mod_pow[0] = 1; mod_pow[1] = EXP; let mut mod_inv = vec![0; n + 1]; mod_inv[0] = 1; mod_inv[1] = mod_inverse(EXP, MOD); for i in 2..n { mod_pow[i] = (mod_pow[i - 1] * mod_pow[1]) % MOD; mod_inv[i] = (mod_inv[i - 1] * mod_inv[1]) % MOD; } let mut seg = SegTree::new(n, m); for m in 0..m { for i in 0..n { let pos = m * seg.total; seg.update(pos, (s[m][i] * mod_pow[i]) % MOD, i); } } for &(t, x, y, from, to) in q.iter() { if t == 1 { let pos1 = x * seg.total; let pos2 = y * seg.total; seg.swap(pos1, pos2, from, to); } else { let pos = x * seg.total; let sum = seg.sum(from, to, pos); println!("{}", (sum * mod_inv[from]) % MOD); } } } fn main() { let mut sc = Scanner::new(); let n = sc.read(); let m = sc.read(); let s: Vec<Vec<usize>> = (0..m) .map(|_| { sc.read::<String>() .chars() .map(|c| c as usize - 'a' as usize + 1) .collect() }) .collect(); let q = sc.read(); let q = (0..q) .map(|_| { let t = sc.read(); if t == 1 { ( t, sc.usize_read() - 1, sc.usize_read() - 1, sc.usize_read() - 1, sc.usize_read() - 1, ) } else { ( t, sc.usize_read() - 1, sc.usize_read(), sc.usize_read() - 1, sc.usize_read() - 1, ) } }) .collect(); solve(n, &s, &q); } fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) { assert!(a < b); if a == 0 { (b, 0, 1) } else { let (g, x, y) = extended_gcd(b % a, a); (g, y - (b / a) * x, x) } } fn mod_inverse(a: usize, modulo: usize) -> usize { let (g, x, _) = extended_gcd(a as i64, modulo as i64); assert!(g == 1); (x as usize) % modulo } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn usize_read(&mut self) -> usize { self.read() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } }
Rust でライブコーディングをした
これの LT 枠でライブコーディングをした。
動機
Rust は比較的難しい言語だと思う(ふわっと書いてふわっと動くタイプの言語ではない)ので、聴衆が自分でもできそうと思えるようなパフォーマンスをしたかった。
問題選定
Rust の標準ライブラリの公式ドキュメントにはダイクストラの実装が載っているので、これをコピペするだけで動くのを見せたいと考えた。 AOJ にはダイクストラをそのまま実装するための問題が用意されているが、それではあまりに味気ないので、本質的にはダイクストラをやるだけだが表面的には面白そうに見える問題を頑張って探した。
(探しても見つからなかったので、結局自分の印象に残っていた問題を思い出した)(僕が初めてダイクストラ法と出会った問題)
練習
本番前に練習をし、いくつかの問題点を見つけた。
- この問題では全ての頂点への最短距離を求める必要があるが、公式ドキュメントのものは終点までの最短経路のみを求めるので、微修正する必要がある。
- AtCoder のジャッジの Rust は 1.15.1 なので、そのままコピペすると
then_with
でコンパイルエラーになる。 - Edge が Clone を継承する必要がある。
- さり気なく
[#derive(Clone)]
を足す。
- さり気なく
- 標準入力が面倒。
- グラフが連結でないケースがテストに入っている。
本番
kenkooさんだ #rust_jp
— κeen (@blackenedgold) August 1, 2018
— Tsuzu (@Wp120_3238) 2018年8月1日
「どうせ自分の発表時間なくなるだろと思ってたので…」
— κeen (@blackenedgold) 2018年8月1日
#rust_jp
立川シネマシティの宣伝がwww #rust_jp
— Satoshi Kojima (@skoji) 2018年8月1日
— 電波椅子🐱 (@dempacat) 2018年8月1日
kenkooさんだ!!#rust_jp
— hello (@yomicerisier) 2018年8月1日
— hsjoihs@数情物化語 (@hsjoihs) 2018年8月1日
— おおた (@ota42y) 2018年8月1日
— おおた (@ota42y) 2018年8月1日
— えまのん (@emanon_was) 2018年8月1日
「今日家に帰ったら使える話をします」
— κeen (@blackenedgold) 2018年8月1日
#rust_jp
— なっぱ@パーフェクトドブマスター (@b7472) 2018年8月1日
「今すぐ5分以内にここでRustを使う話をします!!」 #rust_jp
— Satoshi Kojima (@skoji) 2018年8月1日
「スライドはない」「5分以内に使うRustを話します」 #rust_jp
— tjmmm (@norikakip) 2018年8月1日
— yuki (@helloyuk13) 2018年8月1日
— κeen (@blackenedgold) 2018年8月1日
「webアプリとか作るだけならPythonでいいんですよ!!」 #rust_jp
— Satoshi Kojima (@skoji) 2018年8月1日
— Tsuzu (@Wp120_3238) 2018年8月1日
atcoderの問題をライブコーディングして解くwwww #rust_jp
— おおた (@ota42y) 2018年8月1日
— 名有りさん (@naari_) 2018年8月1日
— κeen (@blackenedgold) 2018年8月1日
LTでAtCoderのC問題をライブコーディング。新しい #rust_jp
— 電波椅子🐱 (@dempacat) 2018年8月1日
ちゃんと時間は確保しますよ😅 #rust_jp
— どらやき (@dorayaki_kun) 2018年8月1日
「だいくすとら」を #rust_jp
— 目指せ黄色 (@matsu7874) 2018年8月1日
AtCoderのC問題をライブコーディングwww #rust_jp
— なっぱ@パーフェクトドブマスター (@b7472) 2018年8月1日
最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド | 高橋 直大 |本 | 通販 | Amazonhttps://t.co/EOUsiDiXa7#rust_jp
— κeen (@blackenedgold) 2018年8月1日
Atcoderのライブコーディングは面白すぎる#rust_jp
— hello (@yomicerisier) 2018年8月1日
標準入力の受け取りめんどいよねw #rust_jp
— yuki (@helloyuk13) 2018年8月1日
ダイクストラ弊社社員うるさいです。僕はうるさくないですが。 #rust_jp
— どらやき (@dorayaki_kun) 2018年8月1日
マイクOFF!! #rust_jp
— なっぱ@パーフェクトドブマスター (@b7472) 2018年8月1日
標準入力を受け取るのもコピペでやっていくことにした
「標準入力受け取るのはRustだとめんどくさいのでコピペします!!」 #rust_jp 勢いがある
— Satoshi Kojima (@skoji) 2018年8月1日
「標準入力を受け取るのがRustは面倒なのでコピペでいきます」 #rust_jp
— 電波椅子🐱 (@dempacat) 2018年8月1日
AtCoderライブコーディングが始まったw #rust_jp
— Tsuzu (@Wp120_3238) 2018年8月1日
ガルパンの宣伝からガチライブコーディングw テンションぱねーw #rust_jp
— えまのん (@emanon_was) 2018年8月1日
「みなさんも実装してください僕といっしょに!!!」 #rust_jp
— tjmmm (@norikakip) 2018年8月1日
「みなさん、今、僕と一緒に、実装してください!!!」 #rust_jp
— Satoshi Kojima (@skoji) 2018年8月1日
喋りながらコード書ける技術何気にすごいと思う #rust_jp
— Yuli Inoue (@iyunoriue) 2018年8月1日
「皆さん、今、実装してくださいね?!僕といっしょに!!」
— κeen (@blackenedgold) 2018年8月1日
#rust_jp
「みなさんも一緒に実装してくださいね!!!」 #rust_jp
— なっぱ@パーフェクトドブマスター (@b7472) 2018年8月1日
「ダイクストラは実装しやすいんですが、ここはコピペでいきます」
— κeen (@blackenedgold) 2018年8月1日
#rust_jp
Rust公式ページにダイクストラが乗っている #rust_jp
— u+ (@uplus_e10) 2018年8月1日
「ダイクストラ法の実装はRustのbinary_heapのドキュメントに乗っている。それをそのままコピペします!!!」 wwwwww #rust_jp
— Satoshi Kojima (@skoji) 2018年8月1日
rustの公式ドキュメントにヒープを使ったダイクストラ法の実装があるwwwwwwwww #rust_jp
— おおた (@ota42y) 2018年8月1日
「RustのBinaryHeapのドキュメントにダイクストラ法のコードが乗っているのでコピペします」 #rust_jp
— 電波椅子🐱 (@dempacat) 2018年8月1日
「Rustはなんと標準ライブラリのBinaryHeapのドキュメントにダイクストラの実装が載ってます!!!これをコピペして使います!!!!」
— κeen (@blackenedgold) 2018年8月1日
#rust_jp
コピペによるライブコーディングが始まった #rust_jp
— soebosi (@ebosi38051) 2018年8月1日
— Satoshi Kojima (@skoji) 2018年8月1日
迷いなく書いてるあたり手慣れてるな〜
— κeen (@blackenedgold) 2018年8月1日
#rust_jp
— yuki (@helloyuk13) 2018年8月1日
— 電波椅子🐱 (@dempacat) 2018年8月1日
話しながら書くの難しそう #rust_jp
— mizdra (@mizdra) 2018年8月1日
公式docsにダイクストラの実装サンプルあるのかhttps://t.co/OTUeX1Jimc
— わさん (@wasanx25) 2018年8月1日
#rust_jp
「提出していきましょう」 #rust_jp
— なっぱ@パーフェクトドブマスター (@b7472) 2018年8月1日
ちゃんとコンパイルエラーになるところも見せた
AtCoderのRust古くなかったっけ・・・ #rust_jp
— Tsuzu (@Wp120_3238) 2018年8月1日
「AtCoderのRustのパージョンが古い!!」
— κeen (@blackenedgold) 2018年8月1日
#rust_jp
みっちり練習した痕跡よww #rust_jp
— えまのん (@emanon_was) 2018年8月1日
— なっぱ@パーフェクトドブマスター (@b7472) 2018年8月1日
AtCoderのRustコンパイラのバージョンが古いので、コピペしたところが動かない #rust_jp
— 電波椅子🐱 (@dempacat) 2018年8月1日
コーナーケースで不正解になるところも見せた
これはあまり伝わっていなかったかもしれない。
Rustの話じゃなくて問題の解説始まった #rust_jp
— 目指せ黄色 (@matsu7874) 2018年8月1日
「結局何をやったかというと、1行目〜84行目までコピペ」 #rust_jp
— 電波椅子🐱 (@dempacat) 2018年8月1日
「ほぼコピペなので自分で書いたコードはこれだけなんですね。なんかできそう!」
— κeen (@blackenedgold) 2018年8月1日
#rust_jp
「速さを享受できるアルゴリズムの問題を解くのがいいのでは」 #rust_jp
— 名有りさん (@naari_) 2018年8月1日
コンパイラのバージョンが古くてストレスが溜まったりしませんか #rust_jp
— Tsuzu (@Wp120_3238) 2018年8月1日
実装する方法は得てないぞwwww #rust_jp
— 電波椅子🐱 (@dempacat) 2018年8月1日
喋りながらのライブコーディングも良いし、まとめもとても良かったw #rust_jp
— わさん (@wasanx25) 2018年8月1日
「みなさんは今日帰ったらダイクストラを実装できます。」
— κeen (@blackenedgold) 2018年8月1日
#rust_jp
けんこーさんうまいなぁ #rust_jp
— Tsuzu (@Wp120_3238) 2018年8月1日
疾走感ある発表だった #rust_jp
— なっぱ@パーフェクトドブマスター (@b7472) 2018年8月1日
プロ #rust_jp
— Ryota Sakamoto (@ryota_sakamot0) 2018年8月1日
ライブ・コーディング面白かった #rust_jp
— Yuli Inoue (@iyunoriue) 2018年8月1日
話しながら実装してミスしないのすごかった… #rust_jp
— おおた (@ota42y) 2018年8月1日
感想
自己顕示欲の満たされ方がすごい。
Rust で競技プログラミングをする時に使う高速な標準入力 Scanner
struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn usize_read(&mut self) -> usize { self.read() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } }