競技プログラミング

AtCoder Beginner Contest 168 F - . (Single Dot)

問題 atcoder.jp 解法 まずはサイズの小さい問題を考える。入力として与えられる全ての線分の座標 (x, y) が 0幅優先探索などをして、線分をまたがずに到達できるマスの数を数えれば良いことになる。マス (i, j) は直線 x=i, x=i+1, y=j, y=j+1 に囲まれたマ…

AtCoder Grand Contest 038 C - LCMs

問題 atcoder.jp 解法メモ を求めるのではなく を求めていく方針を考える。 サンプル2の以下の例を解くことを考える。 8 1 2 3 4 6 8 12 12 なので、i j のペアについて考えるのではなく単体で考えてあとで調整できるということを頭に留めておく。 最大公約…

AtCoder Regular Contest 071 F - Infinite Sequence

問題 rated 黄色 diff 最後の生き残りF - Infinite Sequence 解法 1より大きい数が連続すると以降は全て決まるので、 (1)(211)(3111)(41111)... から構成される prefix と a>1 かつ b>1 として abbbbbb... となる suffix a>1として a11111.... となる suffix…

第二回全国統一プログラミング王決定戦予選 E - Non-triangular Triplets

問題 E - Non-triangular Triplets 解法 とりあえず 2N ... 3N-1 は c に割り当てる。というようにできるとよい。ここで、 としたいが、これだけでN要素は作れないので、前半と後半に分けて別々に構築する。 コード fn main() { let (r, w) = (std::io::stdi…

01/05やったこと

kenkoooo.hatenablog.com AtCoder C - ABland Yard F - Minimum Bounding Box C - Remainder Game E - Antennas on Tree D - 桁和 / Digit Sum AtCoder C - ABland Yard atcoder.jpアイディアの正当性を示すのは非常に難しく感じる。実装はシンプル。atcoder…

01/04やったこと

kenkoooo.hatenablog.com AtCoder D - Snuke Numbers E - キャンディーとN人の子供 / Children and Candies C - ABland Yard D - K-th K C - Swaps B - Holes F - Lotus Leaves AtCoder 昨日やり残した問題もまとめて片付ける。 D - Snuke Numbers atcoder.j…

AGC041 C - Domino Quality

問題 atcoder.jp コンテスト中の解法 実験すると雑な全探索でn=4, 5, 6が求まる。n=7は計算が終わらなかった。これを組み合わせるとn=7以外は構築可能になる。 n=7を気合で手作りする。 コンテスト後の解法 全探索を高速化してn=7を求めたい。 縦向きのドミ…

2019 JUST Programming Contest B. Memory Management System

問題 codeforces.com長さmの線分がとn個の区間があります。q個のクエリが与えられます。i番目のクエリでは整数k_iが与えられるので、線分上のn個の区間と重ならない長さk_i以上の区間で最も右にあるものを出力してください。 解法 空の集合Sを用意する。空い…

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について求めよ。 解法 全ての文字列を陽に持つ必要はなく、(各キーワードを持っているかどうか, 接尾辞…

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

今日復習した問題

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 で得られる…

エクサウィザーズ 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 間のコストは の場合、 だから だか…

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

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