Rust

Project Euler 684 Inverse Digit Sum

問題 projecteuler.net 解法 各桁の数の和がxとなるような最小の整数 s(x) は必ず一番上の桁以外は全て9となる。 よって s(x) は以下のようになる。s(x) の和 S(x) を考える。 S(20)=1074だが、これは以下のようにして求まる。 s(1) = 1 ... s(9) = 9 s(10) …

ABC143 F - Distinct Numbers

問題 atcoder.jp 解法 K枚ずつ食べる時の最大の回数を求めるのではなく、H回食べるときの最大の1回に食べる枚数を求めることにする。 とする。H回食べると決めたとき、同じ数字を同時に食べないように選ぶ1回あたりの食べる枚数はとなる。例えば A = [1,1,1,…

AGC039 C - Division by Two with Something

問題 atcoder.jp 解法 各操作を観察すると、どちらも「最も下のビットをpopして反転して最も上にpushする」と言い換えられる。これをN回繰り返すと元の数のビットを反転させたものが得られるので、2N回繰り返すと必ず元の数が得られる。よって繰り返して元の…

AGC038 C - LCMs

問題 atcoder.jp 解法 mobile.twitter.com自分の学習のために式を書き直してみたが全く同じになってしまった……ここで とすると なので コード use mod_int::ModInt; const MOD: usize = 998244353; fn main() { let s = std::io::stdin(); let mut sc = Scan…

Project Euler 679 Freefarea

問題 projecteuler.net長さ n で A, E, F, R からなる文字列のうち、4つのキーワード FREE, FARE, AREA, REEF を各1回ずつ含むものはいくつあるか。n=30について求めよ。 解法 全ての文字列を陽に持つ必要はなく、(各キーワードを持っているかどうか, 接尾辞…

2019/09/23

atcoder.jp use std::collections::{BTreeMap, BinaryHeap, VecDeque}; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let mut graph = vec![vec![]; (1 << (n + 1)) - 1]; let mut inverse …

AGC036 B - Do Not Duplicate

問題 atcoder.jp 解法 s の先頭の数字と同じ数字が来たら s が空になることを考える。例えば a(0)=a(i), a(i+1)=a(j) のとき、s は i で空になり、jで再び空になる。鳩の巣原理より a0 が何周目で再び先頭になるかO(N)で求めることができる。a0 が先頭になっ…

ABC139 F - Engines

問題 atcoder.jp 解法 答えとなるベクトル v があったとして、それを作るには v となす角が 90° 未満のベクトル集合のみを考えれば良い。よって、最終的に使われるベクトル集合は偏角ソートしたときに連続した区間になっているはずである。Nが小さいので全て…

ABC139 E - League

問題 atcoder.jp 解法 順番を並び替えることを考える余地はなく、「今日試合ができる組は全員試合をする」を毎日繰り返す。 コード use std::cmp::max; use std::collections::VecDeque; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdi…

飲酒プログラミングコンテストに参加した

注意(2019/09/01 追記) この記事は過度な飲酒を推奨するものではありません。飲酒プログラミングコンテストでは速く飲むことを重視するあまり、過度に飲酒を行ってしまう傾向があります。開催する場合、その危険性を十分認識した上で自己責任で行ってくだ…

ABC137 D - Summer Vacation

問題 atcoder.jp 解法 どの仕事も1日で終わるので、もらえる金額が大きければ大きいほどよい。よってもらえる金額が大きい方から処理していく。もらえる金額が同じ仕事同士では、振込が早い仕事よりも遅い仕事の方が候補日が限られるので、遅い仕事から処理…

AtCoder Beginner Contest 136 F - Enclosed Points

問題 atcoder.jp 解法 各点について、自分の (左上、右上、左下、右下) にある点の数を数える。これは 座標圧縮 => Fenwick Tree で O(N logN) でできる。各点について、その点を含まない長方形の数は以下の合計である。 右下の空でない点集合の数 * 右上の…

HUPC 2019 Day1 F: グリッドの番号 (Grid Number)

問題 https://onlinejudge.u-aizu.ac.jp/beta/room.html#HUPC2019Day1/problems/F 解法 1から2nまでの数を順番にグリッドに詰めていく。このとき、各状態からの遷移は上段に詰めるか下段に詰めるかの2通りの遷移がある。各状態を、「下段より右側に出ている…

今日復習した問題

B - Splatter Painting クエリを逆順にやればいいというのは「Pruned Landmark Labeling で見た!」という気持ちでやった。 use std::collections::VecDeque; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usiz…

AGC 014 C - Closed Rooms

問題 atcoder.jp 解法 もし、魔法の操作の順序が入れ替わっていて、魔法が「Kこの部屋を選んで解放し、その後、K回移動する」という操作だったら、移動しながら部屋を開けていけば良いので、非常に単純なBFSになる。ここに落とし込むために、操作を以下のよ…

AtCoder Beginner Contest 132 F - Small Products

問題 atcoder.jp 解法 ナイーブなDPを考えると、遷移する先が区間に分けられ、しかもその区間の数は であることに気づく。DPの際に区間ごとにまとめて遷移させれば良い。 コード use mod_int::ModInt; use std::collections::BTreeSet; const MOD: usize = 1…

AtCoder Beginner Contest 132 E - Hopscotch Addict

問題 atcoder.jp 解法 ステップが3の倍数でないとゴールできない幅優先探索なので、頂点を3倍に増やせば良い。 コード use std::collections::VecDeque; const INF: u64 = std::u64::MAX / 2; fn main() { let s = std::io::stdin(); let mut sc = Scanner {…

AtCoder Beginner Contest 132 D - Blue and Red Balls

問題 atcoder.jp 解法 K個の青いボールをi個の区間に分け、かつ、全ての区間が1個以上ボールを含むような青いボールの分け方は である。同様に考えて赤いボールの分け方を求め、この2つの積が答えになる。 const MOD: usize = 1e9 as usize + 7; fn main() {…

今日解いた問題

atcoder.jpバグらせずに実装するのが地味に大変な問題だと思う。 use std::cmp; use std::collections::BTreeMap; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let h: usize = sc.read(); let w: usize = sc.read(); …

VSCode で Rust で競技プログラミングをするときの設定

拡張機能と RLS を入れる task の登録 { // See https://go.microsoft.com/fwlink/?LinkId=733558 // for the documentation about the tasks.json format "version": "2.0.0", "tasks": [ { "label": "cargo run", "type": "shell", "command": "RUST_BACKT…

今日解いた問題

問題 atcoder.jpT経過後の蟻の位置は分かるので、蟻0がどの位置に対応するかを考える。これは座標0を通過した蟻の数で分かる。 コード fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let l: …

Google Code Jam 2019 Round 1B - Fair Fight

問題 codingcompetitions.withgoogle.com数列 が与えられる。 となるような (l, r) の組の数を求めよ。 解法 となるような (l, r) の組の数を求めて全体から引くことにする。 と は c と d を入れ替えることで独立に同じように求めることができる。各 i につ…

Google Code Jam 2019 Round 1B - Draupnir

問題 codingcompetitions.withgoogle.com要素数 6 の数列 がある。クエリとして D を出力すると、 が与えられる。クエリを 2 回投げた後に を出力せよ。 解法 は入力を 64bit 整数に収めるためのものではなく、解法の重要なポイントになる。D=200 で得られる…

Rust LT #4 で LT をした

rust.connpass.comこれに参加して5分枠で発表した。 テーマ決め AtCoder Problems というサービスのバックエンドを Rust で書いていたので、それについて発表しようと思った。github.com技術的にはそこまで難しくなく、やっていることはドキュメントを読めば…

エクサウィザーズ 2019 D - Modulo Operations

問題 atcoder.jp 解法 解説にあるとおり、ある数が使われた後、その数より大きい数を使ったとしても剰余には影響しないので、大きい数から順番に見ていって数列に詰めていくことを考える。i番目(0 コード const MOD: usize = 1e9 as usize + 7; fn main() { …

エクサウィザーズ 2019 E - Black or White

問題 atcoder.jp 解法 毎回 (i個目を取る時に白が無くなっている確率) + (i個目を取る時に白も黒も無くなっていない確率)/2 を出力する。 (i 個目を取る時に白が無くなっている確率) = (i-1個目を取る時に白が無くなっている確率) + (i-1個目で最後の白を取…

キーエンス プログラミング コンテスト 2019: E - Connecting Cities

問題 atcoder.jp 解法 の値が大きい方から小さい方に辺を張ると考えても良いので、そう考える。 となるような i, j, k を考え、頂点kからiかjのどちらかに辺を引くことを考える。 i-j 間のコストは j-k 間のコストは i-k 間のコストは の場合、 だから だか…

Codeforces Round #541 (Div. 2) E. String Multiplication

問題 http://codeforces.com/contest/1131/problem/Eある文字列 S と T が与えられた時、文字列 S の長さを m として S と T の積を と定義する。文字列 p1, p2, ..., pN が与えられるので の中で同じ文字が連続して現れる回数の最大値を求めよ。 解法 pN 以…

AtCoder Regular Contest 102 D - All Your Paths are Different Lengths

問題 atcoder.jp 解法 頂点 v から v+1 へ、長さ 0 の辺と、長さ の辺を張る。これによって、 の長さのパスが存在することになる。次に、頂点を の順番で見ていく。頂点 0 から頂点 v へは の長さのパスが存在するので、頂点 v から頂点 n-1 へ長さ t の辺を…

Rust の Vec の sort_by_key は気をつけて使おう

当たり前っちゃ当たり前だが、 vec.sort_by_key(|&value| heavy_function(value)); みたいなことをすると、 heavy_function が比較のたびに呼ばれるので、ソートが定数倍遅くなる。これは sort_by_cached_key でなんとかなるっぽい。sort_by_key は This sor…