들어가며
Qualification 라운드에서 “파싱을 FSM으로 짜볼까?” 같은 이상한 생각을 하고 그렇게 풀었는데(잘못된 선택이었다), 이번 라운드에서도 “요즘 Rust 배우는 중인데 Rust로 짜볼까?” 같은 이상한 생각을 하고 그렇게 풀었다(역시 잘못된 선택이었다). 대신 Rust 숙련도가 기대했던 것보다 많이 늘었다. 이번 라운드는 Rust의 패배가 아니라 러폭도 콰즈의 패배다…
Rust 좋고 튼튼한 언어긴 한데, 확실히 C++에 비해 코드가 장황한 점은 있었다. 해커컵 치기 전에 BOJ에서 몇 문제 풀고 왔는데 남들 500 바이트 나오는 코드가 2500 바이트 나왔다. Rust로 더럽게(모든 루틴을 main에 넣는다든지) 짜면 더 줄일 수 있을 것 같긴 한데, 일단은 Rust로 PS를 계속 하려면 여러 스타일을 다양하게 테스트 해 볼 필요성이 있다고 느꼈다.
이게 다 Rust 때문이고 C++로 풀었으면 더 잘했을 거거든요! – 정신승리를 시전중
풀이
Pie Progress
각 날짜별로 파이 가격을 sorting하고, 세금까지 계산해서 파이를 k개 샀을 때 돈을 얼마나 내야 하는지를 계산한다. 다음으로 각 날짜 i가 지났을 때 파이 j개가 남도록 할 때, 최적의 전략을 선택했을 때 소모하는 금액을 DP를 이용해 계산한다.
pie_progress.rs
use std::fmt::Debug;
use std::str::{FromStr, SplitWhitespace};
trait Parser {
fn read<T, E>(&mut self) -> T
where T: FromStr<Err = E>,
E: Debug;
}
impl<'a> Parser for SplitWhitespace<'a> {
fn read<T, E>(&mut self) -> T
where T: FromStr<Err = E>,
E: Debug {
self.next().expect("End of file")
.parse::<T>().expect("Parse Error")
}
}
//==============================================================================
use std::cmp::min;
use std::io;
use std::io::Read;
struct Input {
num_day: i32,
num_pie: i32,
price: Vec<Vec<i32>>,
}
fn read_input(iter: &mut SplitWhitespace) -> Input {
let num_day: i32 = iter.read();
let num_pie: i32 = iter.read();
let mut price = Vec::new();
price.push(vec!());
for _ in 0..num_day {
let mut day_price = Vec::with_capacity(num_pie as usize);
for _ in 0..num_pie {
day_price.push(iter.read());
}
price.push(day_price);
}
Input {
num_day: num_day,
num_pie: num_pie,
price: price,
}
}
fn solve(input: Input) -> i32 {
let num_day = input.num_day;
let price = input.price;
let day_size = (num_day+1) as usize;
let mut dp = vec!(vec!(std::i32::MAX; day_size); day_size);
dp[0][1] = 0;
for day in 1usize..day_size {
let mut today_price = price[day].clone();
today_price.sort();
let mut cost = Vec::with_capacity(day_size);
cost.push(0);
for (i, pie_price) in today_price.iter().enumerate() {
let current_cost = cost[i] + pie_price + 2*(i as i32) + 1;
cost.push(current_cost);
}
for stored_pie in 1usize..day_size {
let prev_price = dp[day-1][stored_pie];
if prev_price == std::i32::MAX { break }
for (i, pie_cost) in cost.iter().enumerate() {
if stored_pie-1+i >= day_size { break }
let cell = &mut dp[day][(stored_pie-1+i) as usize];
*cell = min(*cell, prev_price + pie_cost);
}
}
}
dp[num_day as usize][1]
}
fn main() {
let mut buffer = String::new();
io::stdin().read_to_string(&mut buffer).expect("Failed to read input");
let mut iter = buffer.split_whitespace();
let num_case: i32 = iter.read();
for now_case in 1..(num_case+1) {
let input = read_input(&mut iter);
println!("Case #{}: {}", now_case, solve(input));
}
}
Manic Moving
플로이드-와셜 알고리즘으로 각 도시들 사이의 최단 경로를 구해 두고, 1차원 DP를 돌렸다. i번째 사람의 이사 계획이 s[i]에서 e[i]로 가는 것이라고 하면, 내가 시작할 수 있는 상태는 두 가지가 있다.
- s[i]에서 시작(i-1번째 사람의 짐을 내려놓고 그 다음 i번째 사람의 짐을 들러 왔다)
- e[i-1]에서 시작(i-1번째 사람의 짐을 나르는 도중 i번째 사람의 짐을 들었다)
각 두 가지 시작 케이스에 대해 (current) -> e[i] -> s[i+1]인 경우와 (current) -> s[i+1] -> e[i]인 경우 두 가지를 처리하면 된다.
근데 틀렸다. 왜 틀렸지?
(추가) 제보를 받고 틀린 부분을 찾았다. 중복 간선이 있어서 floyd[edge.from][edge.to] = edge.gas; 이렇게 하면 안 되고 min을 씌워 주어야 한다.
manic_moving.rs
use std::fmt::Debug;
use std::str::{FromStr, SplitWhitespace};
trait Parser {
fn read<T, E>(&mut self) -> T
where T: FromStr<Err = E>,
E: Debug;
}
impl<'a> Parser for SplitWhitespace<'a> {
fn read<T, E>(&mut self) -> T
where T: FromStr<Err = E>,
E: Debug {
self.next().expect("End of file")
.parse::<T>().expect("Parse Error")
}
}
//==============================================================================
use std::cmp::min;
use std::io;
use std::io::Read;
#[derive(Clone)]
struct Edge {
from: usize,
to: usize,
gas: i32,
}
struct Customer {
start: usize,
dest: usize,
}
struct Input {
num_city: usize,
graph: Vec<Vec<Edge>>,
customers: Vec<Customer>,
}
fn read_input(iter: &mut SplitWhitespace) -> Input {
let num_city = iter.read();
let num_edge = iter.read();
let num_customers = iter.read();
let city_size = (num_city+1) as usize;
let mut graph = vec![vec!(); city_size];
for _ in 1..city_size { graph.push(Vec::new()); }
for _ in 0..num_edge {
let a: usize = iter.read();
let b: usize = iter.read();
let gas: i32 = iter.read();
graph[a].push(Edge {
from: a,
to: b,
gas: gas,
});
graph[b].push(Edge {
from: b,
to: a,
gas: gas,
});
}
let mut customers = Vec::new();
for _ in 0..num_customers {
customers.push(Customer {
start: iter.read(), dest: iter.read()
})
}
Input {
num_city: num_city,
graph: graph,
customers: customers,
}
}
const INF: i32 = 7_0000_0000;
fn solve(input: Input) -> i32 {
let customers = &input.customers;
let city_size = (input.num_city+1) as usize;
let customer_size = customers.len();
let mut floyd = vec!(vec!(INF; city_size); city_size);
for i in 1..city_size { floyd[i][i] = 0; }
for v in input.graph {
for edge in v {
floyd[edge.from][edge.to] = edge.gas;
}
}
for k in 1..city_size {
for i in 1..city_size {
for j in 1..city_size {
if floyd[i][j] > floyd[i][k]+floyd[k][j] {
floyd[i][j] = floyd[i][k]+floyd[k][j];
}
}
}
}
let mut load = vec![INF; customer_size];
let mut preload = vec![INF; customer_size];
let mut last_preload = 0;
load[0] = floyd[1][input.customers[0].start];
let last_index = input.customers.len()-1;
for (i, customer) in input.customers.iter().enumerate() {
if i == last_index { break }
let next_start = input.customers[i+1].start;
load[i+1] = min(
load[i] + floyd[customer.start][customer.dest] + floyd[customer.dest][next_start],
preload[i] + floyd[last_preload][customer.dest] + floyd[customer.dest][next_start],
);
preload[i+1] = min(
load[i] + floyd[customer.start][next_start] + floyd[next_start][customer.dest],
preload[i] + floyd[last_preload][next_start] + floyd[next_start][customer.dest],
);
if load[i+1] >= INF && preload[i+1] >= INF {
return -1;
}
last_preload = customer.dest;
}
let customer = &customers[last_index];
let ans = min(
load[last_index] + floyd[customer.start][customer.dest],
preload[last_index] + floyd[last_preload][customer.dest],
);
if ans == INF { -1 } else { ans }
}
fn main() {
let mut buffer = String::new();
io::stdin().read_to_string(&mut buffer).expect("Failed to read input");
let mut iter = buffer.split_whitespace();
let num_case: i32 = iter.read();
for now_case in 1..(num_case+1) {
let input = read_input(&mut iter);
println!("Case #{}: {}", now_case, solve(input));
}
}
Fighting the Zombies
리넘버링 해서 
으로 사각형 두 개를 잡아서 루프를 돌며 세는 문제라고 생각했으나, 원 영역에 애매하게 걸치는 바람에 이동 후 사각형 밖에 존재하게 되어 버리는 점이 생기지 않는지를 엄밀하게 검증하기 싫어서 Beach Umbrellas 문제로 넘어갔다. 맞은 분들 솔루션 보니까 처음 생각한대로 풀면 되는 것 같다. 대회 끝나고 후기를 퇴고하면서 항상 가능하다는 걸 보였는데, 원 반지름을 무한으로 보내서 사각형이 겹치지 않는 경우 그 사이에 선을 긋고(여기까진 대회 도중 생각했다), 겹치는 경우에는 교점 두 개를 대상으로 선을 그어 공간을 분할하면 항상 사각형 두 개를 고르는 경우로 치환 가능하다는 걸 알게 되었다.
Beach Umbrellas
가장 끝에 들어갈 우산 두 개를 루프 돌리고, 나머지 빈 칸에 대해 중복조합과 순열을 이용해 열심히 계산하면 된다. 수식으로는 다음과 같고, modular inverse를 써서 계산한 뒤 
을 곱해 차례로 더하면 된다.
내 코드 시간복잡도가 
인줄 알고 input 파일을 다운 받았는데 알고보니 
이라서 망한 문제다. 최적화 하려면 할 수는 있는 부분이었지만 6분만에 익숙하지 않은 언어로 고치기는 불가능했다. 다행히 6분은 꽤 길기 때문에 시간 내에 답이 나올듯 말듯 진행됐는데, 30초쯤 남았을 때 95번 정도고 마지막에 최대 크기 데이터가 몰려 있는걸 보고 포기하고 코드 전시라도 하자 싶어서 그 때까지의 출력을 복사한 다음 뒤쪽을 다 0으로 채운 fuck.txt를 제출했다. 그런데 7초 남기고 100번까지 결과가 다 나왔다! 하지만 파일 포커스가 fuck.txt에 맞춰져 있어서 output.txt로 바꿔야 했고, Rust는 Working Directory의 src 폴더 안에 소스가 들어 있어서 output.txt와 main.rs가 들어 있는 디렉터리가 달라 제출 할 때 폴더 이동이 필요했다. 결국 클릭이 2초쯤 느려서 제출하지 못했다. 맞은 분들 코드 보니까 도 종종 보이는 걸 보고 아쉬웠다.
Expire 되고 나서 20분쯤 남았는데, 제출한 게 다 맞아야 R2를 진출한다는 부담감이 있었지만 20분 안에 한 문제를 못 풀 것 같아서 씻으러 갔다. 씻고 왔더니 3번이 틀려 있었고 R2의 꿈은 저편으로…
beach_umbrellas.rs
use std::fmt::Debug;
use std::str::{FromStr, SplitWhitespace};
trait Parser {
fn read<T, E>(&mut self) -> T
where T: FromStr<Err = E>,
E: Debug;
}
impl<'a> Parser for SplitWhitespace<'a> {
fn read<T, E>(&mut self) -> T
where T: FromStr<Err = E>,
E: Debug {
self.next().expect("End of file")
.parse::<T>().expect("Parse Error")
}
}
//==============================================================================
use std::io;
use std::io::Read;
struct Input {
num_spot: i64,
radius: Vec<i64>,
}
fn read_input(iter: &mut SplitWhitespace) -> Input {
let num_umbrella = iter.read();
let num_spot = iter.read();
let mut radius = Vec::new();
for _ in 0..num_umbrella {
radius.push(iter.read());
}
Input {
num_spot: num_spot,
radius: radius,
}
}
const MOD: i64 = 1_000_000_007;
fn modinv(val: i64) -> i64 {
let (mut a, mut b) = (val, MOD);
let (mut x0, mut x1) = (0, 1);
while a > 1 {
let q = a / b;
let t = b;
b = a%b;
a = t;
let t = x0;
x0 = x1 - q*x0;
x1 = t;
}
if x1 < 0 { x1 += MOD };
x1
}
fn solve(input: Input) -> i64 {
let n = input.radius.len();
let radius = &input.radius;
if n == 1 {
return (input.num_spot as i64) % MOD;
}
let radius_sum = radius.iter().fold(0, |acc, v| acc+v*2) as i64;
let ordering = (1i64..(n-1) as i64).fold(1i64, |acc, v| acc*v%MOD);
let inversed = (1i64..(n+1) as i64).fold(1i64, |acc, v| acc*modinv(v)%MOD);
let mut ans = 0i64;
for left in 0..n {
for right in left+1..n {
let radius_sum = radius_sum - radius[left] - radius[right];
let free_spot = input.num_spot-1 - radius_sum;
if free_spot < 0 {
continue;
}
// n+1 H free_spot = free_spot+n C free_spot = free_spot+n C n
let mut delta = ordering * inversed % MOD;
for i in 0i64..n as i64 {
delta = delta * (free_spot+n as i64 - i) % MOD;
}
ans = (ans + delta*2) % MOD;
}
}
ans % MOD
}
fn main() {
let mut buffer = String::new();
io::stdin().read_to_string(&mut buffer).expect("Failed to read input");
let mut iter = buffer.split_whitespace();
let num_case: i32 = iter.read();
for now_case in 1..(num_case+1) {
let input = read_input(&mut iter);
println!("Case #{}: {}", now_case, solve(input));
}
}