Rust

CODE FESTIVAL 2018 qual A D - 通勤

問題 beta.atcoder.jp 解法 公式解説を見ながらやった。地点 i で給油した時、残り容量は必ず f になる。x[i] + f - t までは少なくとも t 以下にはならないので、 x[i] から x[i] + f - t までの間にある給油所は、あってもなくても良い。また、iのあと給油…

AOJ 2893: Balanced Edge Deletion

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2893 解法 橋を全列挙し、それぞれについて削除したときの cost を求め、ソートすれば良い。具体的な実装としては、 橋を列挙する。 橋を含まない連結な部分グラフを潰して 1 つの頂点とし、…

AOJ 2891: Namo.. Cut

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2891 解法 N 頂点 N 辺のグラフ(いわゆる「なもりグラフ」)は1つだけ閉路があり、その閉路に木がいくつか連結している形になる。各クエリの頂点の両方とも閉路に含まれている場合2本切断す…

ARC094 D - Worst Case

問題 beta.atcoder.jp 解法 が全て より小さくなるような x、すなわち、 となるような x の最大値を求めたい。 で x は a より大きいとすると、 を満たす x を求めれば良い。 コード /// Thank you tanakh!!! /// https://qiita.com/tanakh/items/0ba42c7ca3…

CODE FESTIVAL 2018 qual B E - Game of +-

問題 beta.atcoder.jp 解法 を足したり引いたりしてを作る。 を足したり引いたりして 1 を作る。 にすることを目指すのではなく にすることを目指す。 であることは である。 なので、各 p について独立に考えればよいということになる。 コード /// Thank y…

AOJ 2900: Bumpy Array

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2900 解法 と並んでいるのを [tex: a_i>a_{i+1}a_{i+1}] が成り立っている時、以降の領域を自由に並べ替えても [tex:a_{i+1}a_{i+1}] も満たされるので、 は入れ替わらない。が満たされてい…

AGC020 C - Median Sum

問題 C - Median Sum 解法 解説の通り。空でない部分列の数は 個存在するが、部分列の和が x となるような部分列の構成方法の数え上げは動的計画法で で求まる。だが、これでは間に合わない。中央値は配列の合計の 1/2 以上になるということに気づくと、部分…

みんなのプロコン2018 決勝 A- Uncommon

問題 https://beta.atcoder.jp/contests/yahoo-procon2018-final/tasks/yahoo_procon2018_final_a 解法 ある整数 i について配列内の i と互いに素な整数の数を数えるのは大変そうなので、i と互いに素でない数を数えることにする。i を素因数分解し、例えば…

AtCoder Regular Contest 101 D - Median of Medians

問題 https://beta.atcoder.jp/contests/abc107/tasks/arc101_b 解法 完全に解法の通り。 全ての連続部分列のうち、中央値が x 以上であるものがいくつあるかを考える問題になる。 数列の中央値が x 以上である。 => 数列の各要素を x 以上なら 1 そうでなけ…

AOJ 3022: Cluster Network

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3022 解法 雰囲気から、関節点を求める機運が高まるが、実際の問題はその後に最後の答えを出力するパートである。http://web-ext.u-aizu.ac.jp/circles/acpc/commentary/ACPC2017Day2/J.pdf…

ARC 039 D - 旅行会社高橋君

問題 https://beta.atcoder.jp/contests/arc039/tasks/arc039_d 解法 橋を2回通らずに A->B->C の移動が出来るかという問題になる。まず橋を検出し、それらを取り除くと、グラフはいくつかの連結成分に分かれる。各連結成分内では頂点間を移動する経路が常に…

CS Academy: Growing Segment

問題と解法 記憶力があれなので同じ問題を何度も解く。kenkoooo.hatenablog.com コード use std::cmp; use std::collections::BTreeSet; macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter…

AtCoder Regular Contest 083 E - Bichrome Tree

問題 https://beta.atcoder.jp/contests/arc083/tasks/arc083_c 解法 いつもありがとうございます。頂点 v を根とする部分木で、頂点 v と同じ色の頂点の重みの合計は x[v] だが、同じ色でない頂点の重みの合計は小さければ小さいほどよい。よって、「頂点 v…

Battle Conference U30 - Programming Battle F - 数列と計算

問題 https://beta.atcoder.jp/contests/bcu30/tasks/bcu30_f 解法 全く同じ問題が CodeChef で出ている。https://ei1333.hateblo.jp/entry/2017/06/04/151131 コード use std::ops::*; const MOD: usize = 1e9 as usize + 7; fn main() { let mut sc = Scan…

AtCoder Regular Contest 081 F - Flip and Rectangles

問題 https://beta.atcoder.jp/contests/arc081/tasks/arc081_d 解法 解説の通り。最大長方形を求めるのは AOJ で学べた。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B コード use std::cmp; use std::collections::VecDeque; trait T…

AOJ Largest Rectangle

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B 解法 各列についてヒストグラムに内接する最大長方形を求める。 コード use std::cmp; use std::collections::VecDeque; trait TopQueue<T> { fn top(&self) -> &T; } impl<T> TopQueue<T> fo</t></t></t>…

AtCoder Regular Contest 073 E - Ball Coloring

問題 https://beta.atcoder.jp/contests/arc073/tasks/arc073_c 解法 解説のとおりだが、個人的には理解が難しかった。(分かると簡単シリーズ) 最小のボールが青、最大のボールが赤のとき 最小のボールを持つ青は、残りのボールをできるだけ小さくしたい。…

AtCoder Regular Contest 077 E - guruguru

問題 https://beta.atcoder.jp/contests/arc077/tasks/arc077_c 解法 x を設定することによって切り替えが高速化している区間を持っておく。 x を 1 増加させるとそれらの区間の切り替え時間はそれぞれ 1 ずつ短くなる。 コード use std::cmp; use std::coll…

C - Not Too Close SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open)

問題 https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_c 解法 解説が全く理解できなかったので下記ブログを参考にした。ありがとうございます。http://fluffyowl.hatenablog.com/entry/2018/07/31/00…

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]…

SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open) E - Hash Swapping

問題 E - Hash Swapping 解法 セグメント木の子ノード j に を入れておき、合計値を求める際に の逆元をかけることでハッシュを取り出せるようにする。各ノードは左右の子ノードへのポインタ(ポインタ操作は Rust で安全にやろうとすると重くなるので、実際…

Rust でライブコーディングをした

rust.connpass.com これの LT 枠でライブコーディングをした。 動機 Rust は比較的難しい言語だと思う(ふわっと書いてふわっと動くタイプの言語ではない)ので、聴衆が自分でもできそうと思えるようなパフォーマンスをしたかった。 問題選定 Rust の標準ラ…

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 st</u8></u8>…

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 文字列の長さを偶数にす…