競技プログラミング

キーエンス プログラミング コンテスト 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…

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

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

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 は になります。すなわ…