2024-10-01から1ヶ月間の記事一覧
https://atcoder.jp/contests/abc377/tasks/abc377_eiからPiにと辿っていくとループがいくつかできます。そうすると、K=1なら2歩、K=2なら4歩、K=3なら8歩そのループを進みます。 べき乗の計算はi128を使うと簡単ですね。 // Permute K times 2 #
https://atcoder.jp/contests/abc377/tasks/abc377_d例3だと、[5, 19]は[8, 12]を含みますが、この場合[5, 19]は要らないないです。こういう区間を消すと楽になります。 // Many Segments 2 #![allow(non_snake_case)] use std::collections::BTreeSet; ////…
https://atcoder.jp/contests/abc376/tasks/abc376_emax Aを決めて、その条件でBの和が最小になるようにすると考えるとわかりやすいです。 // Max × Sum #![allow(non_snake_case)] use std::collections::BinaryHeap; //////////////////// library ///////…
https://atcoder.jp/contests/abc376/tasks/abc376_d幅優先探索します。 // Cycle #![allow(non_snake_case)] use std::collections::VecDeque; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io</t:>…
https://projecteuler.net/problem=74辿っていくとρ型になるのですが、すでにあと何歩進めるか分かっているノードに突き当たったら、そこで終了できます。 import sys #################### library #################### fn make_factorial_table(N: Int) -…
https://atcoder.jp/contests/abc375/tasks/abc375_eDPです。状態を各チームの強さ、値を変更人数とします。各チームの強さの最大は500ですが、2チーム分だけを状態とすればよいです。 // 3 Team Division #![allow(non_snake_case)] use std::cmp::min; ///…
https://atcoder.jp/contests/abc375/tasks/abc375_d文字ごとにポジションを配列にして、それをxと書くと、その配列のサイズをNとして、とすると、となって、で計算できます。 // ABA #![allow(non_snake_case)] use std::collections::HashMap; ///////////…
https://projecteuler.net/problem=73しらみつぶしをしてもよいのですが、もっと速い方法があります。 まず、約分を考えなければ、dを固定して考えて、分母の上限をNと書くと、となります。これをがんばって計算すると、そして、約分できない分数の個数をと…
https://projecteuler.net/problem=72分母を固定すれば、を計算すればよいとわかります。頑張れば速くできる気がしますが、ふつうにふるいを使います。 import sys #################### List #################### fn initialize_list[T: CollectionElement…
https://projecteuler.net/problem=710/1と3/7の間で3/7寄りだと(0+3x)/(1+7x)とすればよいです。これで分母が1000000以下になるようにxを定めればよいですが、分母が3で割り切れるならさらにxを大きくできます。 MojoもOptionalが使えますが、TupleがCollec…
https://projecteuler.net/problem=70が小さいほうから調べればよいです。一番小さくなるのは素数ですが、素数はpermutationになりえないので、素数の平方から調べます。100未満とすると、7×7です。次に小さいのは5×5か7×13です。、なので、次は5×5です。そ…
https://atcoder.jp/contests/abc374/tasks/abc374_d?lang=ja単なるしらみつぶしですね。 // Laser Marking #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin(</t:>…
