2019-01-01から1年間の記事一覧
問題 E - All-you-can-eat 解説 他の回答を見つつ、公式解説の解法２に沿って回答を作成。 DP難しい。。。 fn solve(t: usize, abs: Vec<(usize, usize)>) -> usize { use std::cmp::max; let mut abs = abs; abs.sort_by_key(|x| x.0); let mut dp = vec
問題 F - Engines 解説 公式解説結構長めに書いてあるけど実装としては f64.atan2()で角度を求めてソート 連続的に取りうる組み合わせを全て試す これで で解ける fn solve(xys: Vec<(i64, i64)>) -> f64 { let n = xys.len(); let mut xys = xys; xys.sort_…
F - Enclosed Points 問題 TODO BIT 解説の前に今回のBITの使いどころについて軽く整理。 いまx座標で昇順に並べた点(例: ) があるとする。 BITを利用すると各点を原点として特定の象限に含まれる点の数を順に求めることができる。 例えば第3象限の場合は以…
E - Max GCD 問題 数列に対して、あるものにすると同時に、別の項にをするという操作をK回以下おこなって、取りうる最大のGCDを求めるという問題。 解説 ポイントは操作を行っても数列の総和は変わらず、かつ総和はGCDの倍数になっているはず、というところ…
E - Sequence Decomposing 問題 数列 が与えられたとき、数列を単調増加となるような部分数列に分けた場合に最小のグループ数を答える問題。 解説 公式解説には「広義の単調減少列の最大の長さ」を求めれば良いとあるが、ここがあまりしっくり来ていない。 …
F - Small Products 問題 正の整数K個を一列に並べたものであって、隣接して並んでいるどの2つの整数の積もN以下であるものの個数を109+7で割った余りを求めてください。 解説 公式解説にあるようにxが最後の整数となるようなi個の整数を並べて条件を満たす…
E - Friendships 問題 N頂点単純連結無向グラフで最短距離が2である頂点対がK個あるものを構築する。 解説 まず最短距離が2である頂点対が最大となるのはある１点（仮に「中心点」と呼ぶ）が他の全ての点と辺を持ち、それ以外の辺が存在しないときである。 …
D - Rain Flows into Dams 反省 二分探索で解けると思ったが、上限下限が決定できるような問題じゃなかった。 解説 に気づけたら実装は簡単。 fn solve(aa: &[i64]) -> Vec<i64> { let s = aa.iter().fold(0, |sum, i| sum + i); let x1 = s - 2 * aa.iter().skip</i64>…
AtCoder Beginner Contest 131 - AtCoder 反省 UnionFind木使うとかどうやったら思いつくんですかね…。 解説 参考: AtCoder ABC 131 F - Must Be Rectangular! (600 点) - けんちょんの競プロ精進記録 fn solve(xys: &[(usize, usize)]) -> usize { let n = …
