Advent of Code
毎日2題出題されます。競技プログラミングチックに楽しめます。
この問題概要と実装解答を以下にご紹介します。
問題概要は生成AIに書いてもらったものを貼り付けています。
実装は人間が行なっています。
Day 3: Lobby
part1 問題概要
- 入力は複数行の数字列（例：987654321111111 など）。
- 各行は「バッテリーバンク」を表していて、1桁1桁が 電池の「電圧 (1〜9)」
- 各バンクでは、ちょうど2つの電池を選んで ON にする。
- 桁の順番は並べ替えできない。
- 例えば 12345 で 2番目と4番目の電池をつけると、24 ジョルト。
- 各バンクについて、その行の中から2つ位置を選ぶ
- その2つの桁で作れる2桁の数のうち 最大のもの を求める
最後に：
すべてのバンクについて求めた「最大ジョルテージ」を全部足した合計
→ これが答え。
解答
入力が200行しかなく、各行も100桁くらいの数で飛んでくるので $\binom{100}{2} = 4950$ なので4950 * 200なので全探索しても余裕です。
ただ、選べるものを貪欲に取った方が計算量的に優しいと思ったので、mapを使って貪欲に取りました。
ここで言う「選べるもの」とは10の位としてとった数より右になる数字全部をさします。
fn main() {
let n = 200;
input! {
s: [Chars; n]
}
let nums = s
.iter()
.map(|e| {
e.iter()
.map(|e| e.to_string().parse::<usize>().unwrap())
.collect_vec()
})
.collect_vec();
let mut ans = 0;
for row in nums.iter() {
let mut map = BTreeMap::new();
for &num in row.iter() {
map.entry(num).and_modify(|e| *e += 1).or_insert(1usize);
}
let mut t = 0;
for &num in row.iter() {
let &pre = map.get(&num).unwrap();
if pre == 1 {
map.remove(&num);
} else {
map.insert(num, pre - 1);
}
let la = map.last_key_value();
if la.is_none() {
continue;
}
let &la = la.unwrap().0;
let now = num * 10 + la;
t = max(t, now);
}
ans += t;
}
println!("{}", ans);
}
part2 問題概要
part1では2桁で最大のものを選んでいましたが、part2では12桁になります。
解答
$\binom{100}{12} = 1.0504210511E15$ なのでいくらなんでも全探索ができません。
- 大きい数字からとっていきたい
- 後で選べる余地を大きくしたいので、なるべく左の数字をとりたい
ということはわかるので、選べる数字を貪欲に取る解放で解けます。
ここで言う「選べるもの」とは、その桁をとっても12桁埋められる数字全体です。
例えば、12桁の一番大きい位を埋めようとして、おしり11個の中から選んでとってしまうと12桁埋められなくなってしまうので、こういう値はのぞいて貪欲に数字を埋めていきます
fn main() {
let n = 200;
let choose = 12;
input! {
s: [Chars; n]
}
let nums = s
.iter()
.map(|e| {
e.iter()
.map(|e| e.to_string().parse::<usize>().unwrap())
.collect_vec()
})
.collect_vec();
let mut ans = 0;
for row in nums.iter() {
let mut set = BTreeSet::new();
let fe = row.len() - choose;
for i in 0..=fe {
set.insert((Reverse(row[i]), i));
}
let mut now = 0;
let mut a: Vec<usize> = vec![];
while a.len() < choose {
let fi = set.pop_first().unwrap();
if fi.1 < now {
continue;
}
now = fi.1;
let fi = fi.0.0;
a.push(fi);
if fe + a.len() < row.len() {
set.insert((Reverse(row[fe + a.len()]), fe + a.len()));
}
}
assert_eq!(a.len(), choose);
let num = a.iter().join("").parse::<usize>().unwrap();
ans += num;
}
println!("{}", ans);
}
終わりに
day4も頑張ります！