2022-01-01から1年間の記事一覧

AtCoder Beginner Contest 271 D

https://atcoder.jp/contests/abc271/tasks/abc271_dカードの組と和でDPすればいいです。この時、1歩前の和を記録しておくとDPが終わった後にtrace backできて文字列を作ることができます。 後ろから追加していくので、あとから逆順の文字列にします。 // Fl…

AtCoder Beginner Contest 282 D

https://atcoder.jp/contests/abc282/tasks/abc282_d連結成分に分けて、隣り合うノードを白と黒に塗り分けます。塗り分けられなかったら二部グラフではありません。そして、連結成分の中と連結成分の間にエッジをいくつ作れるかを数えます。 // Make Biparti…

AtCoder Beginner Contest 276 D

https://atcoder.jp/contests/abc276/tasks/abc276_dAのgcdにAの各要素が何回割ってたどり着くかをカウントします。 reduceって無いんですね。foldだとgcdはちょっと面倒ですよね。 // Divide by 2 or 3 #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut</t:>…

AtCoder Beginner Contest 277 D

https://atcoder.jp/contests/abc277/tasks/abc277_dAをソートして、グループ化します。あとは最初と最後がくっつくかですね。 // Takahashi's Solitaire #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_</t:>…

AtCoder Beginner Contest 281 D

https://atcoder.jp/contests/abc281/tasks/abc281_dキーが個数と和のDの剰余、値を和の最大値とするDPですね。 // All Assign Point Add #![allow(non_snake_case)] use std::collections::HashMap; fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::i</t:>…

AtCoder Beginner Contest 278 D

https://atcoder.jp/contests/abc278/tasks/abc278_dHashMapを使えば簡単ですね。 // All Assign Point Add #![allow(non_snake_case)] use std::collections::HashMap; fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut li</t:>…

AtCoder Beginner Contest 279 D(2)

https://atcoder.jp/contests/abc279/tasks/abc279_d微分を使わなくても、3点の区間を倍々にしていって、3点の中で真ん中が一番時間が短ければ、そこから真ん中が一番時間が短い状態をキープしつつ区間を縮小していきます。 // Freefall #![allow(non_snake_…

AtCoder Beginner Contest 279 D

https://atcoder.jp/contests/abc279/tasks/abc279_d微分して0になる点から、前後を調べます。ただし、1より小さくなってはいけません。 // Freefall #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line</t:>…

AtCoder Beginner Contest 280 D

https://atcoder.jp/contests/abc280/tasks/abc280_d素因数分解すれば、あとは素数ごとに計算すればよいですね。 素数ごとに条件を満たす最小の倍数を求める部分はもっと効率のいい方法があると思いますが、素因数分解に比べれば十分に速いですね。 // Facto…

AtCoder Beginner Contest 272 D(2)

https://atcoder.jp/contests/abc272/tasks/abc272_d素因数分解さえできれば、移動できるステップを高速に求められます。そのために、GaussIntという構造体を作りました。 デバッグのためにfmtというメソッドを作って複素数を出力できるようにしましたが、そ…

AtCoder Beginner Contest 272 D

https://atcoder.jp/contests/abc272/tasks/abc272_dどこへ進めるかはナイーブに実装しても十分に間に合いますね。 何歩で行けるかはQueueを使えばよいですが、RustではVecDequeというcollectionを使うようです。 // Root M Leaper #![allow(non_snake_case)…

AtCoder Beginner Contest 273 D

https://atcoder.jp/contests/abc273/tasks/abc273_dこれも行と列で分けて考えることができます。 壁の座標を各行、各列で格納します。 その際に二分探索をするのでソートしますが、HashMapの中のVecをどうソートしていいのか分からなかったので、新たにHash…

AtCoder Beginner Contest 274 D

https://atcoder.jp/contests/abc274/tasks/abc274_dx軸とy軸で分けて考えればよいです。 あと、flattenがちゃんとあるんですね。 // Robot Arms 2 #![allow(non_snake_case)] use std::collections::HashSet; fn read<T: std::str::FromStr>() -> T { let mut line = String::new(</t:>…

AtCoder Beginner Contest 275 D(3)

https://atcoder.jp/contests/abc275/tasks/abc275_dmemoizeというcrateを使えば簡単です。 ただ、AtCoderでは使えないようです。 // Yet Another Recursive Function #![allow(non_snake_case)] use memoize::memoize; fn read<T: std::str::FromStr>() -> T { let mut line = Str</t:>…

AtCoder Beginner Contest 275 D(2)

