Advent of Code
毎日2題出題されます。競技プログラミングチックに楽しめます。
この問題概要と実装解答を以下にご紹介します。
問題概要は生成AIに書いてもらったものを貼り付けています。
実装は人間が行なっています。
Day 12: Christmas Tree Farm
part1 問題概要
入力が以下のように与えられます。
入力で与えられた$n * m$の長方形にid: iの3 * 3の正方形をn個というのをすべて重ならずに置けるかどうかを判定してという問題です。
図形は回転OKです。
0:
###
##.
##.
1:
###
##.
.##
2:
.##
###
##.
3:
##.
###
##.
4:
###
#..
###
5:
###
.#.
###
4x4: 0 0 0 0 2 0
12x5: 1 0 1 0 2 2
12x5: 1 0 1 0 3 2
解答
みんな大好きpolynomioが頭をよぎりました。
ただ、本番入力を見てみると値がデカすぎます。
いくらなんでも全探索できません。
38x47: 30 28 36 34 25 27
47x38: 42 45 49 50 43 45
41x40: 53 37 45 43 39 34
43x43: 44 51 43 48 50 50
36x36: 10 17 29 26 31 30
40x36: 35 37 41 46 38 25
全探索以外に妥当な方法が見つからず、さすがに困ってしまってしまいました...
本当に方法がわからないので、探索が必要なものを炙り出すことにしました。
逆に探索が必要ないものは以下の2通りが考えられました。
- 3 * 3を重ねずに置いていってもおけるくらいh * wが大きければ必ずおける。
-
#の数を数えて、その数がh * wより大きければどう頑張っても置けない
すると、すべて↑のケースで弾かれることがわかりました。
つまりは入力で与えられるケースは適当においても余裕があるケースか、どう頑張ってもおけないケースしか与えられてきませんでした。
よって本当は解けていませんが、この入力では解くことができました。
これ本当に現実的な時間で弱いケース以外も判定する方法あるんですかね...
use itertools::Itertools;
use proconio::{input, marker::Chars};
fn main() {
let mut blocks = vec![];
let count = 6;
let case = 1000;
let mut bs = vec![];
for _ in 0..count {
input! {
_n: String,
s: [Chars; 3]
}
bs.push(s.iter().flatten().filter(|&&e| e == '#').count());
blocks.push(s);
}
let mut ans = 0usize;
for _ in 0..case {
input! {
mut s: String,
count: [usize; 6]
}
s.pop();
let s = s.split('x').collect_vec();
let h = s[0].parse::<usize>().unwrap();
let w = s[1].parse::<usize>().unwrap();
let cs = count.iter().sum::<usize>();
let mut c = 0;
for i in 0..6 {
c += count[i] * bs[i];
}
if h / 3 * w / 3 >= cs {
ans += 1usize;
} else if c > h * w {
continue;
} else {
// ここを通るケースがないのでこれでこの問題はとけます...
panic!("ここを通ると他の解法が必要です...!!")
}
}
println!("{}", ans);
}
atcoderでは絶対に出題されないようなコーナーケース的な問題で面白かったです
part2
省略します。part1を解いてお読みください。
終わりに
無事すべての問題を解けてピカピカになりました！！
楽しかったです。来年もやりたいです！