2023-02-01から1ヶ月間の記事一覧

AtCoder Beginner Contest 290 D

https://atcoder.jp/contests/abc290/tasks/abc290_d例えば、N=10、D=4なら、0 -> 4 -> 8 -> 2 -> 6 -> 0だから、周期が5になります。 Kが5より大きければ1つずれます。 // Marking #![allow(non_snake_case)] //////////////////// library ///////////////…

アルゴリズムと数学 036

https://atcoder.jp/contests/math-and-algorithm/tasks/abc168_csin/cosはこんな感じですね。 theta.sin() theta.cos() // : (Colon) #![allow(non_snake_case)] use std::ops::Sub; use std::f64::consts::PI; //////////////////// library /////////////…

アルゴリズムと数学 035

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ag半径と中心間の距離の関係ですね。 // Two Circles #![allow(non_snake_case)] use std::ops::Sub; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let m</t:>…

アルゴリズムと数学 034

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_af総当たりでOKですね。 f64はminを取るのが面倒で、foldを使えば可能ですが、 fold(f64::MAX, f64::min) がAtCoderでは通らなくて、f64::MAXの代わりに1e7としました。 // Neares…

アルゴリズムと数学 033

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ae直線BC上の点はと表されるので、この点PとAを結んだ直線とBCが直交するなら、 なら、点Pは線分BC上となり、Aから最短の点に、そうでなければBかCが最短の点になります。 // Dist…

AtCoder Beginner Contest 289 D

https://atcoder.jp/contests/abc289/tasks/abc289_dただのDPですね。 // Step Up Robot #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut l</t:>…

アルゴリズムと数学 031

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_acこれもDPですが、一つ前とその前で最大を覚えておくとよいです。 手元では、 (a, b) = (max(a, b), a + c) が通ったのですが、AtCoderではダメでした。 // Taro's Vacation #![a…

アルゴリズムと数学 030

https://atcoder.jp/contests/math-and-algorithm/tasks/dp_d重さを状態とするDPですね。 // Knapsack 1 #![allow(non_snake_case)] use std::cmp::max; fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.</t:>…

アルゴリズムと数学 029

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_abFibonacci数列ですね。 // Frog1 #![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:>…

アルゴリズムと数学 028

https://atcoder.jp/contests/math-and-algorithm/tasks/dp_a単なるDPですね。 // Frog1 #![allow(non_snake_case)] use std::cmp::min; 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 288 D

https://atcoder.jp/contests/abc288/tasks/abc288_dにcを加算するとはどういうことでしょう。Aを多項式、すなわちと考えると、を足すことです。つまり、この問題は、の倍数を足して0になるか、言い換えると多項式をで割って余りが0か否かということです。K=…

アルゴリズムと数学 027

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_aaマージソートを実装するだけです。 URLはExcel方式ですね。 // Sorting #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_lin</t:>…

アルゴリズムと数学 026

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_zN種類だったとして最初に1種類目が出るまで1回、次の種類が出る確率は(N-1)/Nなので、次の種類が出るまでの回数の期待値はN/(N-1)、その次の種類が出る確率は(N-2)/Nなので、次の…

アルゴリズムと数学 022

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_v2つを足してある値になるは、ソートしてしゃくとり法ですね。 // Choose Cards 3 #![allow(non_snake_case)] fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().</t:>…