https://atcoder.jp/contests/abc275/tasks/abc275_d構造体にメモを置けばそんなに気持ち悪くないと思います。 // Yet Another Recursive Function #![allow(non_snake_case)] use std::collections::HashMap; fn read<T: std::str::FromStr>() -> T { let mut line = String::new(</t:>…

AtCoder Beginner Contest 275 D

https://atcoder.jp/contests/abc275/tasks/abc275_dABCのD問題を解いていきます。 単なるメモ化の問題ですが、Rustではグローバル変数が難しいので、みっともないですが関数にメモを渡します。 // Yet Another Recursive Function #![allow(non_snake_case)…

AtCoder Beginner Contest 270 C

https://atcoder.jp/contests/abc270/tasks/abc270_c各点のXからの距離を調べて、Yからトレースバックします。 Yにたどり着いたら距離を調べるのを打ち切ってもいいのですが、これでも十分速いです。 // Simple path #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -></t:>…

AtCoder Beginner Contest 271 C

https://atcoder.jp/contests/abc271/tasks/abc271_cBTreeSetを使って、一つずつtreeにinsertして、重複分は十分大きな値にしてinsertします。 最初はVecを使って実装しましたが、そちらの方が速かったようです。 // Manga #![allow(non_snake_case)] use st…

AtCoder Beginner Contest 272 C

https://atcoder.jp/contests/abc272/tasks/abc272_cAを偶数と奇数に分ければよいですが、filterを使って簡単に書くとどうしてもVecになってしまいます。 let mut evens = Vec::<i32>::new(); let mut odds = Vec::<i32>::new(); for a in A.iter() { if a % 2 == 0 { </i32></i32>…

AtCoder Beginner Contest 273 C

https://atcoder.jp/contests/abc273/tasks/abc273_cgroupbyが使えれば簡単ですが、itertools::Itertoolsにgroup_byというのがありますね。 あと、fにVecをmutableで渡すとめんどうなので、渡す前にsortします。 // (K+1)-th Largest Number #![allow(non_sn…

AtCoder Beginner Contest 274 C

https://atcoder.jp/contests/abc274/tasks/abc274_cただのDPですね。 // Ameba #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr></t:></t:>…

AtCoder Beginner Contest 255 C

https://atcoder.jp/contests/abc255/tasks/abc255_c等差数列を構造体にすれば楽になりますが、負数が絡むと不安になりますね。 // ±1 Operation 1 #![allow(non_snake_case)] use std::cmp::min; fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::</t:>…

AtCoder Beginner Contest 256 C

https://atcoder.jp/contests/abc256/tasks/abc256_cこうすると怒られます。 if hs.iter().sum() != ws.iter().sum() { 40 | if hs.iter().sum() != ws.iter().sum() { | ^^^ cannot infer type for type parameter `S` declared on the associated function…

AtCoder Beginner Contest 257 C

https://atcoder.jp/contests/abc257/tasks/abc257_c各体重に対して子どもが何人、大人が何人いるかをMapに入れますが、ソートして使いたいのでBTreeMapを使います。 // Robot Takahashi #![allow(non_snake_case)] use std::collections::BTreeMap; fn read<T: std::str::FromStr></t:>…

AtCoder Beginner Contest 258 C

https://atcoder.jp/contests/abc258/tasks/abc258_c1の処理をする代わりに先頭の位置を変えます。 // Rotation #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse</t:>…

AtCoder Beginner Contest 259 C

https://atcoder.jp/contests/abc260/tasks/abc259_cgroupbyを使えば簡単です。PartialEqとCopyが実装されていればOKのようです。 // XX to XXX #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut</t:>…

AtCoder Beginner Contest 260 C

https://atcoder.jp/contests/abc260/tasks/abc260_c結局、HashMapはentryを使わないとうまくいかないですね。 // Changing Jewels #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok();</t:>…

AtCoder Beginner Contest 261 C

https://atcoder.jp/contests/abc261/tasks/abc261_c結局、HashMapはentryを使わないとうまくいかないですね。 // NewFolder(1) #![allow(non_snake_case)] use std::collections::HashMap; fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin(</t:>…

AtCoder Beginner Contest 262 C

https://atcoder.jp/contests/abc262/tasks/abc262_cインデックスと同じものと往復すると同じになるものを数えます。 // Min Max Pair #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok</t:>…

AtCoder Beginner Contest 263 C

https://atcoder.jp/contests/abc263/tasks/abc263_ccombinationsを使うだけですね。 // Monotonically Increasing #![allow(non_snake_case)] use itertools::Itertools; fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut </t:>…