競技プログラミング

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 の辺を…

「第3回 RCO日本橋ハーフマラソン 予選」の復習

atcoder.jpこのコンテストに出たのですが、散々な結果だった。ただ、終わった後に流れてきた解法を見ると結構シンプルなものが多かったので、復習した。 A - ツーリストXの旅行計画 A - ツーリストXの旅行計画 分散が出てきてややこしい気持ちになるが、平均…

AGC 029 C - Lexicographic constraints

問題 beta.atcoder.jp 解法 できるだけ、辞書準最小のリストを作ることを目指す。例えばA=[2, 2]の時は["aa","bb"]でもよいが、["aa", "ab"] が辞書準最小のリストになる。この時、一つ前の要素よりも大きい時は、一つ前の文字列の後ろに "a" を連続で追加す…

AGC 029 D - Grid game

問題 beta.atcoder.jp 解法 まず先手が能動的にパスを選択することはありえない。なので、後手は先手の進行方向に障害物を置きさえすれば良い。両プレーヤーが能動的にパスを選択せずにxターンが終了した時の位置を (x, y) とする。このとき、後手は適当にパ…

AtCoder Regular Contest 059 E - キャンディーとN人の子供 / Children and Candies

問題 beta.atcoder.jp 解法 求める値は以下の式で表される。これは解説動画の変形を駆使して、以下のように変形できる。よって以下のような動的計画法で解ける。 コード use self::mod_int::ModInt; const MOD: usize = 1e9 as usize + 7; fn main() { let s…

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…