AtCoder

今日復習した問題

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

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

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

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

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のあと給油…

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…

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 そうでなけ…

lowlink, 橋や関節点について練習

lowlink や橋や関節点について、いくつか問題を解いたのでリンクを貼っておく。 lowlink の説明 kagamiz.hatenablog.comkagamiz 先生による有名記事。大変わかりやすい。 関節点・橋の確認用問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=…

ARC 039 D - 旅行会社高橋君

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

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…

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…

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

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