2022-12-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というメソッドを作って複素数を出力できるようにしましたが、そ…