問題 D - Alice&Brown 解法 実験すると |x-y|grundy 数が 0 になりそうな気がするので、結論ありきで帰納法で証明する。 コード use std::collections::{BTreeMap, BTreeSet}; fn main() { let mut sc = Scanner::new(); let x: u64 = sc.read(); let y: u64…

問題 C - Cheating Nim 解法 Grundy 数の原理から、「各 もしくは の XOR の値を 0 にすることが出来るか？出来るなら を使った回数は何回か？」という問題に言い換えることができます。ここで、ある i について を使うと XOR の値 x は になります。すなわ…

問題 D - XOR XorY 解法 解説を読んでも分からなかったので 「みんなのプロコン 2018」: D - XOR XorY · うさぎ小屋 を参考にした。 または ということは なので とすると となる。以後、 を満たす を数え上げることにする。 i=j でも条件を満たすため より …

問題 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…

問題 C: 広告 - SoundHound Inc. Programming Contest 2018 (春) | AtCoder 解法 グリッドグラフでの最大安定集合を求めたい。最大安定集合は最小点被覆の補集合なので、最小点被覆問題を解く。二部グラフでは最小点被覆問題は最大マッチング問題の双対なの…

LG Gram 買いました 会社の MacBook Pro 2015 13-inch を使っていましたが、会社をやめるにあたって自分用の PC を買いました。かなり悩んだ末買いましたが思ったより良かったのでレビューを書いておきます。 商品リンク http://amzn.to/2Csklt8 購入の際の…