Rust

AGC 003 D - Anticube

問題 https://beta.atcoder.jp/contests/agc003/tasks/agc003_d 解説 各 s_i を素因数分解する(方法は後で考える)。まず、 s_i に 3 つ同じ素因数が含まれるとき、それらを取り除いてしまっても構わない。例えば のとき、 を取り除いて と考えて良い。この…

ARC 072 D - Alice&Brown

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

CODE FESTIVAL 2016 Grand Final C - Cheating Nim

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

「みんなのプロコン2018」 D - XOR XorY

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

SoundHound Inc. Programming Contest 2018 (春) D - 建物

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

SoundHound Inc. Programming Contest 2018 (春) C - 広告

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

CODE FESTIVAL 2017 Final E - Combination Lock

問題 E - Combination Lock 解法 方針としては、 区間を整理しやすいように文字列の長さを偶数にする。 区間の整理をめっちゃ頑張る 端から区間を見ていけば良いだけの状態になったら imos 法で順番に処理していき、ダメだったら NO 文字列の長さを偶数にす…

AIM Tech Round 4 (Div. 1) D. Dynamic Shortest Path

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

ARC082 F - Sandglass

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

ARC082 E - ConvexScore

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

ARC080 E - Young Maids

Rust の練習 問題 http://arc080.contest.atcoder.jp/tasks/arc080_c 解法 逆から考えて、最後に先頭に追加される 2 つの数を考える。これらを前から順番に とすると、i は偶数、j は奇数であり、かつ、 が成り立つことがわかる。よって、この条件を満たす i…

AtCoder Grand Contest 013 C - Ants on a Circle

問題 http://agc013.contest.atcoder.jp/tasks/agc013_c 解法 解説の通りにやった。Rustでは map を使って for を消せることを学んだ。 コード use std::fmt::Debug; use std::io; use std::io::{Read, Stdin}; use std::str; use std::str::FromStr; use st…

ABC062/ARC074

Rust でやってみました。標準入出力は他の人のを拝借してきたけど、 println マクロは出力ごとに flush しているようなので注意が必要そう。もっときれいに書けるようになりたい。 A - Grouping http://abc062.contest.atcoder.jp/tasks/abc062_a fn next() …