CODE FESTIVAL 2016 Grand Final C - Cheating Nim
解法
Grundy 数の原理から、「各 もしくは の XOR の値を 0 にすることが出来るか?出来るなら を使った回数は何回か?」という問題に言い換えることができます。
ここで、ある i について を使うと XOR の値 x は になります。すなわち、現在の XOR の値と の XOR をとった値になります。ところで は必ず の形になります。証明もできますが、実験でもわかります。なので、貪欲に上のビットから潰していくことで解けます。
コード
fn main() { let mut sc = Scanner::new(); let n: usize = sc.read(); let a: Vec<u32> = (0..n).map(|_| sc.read()).collect(); let mut xor_sum = 0; for &a in &a { xor_sum ^= a; } let mut ans = 0; for bit in (0..30).rev() { if ((1 << bit) & xor_sum) == 0 { continue; } let x = (1 << (bit + 1)) - 1; for &a in &a { let y = a ^ (a - 1); if y == x { xor_sum ^= y; ans += 1; break; } } } if xor_sum != 0 { println!("-1"); } else { println!("{}", ans); } } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } 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<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(); } }
「みんなのプロコン2018」 D - XOR XorY
問題
解法
解説を読んでも分からなかったので 「みんなのプロコン 2018」: D - XOR XorY · うさぎ小屋 を参考にした。
または ということは なので とすると となる。以後、 を満たす を数え上げることにする。
- i=j でも条件を満たすため より
- i=j で条件を満たすとき j=i でも条件を満たすので かつ より
- を選んだとき より だから各 j について または となるものを から選んで [ex: a_j] とする。
コード
use std::cmp; const MAX_A: usize = 2048; const MOD: usize = 1000000007; fn main() { let mut sc = Scanner::new(); let n: usize = sc.read(); let k: usize = sc.read(); let x: usize = sc.read(); let y: usize = sc.read(); let c: Vec<usize> = (0..n).map(|_| sc.read()).collect(); let mut a = vec![vec![0; k]; k]; for i in 0..k { for j in 0..k { a[i][j] = sc.read::<usize>() ^ x; } } println!("{}", solve(k, x ^ y, &c, &a)); } fn solve(k: usize, z: usize, x: &Vec<usize>, b: &Vec<Vec<usize>>) -> usize { let comb = Combination::new(MAX_A * 2, MOD); // check for i in 0..k { if b[i][i] != 0 && b[i][i] != z { return 0; } } for i in 0..k { for j in 0..k { let delta = b[i][j] ^ b[j][i]; if delta != 0 && delta != z { return 0; } } } let mut count = vec![0; MAX_A + 1]; let mut xor_counted = vec![0; MAX_A + 1]; for xi in x { let xi = *xi; count[cmp::min(xi, xi ^ z)] += 1; if (xi ^ z) < xi { xor_counted[xi ^ z] += 1; } } let mut answer = 0; for a0 in 0..(MAX_A + 1) { if count[a0] == 0 { continue; } let mut used = vec![0; MAX_A + 1]; used[a0] += 1; let mut can_construct = true; for j in 1..k { let aj = cmp::min(b[0][j] ^ a0, b[0][j] ^ a0 ^ z); if used[aj] == count[aj] { can_construct = false; break; } used[aj] += 1; } if !can_construct { continue; } let mut ans_for_a0 = 1; for a in 0..(MAX_A + 1) { if used[a] == 0 { continue; } let needed = used[a]; let max_not_xor = cmp::min(count[a] - xor_counted[a], needed); let min_not_xor = if needed < xor_counted[a] { 0 } else { needed - xor_counted[a] }; let mut combination_sum = 0; for choose in min_not_xor..(max_not_xor + 1) { combination_sum += comb.get(needed, choose); if combination_sum > MOD { combination_sum -= MOD; } } ans_for_a0 *= combination_sum; ans_for_a0 %= MOD; } answer += ans_for_a0; if answer > MOD { answer -= MOD; } } return answer; } 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) -> usize { assert!(x >= y); 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>, } 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<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 Inc. Programming Contest 2018 (春) D - 建物
問題
解法
(i, j) から (i, k) に移動して (i+1, k) に移動する経路 (i, j) => (i+1, k) を考える。このとき、 (i, j-1) => (i+1, k) よりも多くの報酬が得られることに留意する。次に (i+1, k+1) に移動する経路を考える。このとき (i, j-1) => (i+1, k+1) よりも (i, j) => (i+1, k+1) の方がより多くの報酬が得られる。このように、下の階から上の階へ上がる経路はしゃくとり法によって求まる。
コード
use std::cmp; use std::i64::MIN; fn main() { let (h, w) = { let v = read_values::<usize>(); (v[0], v[1]) }; let p = { let mut p = vec![vec![0; w]; h + 1]; for i in 0..h { let v = read_values::<i64>(); for j in 0..w { p[i][j] = v[j]; } } p }; let f = { let mut f = vec![vec![0; w]; h + 1]; for i in 0..h { let v = read_values::<i64>(); for j in 0..w { f[i][j] = v[j]; } } f }; let mut gain = vec![vec![MIN; w]; h + 1]; gain[0][0] = p[0][0]; for i in 0..h { let mut left_turn = vec![0; w]; for j in 1..w { left_turn[j] = cmp::max(left_turn[j - 1] + p[i][j - 1] - (f[i][j - 1] + f[i][j]), 0); } let mut right_turn = vec![0; w]; for j in (0..(w - 1)).rev() { right_turn[j] = cmp::max(right_turn[j + 1] + p[i][j + 1] - (f[i][j + 1] + f[i][j]), 0); } let mut sum = vec![0; w + 1]; for j in 0..w { sum[j + 1] = sum[j] + p[i][j] - f[i][j]; } if i == 0 { for j in 0..w { gain[i + 1][j] = p[i + 1][j] - f[i + 1][j] + sum[j + 1] + right_turn[j]; } } else { let mut left_max = 0; for j in 0..w { let segment_sum = sum[j + 1] - sum[left_max + 1]; let enter_gain = p[i + 1][j] - f[i + 1][j]; let old_gain = gain[i][left_max] + segment_sum + left_turn[left_max]; let new_gain = gain[i][j] + left_turn[j]; if old_gain < new_gain { left_max = j; } gain[i + 1][j] = cmp::max(old_gain, new_gain) + right_turn[j] + enter_gain; } let mut right_max = w - 1; for j in (0..w).rev() { let segment_sum = sum[right_max] - sum[j]; let enter_gain = p[i + 1][j] - f[i + 1][j]; let old_gain = gain[i][right_max] + segment_sum + right_turn[right_max]; let new_gain = gain[i][j] + right_turn[j]; if old_gain < new_gain { right_max = j; } gain[i + 1][j] = cmp::max( cmp::max(old_gain, new_gain) + left_turn[j] + enter_gain, gain[i + 1][j], ); } } } for i in 0..w { println!("{}", gain[h][i]); } } fn read_line() -> String { let stdin = std::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() }
SoundHound Inc. Programming Contest 2018 (春) C - 広告
解法
グリッドグラフでの最大安定集合を求めたい。最大安定集合は最小点被覆の補集合なので、最小点被覆問題を解く。二部グラフでは最小点被覆問題は最大マッチング問題の双対なので(未証明)、最大マッチング問題を解く。
コード
use std::usize; use std::cmp; use std::collections::vec_deque::VecDeque; use std::i64::MAX; fn main() { let (r, c) = { let v = read_values::<usize>(); (v[0], v[1]) }; let dot = ".".as_bytes()[0]; let map = (0..r).map(|_| { read_line() .trim() .bytes() .map(|b| b == dot) .collect::<Vec<_>>() }).collect::<Vec<_>>(); let mut ok = 0; let mut dinitz = Dinitz::new(r * c + 2); let source = r * c; let sink = source + 1; for i in 0..r { for j in 0..c { if !map[i][j] { continue; } ok += 1; let v = i * c + j; if i % 2 == j % 2 { dinitz.add_edge(source, v, 1); } else { dinitz.add_edge(v, sink, 1); continue; } let x = vec![(1, 0), (-1, 0), (0, 1), (0, -1)]; for t in &x { let (di, dj) = *t; let ni = (i as i32) + di; let nj = (j as i32) + dj; if ni < 0 || ni >= r as i32 || nj < 0 || nj >= c as i32 { continue; } let w = ni * (c as i32) + nj; dinitz.add_edge(v, w as usize, 1); } } } let f = dinitz.max_flow(source, sink); println!("{}", ok - f as usize); } struct Edge { pub to: usize, pub rev: usize, pub cap: i64, } pub struct Dinitz { g: Vec<Vec<Edge>>, level: Vec<i32>, iter: Vec<usize>, } impl Dinitz { pub fn new(v: usize) -> Dinitz { let mut g: Vec<Vec<Edge>> = Vec::new(); for _ in 0..v { g.push(Vec::new()); } Dinitz { g: g, level: vec![0; v], iter: vec![0; v], } } pub fn add_edge(&mut self, from: usize, to: usize, cap: i64) { let to_len = self.g[to].len(); let from_len = self.g[from].len(); self.g[from].push(Edge { to: to, rev: to_len, cap: cap, }); self.g[to].push(Edge { to: from, rev: from_len, cap: 0, }); } fn dfs(&mut self, v: usize, t: usize, f: i64) -> i64 { if v == t { return f; } while self.iter[v] < self.g[v].len() { let (e_cap, e_to, e_rev); { let ref e = self.g[v][self.iter[v]]; e_cap = e.cap; e_to = e.to; e_rev = e.rev; } if e_cap > 0 && self.level[v] < self.level[e_to] { let d = self.dfs(e_to, t, cmp::min(f, e_cap)); if d > 0 { { let ref mut e = self.g[v][self.iter[v]]; e.cap -= d; } { let ref mut rev_edge = self.g[e_to][e_rev]; rev_edge.cap += d; } return d; } } self.iter[v] += 1; } return 0; } fn bfs(&mut self, s: usize) { let v = self.level.len(); self.level = vec![-1; v]; self.level[s] = 0; let mut deque = VecDeque::new(); deque.push_back(s); while !deque.is_empty() { let v = deque.pop_front().unwrap(); for e in &self.g[v] { if e.cap > 0 && self.level[e.to] < 0 { self.level[e.to] = self.level[v] + 1; deque.push_back(e.to); } } } } pub fn max_flow(&mut self, s: usize, t: usize) -> i64 { let v = self.level.len(); let mut flow: i64 = 0; loop { self.bfs(s); if self.level[t] < 0 { return flow; } self.iter = vec![0; v]; loop { let f = self.dfs(s, t, MAX); if f == 0 { break; } flow += f; } } } } fn read_line() -> String { let stdin = std::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() }
LG Gram 14Z970-GA55J レビュー
LG Gram 買いました
会社の MacBook Pro 2015 13-inch を使っていましたが、会社をやめるにあたって自分用の PC を買いました。かなり悩んだ末買いましたが思ったより良かったのでレビューを書いておきます。
商品リンク
購入の際の検討事項
以下の条件でノート PC を探していました。
- 日本で買えるもの(海外から取り寄せると初期不良とかあった時に面倒くさそう)
- メモリ 16 GB
- 英字配列キーボード
- 重量 1 kg 以下
- 13 インチ以上
- 10 万円前後
この条件に合致するものはなく、近いものとして以下のものがありました。
画面
14 インチのものを買いました。前の MacBook Pro が 13 インチだったので同じで良いかと思いましたが、LG Gram は画面の端が薄いのらしく、 14 インチ版が MacBook Pro 13 インチ版と同じ大きさらしかったので、14 インチに決めました。Retina ディスプレイを長きに渡って使ってきたので画面の粗さが気になると思って悩みましたが、意外にも全く気になりませんでした。
キーボード
英字配列が欲しかったので、英字配列しか存在しない Gram を選んで良かったです。購入の候補には ThinkPad も入っていたのですが、これは日本では JIS キーボードのものしか買えないとのことだったので諦めました。
メモリ
16 GB メモリを積んでいるものが欲しかったのですが、存在しなかったため、後から 16 GB に増設できる(LG で増設してもらうこともできますし、保証対象外ですが自分で増設することも出来ます)8GB モデルを選びました。Mac では 16 GB 無いと話にならなかったのですが、これは OS X がメモリをバカ食いするだけで、 Ubuntu をインストールして使う分には 8 GB で全く問題ありませんでした。
タッチパッド
MacBook Pro と違って、クリックがソフトウェアではなく物理なので、Mac に慣れていると少し違和感はあります。2本指での操作にも対応しています。
バッテリー
主な用途がプログラミングなのですが、この用途だと6〜8時間ほど使えます。
重量
971gだそうです。個人的にはかなり軽く感じます。肩掛けバッグに入れても気にならない程度の軽さです。
値段
14 万円くらいしました。ちょっと高い・・・
おわりに
それなりに良い買い物をしたと思います。特に Ubuntu との相性が良いのが気に入っています。
並列二分探索(解説なしバージョン)
並列二分探索、名前からして難しそうな感じがしていたが、特に難しいわけではなかった。
並列二分探索
個人的には並列という名前は正しくない気がします。
普通の二分探索は次の通り。
let mut ng = 0; let mut ok = m; for _ in 0..30 { let med = (ng + ok) / 2; // 何かしらの操作 if (何かしらの条件) { ok = med; } else { ng = med; } }
並列二分探索は次の通り。
let mut ng = vec![0; q]; let mut ok = vec![m; q]; for _ in 0..30 { let mut check: Vec<Vec<usize>> = vec![Vec::new(); m + 1]; // 各 med を取るようなクエリをリストアップしておく for i in 0..q { let med = (ng[i] + ok[i]) / 2; check[med].push(i); } let mut uf = UnionFind::new(n); // 順番に見ていき、 edge_id==med となるようなクエリについて ok と ng を更新する for edge_id in 0..m { uf.unite(a[edge_id], b[edge_id]); for query in check[edge_id].iter() { let from = uf.find(x[*query]); let to = uf.find(y[*query]); let count = if from == to { uf.sizes[from] } else { uf.sizes[from] + uf.sizes[to] }; if count >= z[*query] { ok[*query] = edge_id; } else { ng[*query] = edge_id; } } } }
コード
use std::io; fn main() { let (n, m) = { let v = read_values::<usize>(); (v[0], v[1]) }; let (a, b) = { let mut a = vec![0; m]; let mut b = vec![0; m]; for i in 0..m { let v = read_values::<usize>(); a[i] = v[0] - 1; b[i] = v[1] - 1; } (a, b) }; let q = read_values::<usize>()[0]; let (x, y, z) = { let mut x = vec![0; q]; let mut y = vec![0; q]; let mut z = vec![0; q]; for i in 0..q { let v = read_values::<usize>(); x[i] = v[0] - 1; y[i] = v[1] - 1; z[i] = v[2]; } (x, y, z) }; let mut ng = vec![0; q]; let mut ok = vec![m; q]; for _ in 0..30 { let mut check: Vec<Vec<usize>> = vec![Vec::new(); m + 1]; for i in 0..q { let med = (ng[i] + ok[i]) / 2; check[med].push(i); } let mut uf = UnionFind::new(n); for edge_id in 0..m { uf.unite(a[edge_id], b[edge_id]); for query in check[edge_id].iter() { let from = uf.find(x[*query]); let to = uf.find(y[*query]); let count = if from == to { uf.sizes[from] } else { uf.sizes[from] + uf.sizes[to] }; if count >= z[*query] { ok[*query] = edge_id; } else { ng[*query] = edge_id; } } } } for i in 0..q { println!("{}", ok[i] + 1); } } struct UnionFind { parent: Vec<usize>, sizes: Vec<usize>, size: usize, } impl UnionFind { fn new(n: usize) -> UnionFind { UnionFind { parent: (0..n).map(|i| { i }).collect::<Vec<usize>>(), sizes: vec![1; n], size: n, } } fn find(&mut self, x: usize) -> usize { if x == self.parent[x] { x } else { let px = self.parent[x]; self.parent[x] = self.find(px); self.parent[x] } } fn unite(&mut self, x: usize, y: usize) -> bool { let parent_x = self.find(x); let parent_y = self.find(y); if parent_x == parent_y { return false; } let (large, small) = if self.sizes[parent_x] < self.sizes[parent_y] { (parent_y, parent_x) } else { (parent_x, parent_y) }; self.parent[small] = large; self.sizes[large] += self.sizes[small]; self.sizes[small] = 0; self.size -= 1; return true; } } 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() }