https://atcoder.jp/contests/abc355/tasks/abc355_d区間の両端の点を一つのVecに入れて位置でソートします。その際、左右と何番目の区間かの情報も入れておきます。そして、位置の左から見ていって、左だったら何番目の左かを記録して、右だったらその区間…

https://projecteuler.net/problem=34Problem 30とほぼ同じで重複組み合わせを出します。ただし、0! = 1なので、桁数を変えないといけません。 from algorithm.sort import sort from math import min import sys #################### library ############…

https://projecteuler.net/problem=33しらみつぶしするだけですね。 #################### library #################### fn gcd(n: Int, m: Int) -> Int: if m == 0: return n else: return gcd(m, n % m) #################### process ##################…

https://atcoder.jp/contests/abc354/tasks/abc354_fまず、Aを左から見ていって、その要素が最大で増加部分列の何番目になるかを調べます。そのとき、その要素より小さい要素が最大何番目になっているかを調べます。そのために同じ番目で最小の要素を調べて…

https://atcoder.jp/contests/abc354/tasks/abc354_e特に工夫もせずにグラフを作ります。それで十分間に合いました。 // Remove Pairs #![allow(non_snake_case)] use std::collections::HashMap; //////////////////// library //////////////////// fn read<T: std::str::FromStr></t:>…

https://atcoder.jp/contests/abc354/tasks/abc354_d幅が4の倍数で高さが2の倍数の部分とそれ以外の3つの部分に分けて足し合わせます。 // AtCoder Wallpaper #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T </t:>…

https://projecteuler.net/problem=32問題をB進法に拡張します。 単にしらみつぶししてもいいのですが、それだけだと面白くないのでもう少し工夫します。B-1の剰余を考えると、各桁を足した和の剰余と同じになります。そうすると剰余の組み合わせが限られま…

https://atcoder.jp/contests/abc353/tasks/abc353_fK = 1なら単なるマンハッタン距離です。 K > 1なら、例1のように両側から大きいタイルに出て、大きなタイル間の距離を調べます。そのとき斜めの成分とx軸、y軸のどちらかに分解します。斜め成分は一つ進む…

https://atcoder.jp/contests/abc353/tasks/abc353_e木を作ればよいです。例1なら、 a(3)┓ ┣b(2)┓ ┃ ┗c(1) ┗rc(1)のような木を作ります。数字は文字列の個数です。 Pythonで書いてAIにRustにしてもらいましたが、間違いが多くて修正するのが大変でした。 // …

https://atcoder.jp/contests/abc353/tasks/abc353_dAtCoderではあまりないですが、和の取り方を逆にすればいい問題ですね。 // Another Sigma Problem #![allow(non_snake_case)] const D: u64 = 998244353; //////////////////// library ////////////////…

https://projecteuler.net/problem=31前回、同じようなコード、 for i in range(e, self.L-width, width): var e1 = self.a.load[width=nelts](i) var e2 = self.a.load[width=nelts](i-e) self.a.store[width=nelts](i, (e1+e2)%D) が3つ出てきましたが、次…

https://atcoder.jp/contests/abc352/tasks/abc352_eKruscal法を使うだけです。 // Clique Connect #![allow(non_snake_case)] use std::cmp::max; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std:</t:>…

https://atcoder.jp/contests/abc352/tasks/abc352_dインデックスをPの要素の大きさで並べ替えて、幅Kの中に入るインデックスの最大と最小の差を調べます。 // Permutation Subsequence #![allow(non_snake_case)] use std::cmp::{min, max}; //////////////…

https://projecteuler.net/problem=31この問題はSIMDが使えます。1コアでいくつかのデータに対して同時に処理を行えます。いくつ同時に処理を行えるかは、次のように分かります。 alias nelts = simdwidthof[DType.int32]() 手元では8でした。 まず、領域を…