Advent of Code
毎日2題出題されます。競技プログラミングチックに楽しめます。
この問題概要と実装解答を以下にご紹介します。
問題概要は生成AIに書いてもらったものを貼り付けています。
実装は人間が行なっています。
Day 9: Movie Theater
part1 問題概要
.と#を持つ2次元グリッドの#の座標が配列で与えられます。
#を対角線に持つ長方形の中で面積が一番大きいものの面積を教えて！
解答
全探索です。#の頂点数は ~= 400なので全探索を余裕でできます。
use std::cmp::max;
use itertools::Itertools;
use proconio::input;
fn parse_input(s: &str) -> (usize, usize) {
let s = s.split(',').collect_vec();
let a = s[0].parse::<usize>().unwrap();
let b = s[1].parse::<usize>().unwrap();
(a, b)
}
fn main() {
let n = 496;
input! {
s: [String; n]
}
let ab = s.iter().map(|e| parse_input(e)).collect_vec();
let mut ans = 0;
for &(a1, b1) in ab.iter() {
for &(a2, b2) in ab.iter() {
ans = max(ans, (a1.abs_diff(a2) + 1) * (b1.abs_diff(b2) + 1));
}
}
println!("{}", ans);
}
part2 問題概要
実は入力はi個目の座標と i + 1個目の座標がx軸もしくはy軸に水平となります。
また、これを結ぶと交差なく1つの図形に閉じます。
この図形の外側の領域(.)が入ることなく作れる長方形のうち、対角線2点が # になるような長方形の最大の面積を教えて！
解答
めんどくさい問題です。
座標はx, yともに <= 10^5 くらいなので、2次元座標をそのまま持つことはできないので、
座圧して 400 * 400くらいのオーダーにしておいてから、その中に範囲外の箇所がないかを2次元累積和を使って計算して、範囲外の箇所を含んだ面積ではないかのチェックをしつつ面積を計算するという問題です。
範囲外かどうかはある1点が外側かどうかさえわかればBFSで塗っていけるので座圧したグリッドの上下左右にマージン設けておいて(外側は必ず.にするようにしておいて)、(0, 0)からBFSすることで必ず外堀埋められるようにしています。
AIではどう頑張っても書いてくれないレベルでコードが汚いです。
use std::{
cmp::{max, min},
collections::{HashMap, VecDeque},
};
use itertools::Itertools;
use proconio::input;
fn parse_input(s: &str) -> (usize, usize) {
let s = s.split(',').collect_vec();
let a = s[0].parse::<usize>().unwrap();
let b = s[1].parse::<usize>().unwrap();
(b, a)
}
fn main() {
let n = 496;
input! {
s: [String; n]
}
let ab = s.iter().map(|e| parse_input(e)).collect_vec();
let mut is = ab.iter().map(|e| e.0).collect_vec();
let mut js = ab.iter().map(|e| e.1).collect_vec();
is.sort();
is.dedup();
js.sort();
js.dedup();
let imap = {
let mut imap = HashMap::new();
let mut id = 1;
for &num in is.iter() {
imap.insert(num, id);
id += 1usize;
}
imap
};
let jmap = {
let mut jmap = HashMap::new();
let mut id = 1;
for &num in js.iter() {
jmap.insert(num, id);
id += 1usize;
}
jmap
};
let h = imap.len() + 2;
let w = jmap.len() + 2;
let mut table = vec![vec![false; w]; h];
let mut idx = vec![];
for &(a, b) in ab.iter() {
let &aa = imap.get(&a).unwrap();
let &bb = jmap.get(&b).unwrap();
idx.push((aa, bb));
}
for i in 0..n {
let (a1, b1) = idx[i];
let (a2, b2) = idx[(i + 1) % n];
if a1 == a2 {
let l = min(b1, b2);
let r = max(b1, b2);
for col in l..=r {
table[a1][col] = true;
}
} else {
let l = min(a1, a2);
let r = max(a1, a2);
for row in l..=r {
table[row][b1] = true;
}
}
}
let mut que = VecDeque::new();
let mut blank = vec![vec![0; w]; h];
que.push_back((0, 0));
let didj = vec![(1, 0), (-1, 0), (0, 1), (0, -1)];
while !que.is_empty() {
let (i, j) = que.pop_front().unwrap();
for &(di, dj) in didj.iter() {
let ni = i as isize + di;
let nj = j as isize + dj;
if ni < 0 || ni >= h as isize || nj < 0 || nj >= w as isize {
continue;
}
let ni = ni as usize;
let nj = nj as usize;
if table[ni][nj] {
continue;
}
if blank[ni][nj] == 1 {
continue;
}
blank[ni][nj] = 1usize;
que.push_back((ni, nj));
}
}
let mut acc = vec![vec![0usize; w]; h];
for i in 0..h {
for j in 0..w {
if blank[i][j] == 0 {
continue;
}
acc[i][j] = 1;
}
}
for i in 0..h {
for j in 0..w - 1 {
acc[i][j + 1] += acc[i][j];
}
}
for j in 0..w {
for i in 0..h - 1 {
acc[i + 1][j] += acc[i][j];
}
}
let mut ans = 0;
for &(i1, j1) in idx.iter() {
for &(i2, j2) in idx.iter() {
let li = min(i1, i2);
let ri = max(i1, i2);
let lj = min(j1, j2);
let rj = max(j1, j2);
let bc = acc[ri][rj] + acc[li - 1][lj - 1] - acc[ri][lj - 1] - acc[li - 1][rj];
if bc != 0 {
continue;
}
let idiff = is[max(li, ri) - 1] - is[min(i1, i2) - 1] + 1;
let jdiff = js[max(j1, j2) - 1] - js[min(j1, j2) - 1] + 1;
ans = max(ans, idiff * jdiff);
}
}
println!("{}", ans);
}
終わりに
day10もがんばります！