https://projecteuler.net/problem=38一般的にB進法で考えます。単純に実行するとすぐにオーバーフローするので、B進のBigIntegerを作ります。 n=2のときが調べなければならない被乗数の個数が多いのでここが問題になります。攻めて考えると、10進のとき、被…

https://atcoder.jp/contests/abc359/tasks/abc359_f次数は1以上で全部で2N-2なので、まず全ての頂点に1を割り当てて、それからコストが小さいところから次数を1ずつ割り当てます。から次数を1つ割り当てると、コストが増すことになるので、それを考慮してPr…

https://atcoder.jp/contests/abc359/tasks/abc359_e左で一番最初に自分以上の値を探して、そこまでを自分の値と同じにします。そういう木を作ればよいです。 // Water Tank #![allow(non_snake_case)] use std::cmp::{min, max}; //////////////////// libr…

https://atcoder.jp/contests/abc359/tasks/abc359_d単純なDPですね。K文字でAを0、Bを1と考えれば、0～2K-1までの整数が状態となります。 // Avoid K Palindrome #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -</t:>…

https://projecteuler.net/problem=37右に数字を追加した素数と左に追加した素数をそれぞれ作っていって、共通部分がtruncable primeで、どちらかがなくなったら終わりです。 #################### library #################### fn print_list(a: List[Int]…

https://atcoder.jp/contests/abc358/tasks/abc358_f基本、Kの最小は高さで、これに偶数を足した数ならOKです。ただ、高さが1のときは別です。 高さが偶数なら、適当に左に行って帰ってくるを繰り返すだけなので簡単です。 奇数だとだいぶややこしくなります…

https://atcoder.jp/contests/abc358/tasks/abc358_e母関数を考えればよいですが、組合せじゃなくて順序も考えなければならないので指数関数型の母関数ですね。例えば、Aが2個、Bが1個で3文字を考えると、AAB、ABA、BAAの3通りが考えられます。これは母関数…

https://atcoder.jp/contests/abc358/tasks/abc358_dソートして尺取り法っぽいことをするだけですね。 // Souvenirs #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io</t:>…

https://projecteuler.net/problem=3610進で回文数を出してそれが2進で回文数になっているか調べるくらいですが、2進で考えると回文数は必ず奇数になるんですね。 これを進めて考えると、例えば、17xxxという10進数を2進にすると10xx…となりますが、末尾を考…

https://atcoder.jp/contests/abc357/tasks/abc357_e木よりエッジが一つ多いので、ループができます。連結成分ごとに一つループができます。ループに含まれないノードはエッジを辿っていくとループに行き着きます。 なので、ループ上のノードはループのサイ…

https://atcoder.jp/contests/abc357/tasks/abc357_dの桁数をとして、 を求めるだけですが、すぐにオーバーフローするので大変です。Fermatの小定理も使わないといけません。 // 88888888 #![allow(non_snake_case)] //////////////////// library /////////…

https://projecteuler.net/problem=35エラトステネスの篩を使えば簡単ですが、これだとせいぜい10^9までです。 2桁以上だと1, 3, 7, 9しか使えないので、これらからなる整数を作ってMiller-Rabinで素数判定すればいいです。 さらに攻めると、その整数の中で…

https://atcoder.jp/contests/abc356/tasks/abc356_eなので、そこまでの値がいくつあるかを調べます。分母がnなら分子が[nq, n(q+1))の範囲なら値がqになります。 // Max/Min #![allow(non_snake_case)] //////////////////// library //////////////////// …

https://atcoder.jp/contests/abc356/tasks/abc356_dビットごとにカウントすると簡単です。 // Masked Popcount #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::st</t:>…