AtCoder Beginner Contest 439
久々にrated参加しまして、70分2ペナでのA~D4完でした。
レートは1054→1041(-13)です。
今回はA~Dの感想を書きます。
A - 2^n - 2*n
ただ計算するだけではありますが、Rustの冪乗の書き方に慣れてないと少し戸惑うかもしれません。
計算結果の型は基数と同じで、指数はu32にしなければならないのですね。
use proconio::input;
fn main() {
input! {
n: usize,
}
println!("{}", 2_usize.pow(n as u32) - 2 * n);
}
B - Happy Number
B問題にしては少し難しかった気がします。
各桁の二乗和を取る操作を十分大きい回数行うことで$1$になるかどうかを判定できるのか、またその十分大きい回数とは何回なのかを考える必要があるからです。
（落ち着いて考えれば、$N$が$2026$以下かつ各桁の二乗和の総和が$3\times9^2=243$なので、$243$回も操作すればどこかでループが生じることは明白なのですが）
そこで、以下のようなBFS的な考え方でこの問題を解こうと考えました。
つまり、ハッピー数の集合を$C$として$C=\{1\}$からスタートして、$[1,N]$までで二乗和の総和が$C$に含まれるような数を探索し、もし含まれる場合その数を$C$に投入します。
例）
C={1}
↓
C={1,10,100,1000}
↓
C={1,13,31,...}
↓
...
このような操作を十分大きな回数行えば、$[1,N]$のすべての数が$C$に投入されるか、操作の途中で$C$に投入される数がなくなるかによって、$C$の集合が変化せず安定するようになります（操作の方はたったの$4$回で収束し、ハッピー数は合計で$302$個のようです）。
したがって、この状態の$C$に$N$が含まれているかどうかを判定することで$N$がハッピー数かどうかがわかります。
なお、筆者は$C$に$[1,N]$の値（解答コードのj）ではなく何回目の操作か（解答コードの_i）を投入してしまったことに気付けず2ペナと大幅なタイムロスをしてしまいました。
use proconio::input;
use std::collections::HashSet;
fn main() {
input! {
n: usize,
}
let mut set: HashSet<_> = HashSet::new();
for i in 0..=8 {
set.insert(10usize.pow(i));
}
for _i in 1..=2026 {
for j in 1..=2026 {
let mut sum = 0;
for k in 0..=3 {
let base = (j / (10usize.pow(k))) % 10;
sum += base.pow(2);
}
if set.contains(&sum) {
set.insert(j);
}
}
}
if set.contains(&n) {
println!("Yes")
} else {
println!("No")
};
}
C - 2026
エラストテネスの篩が必要かと思いきや、単なる全探索で解くことができました。
あとは、$x<y$を守りつつ、map等で$x^2+y^2=n$となるような$n$についていくつの$(x,y)$の組があるかを数えればよいだけです。
use itertools::Itertools;
use proconio::input;
use std::collections::HashMap;
fn main() {
input! {
n: usize,
}
let mut ans = vec![];
let mut map: HashMap<_, _> = HashMap::new();
for i in 1..3200 {
for j in i+1..3200 {
let key = i * i + j * j;
*map.entry(key).or_insert(0) += 1;
}
}
for (&key, &val) in &map {
if val == 1 && key <= n {
ans.push(key);
}
}
ans.sort();
println!("{}", ans.len());
println!("{}", ans.iter().join(" "));
}
D - Kadomatsu Subsequence
$\min(i,j,k)=j$のとき、$j$よりも右にあるような$A_i:A_j:A_k=7:5:3$を満たす$(i,k)$の個数がそれぞれ$r_i,r_k$だとわかっているならば、$(i,k)$の組み合わせの数は、$r_i\times r_k$ですし、$j$よりも左にあるような$A_i:A_j:A_k=7:5:3$を満たす$(i,k)$の個数がそれぞれ$l_i,l_k$だとわかっているならば、$(i,k)$の組み合わせの数は、$l_i\times l_k$です。
つまり、任意の$j$について、$r_i, r_k, l_i, l_k$さえ高速にわかればこの問題を解くことができます。
配列$A$の要素を左から順に見ていくことにすると、$7,3$いずれかの倍数の値に遭遇したとき、任意の比率$x$をkeyとするHashMapに出現回数を加算していくことで任意の$j$について$l_i,l_k$の値を求めることができます。
また、あらかじめ全体として比率$x$の$7,3$いずれかが何回出現するかを前計算しておくことによって、それらから$l_i,l_k$を差し引くことで$r_i,r_k$も求めることができます。
なお、注意点として$l_i,l_k$は$j$のカウント処理の前、$l_i,l_k$は$j$の後に処理しないとズレてしまいます。
以上で、全体として$O(N)$の計算量でこの問題を解くことができました。
use proconio::input;
use std::collections::HashMap;
fn main() {
input! {
n: usize,
a: [usize; n],
}
let mut ans = 0;
let mut map: HashMap<usize, (usize, usize, usize)> = HashMap::new();
for i in 0..n {
let e = a[i];
let mut tp = (0, 0, 0);
if e % 7 == 0 {
tp.0 = e / 7;
map.entry(tp.0).or_insert((0, 0, 0)).0 += 1;
}
if e % 5 == 0 {
tp.1 = e / 5;
map.entry(tp.1).or_insert((0, 0, 0)).1 += 1;
}
if e % 3 == 0 {
tp.2 = e / 3;
map.entry(tp.2).or_insert((0, 0, 0)).2 += 1;
}
}
let mut cur: HashMap<usize, (usize, i32, usize)> = HashMap::new();
for (&key, &val) in &map {
if val.1 > 0 {
cur.entry(key).or_default();
}
}
for i in 0..n {
let e = a[i];
let mut tp = (0, 0, 0);
if e % 7 == 0 {
tp.0 = e / 7;
cur.entry(tp.0).or_insert((0, 0, 0)).0 += 1;
}
if e % 5 == 0 {
let key = e / 5;
ans += cur.get(&key).unwrap().0 * cur.get(&key).unwrap().2;
tp.1 = e / 5;
cur.entry(tp.1).or_insert((0, 0, 0)).1 += 1;
ans += (map.get(&key).unwrap().0 - cur.get(&key).unwrap().0)
* (map.get(&key).unwrap().2 - cur.get(&key).unwrap().2)
}
if e % 3 == 0 {
tp.2 = e / 3;
cur.entry(tp.2).or_insert((0, 0, 0)).2 += 1;
}
}
println!("{}", ans);
}
まとめ
Rustが難しすぎて、実装だけでB問題に10分かかってしまいました。
また、所有権などRust特有の考慮事項も多く、考え方がそもそも違うのか、実装不備なのかがわからないためかなり苦戦してしまいます。
これを高速に書けるプログラマーは本当にすごいです。