글쓴이 ·0개의 댓글

오랜만의 블로그 포스트가 알고리즘 대회 후기가 될 것이라고 예상하지 못했는데, 마지막 글이 올라온지도 꽤 됐고 이번 대회에서 하고 싶은 얘기도 있어서 포스팅을 하기로 했다. 현재 나는 작년 ICPC 이후로 공식적으로는 경쟁 프로그래밍을 은퇴한 상태다. 평소에 공부하고 시간 쓰는건 완전히 멈췄고, 대신 거기 쓰던 시간을 워게임 등 해킹 문제를 풀거나 졸업 후 진로 준비에 쓰고 있다. 이렇게 말하니까 알고리즘 공부에 계속 시간을 많이 쓰고 노력했던 것 같지만 은퇴 선언 이전에도 실질적으로 손을 놓은지는 꽤 됐다. 지금은 티셔츠나 상금 등 부상 주는 대회를 가끔 부담 없이 나가는 걸 목표로 하고 있다.

원래 이번 코드잼은 Rust로 알고리즘 라이브러리를 짜고 그걸 써서 대회를 치고, 대회와 대회 사이에 라이브러리를 보강한 뒤 대회 이후 프로젝트를 다듬어서 공개한다는 원대한 계획과 함께하고 있었다. 하지만 코드잼 플랫폼이 바뀌고 Rust가 지원 언어 목록에 없어서 라이브러리 작성에 대한 관심이 급격하게 식었고, 다익스트라 알고리즘 정도만 겨우 구현된 Rust 알고리즘 라이브러리는 지금까지 존재했던 나만 알고 있다가 비트의 저편으로 사라졌던 많은 개인 프로젝트와 마찬가지로 GitHub 개인 저장소에 조금 더 머무르다 영영 사라질 예정이다. Cargo 배포용으로 이름도 지어줬는데 불쌍한 친구…

올해 코드잼 연습 세션을 치고 나서 느꼈던 건 생각하는 능력 자체는 예상보다 덜 줄었고, 전통적인 테크닉을 떠올리거나 코드를 빠르게 짜는 능력은 예상보다 많이 줄었다는 거였다. 여기서 “생각하는 능력”은 연습 세션 3번 Steed 2 Cruise Control에서 여러 속도로 달리는 말들 사이의 불변조건을 구하는 능력을 말하고 “전통적인 테크닉”은 R1A 3번 Edgy Baking을 보고 냅색이니까 DP로 풀면 뚝딱 할 수 있겠다는 걸 떠올리는 능력을 말한다. 연습 세션부터 이번 R1A까지 예전에 비해 같은 코드를 짜는데 시간이 훨씬 오래 걸린다는게 느껴졌다.

이번 대회를 치면서 좀 놀랐던 점은 대회 중 오랜만에 초심을 되찾은 기분을 느꼈던 것이다. 내 풀이에서 놓친 점을 찾았을 때 예전 같았으면 쉬운 문제에서 실수했다고 자책했겠지만 이번 대회에서는 웬일로 풀이의 빠진 구멍을 채워 나가는 느낌이 즐겁게 느껴졌다. 알고리즘 대회에서 어려운 문제에 도전하는 지적 만족감을 느낀 적은 많았지만, 문제를 푸는 것이 아니라 시간 제한을 두고 대회를 치는 것을 즐겁다고 생각해 본지는 꽤 오래됐다. 평소에 연습을 많이 안 하니 예전만큼 잘하지 못하는 건 당연하다고 생각하면서도 무의식 속에서는 그래도 내가 경력이 얼마인데 못해도 어느 정도는 해야 한다는 부담을 느끼고 있었다고 생각한다. 나도 내가 무의식에서 어떤 생각을 하는지 완전히 모르지만, 공식적으로 은퇴했다고 선언했던게 그런 부담을 낮춰준 게 아닌가 추측하고 있다. 바뀐 플랫폼에서 스코어보드가 문제 페이지에 보이지 않는 것도 도움이 됐다.

원래 대회 후기는 문제 풀이도 함께 올리는게 전통이므로 간단한 풀이도 함께 첨부한다.

  • A: 전체 초콜릿 개수를 세고, \text{(number of H piece)}\times \text{(number of V piece)}로 나누어 떨어지는지 확인한다. 가로 분할선과 세로 분할선의 위치는 초콜릿 개수를 통해 독립적으로 판단 가능하며, 분할선들의 위치가 정해지면 분할된 각 칸에 초콜릿이 균등하게 들어가 있는지 확인한다.
  • B: 계산이 특정 시간 안에 끝날 수 있는지를 판단하는 판별 함수를 작성하고 파라메트릭 바이너리 서치를 수행한다. 판별 함수는 각 계산원이 그 시간까지 처리 가능한 비트의 수를 계산한 뒤 정렬해 큰 순서대로 R개를 뽑아 B 이상이면 처리 가능한 것이다.
  • C: 0-1 냅색. 2 \cdot w_i h_i를 미리 P에서 빼고, 물건의 크기가 min(w, h) 점수는 \sqrt{w^2 + h^2}인 냅색을 수행한다.

글쓴이 ·0개의 댓글

들어가며

대회 덕분에 오랜만에 또 문제풀이 코딩을 했다. 전부 풀긴 했는데 시간을 좀 오래 썼다. D에서 코딩 미스가 한 번 있었다. 문제풀이를 좀 쉬었을 때 풀 수 있는 문제 풀은 크게 안 변하는데, 코딩 속도나 풀이를 떠올리는 속도가 좀 줄어든 것 같다는 기분을 느꼈다.

풀이

Problem A. Oversized Pancake Flipper

같은 위치에서 두 번 뒤집는 것은 불필요하므로 왼쪽부터 하나씩 뒤집어보면 된다. O(N^2)으로 Large input이 풀리기 때문에 특별히 자료구조를 쓸 필요도 없다.

A.cpp
#include <cstdio>
#include <cstring>

const int MAX = 1020;

char cake[MAX];
int flipSize;

void solve() {
	int ans = 0;

	int len = strlen(cake);
	for (int i = 0; i <= len-flipSize; i++) {
		if (cake[i] == '-') {
			ans++;
			for (int j = i; j < i+flipSize; j++) {
				cake[j] = cake[j] == '+' ? '-' : '+';
			}
		}
	}

	// final check
	for (int i = len-flipSize+1; i < len; i++) {
		if (cake[i] == '-') {
			puts("IMPOSSIBLE");
			return;
		}
	}

	printf("%d\n", ans);
}

int main() {
	freopen("output.txt", "w", stdout);

	int numCase;
	scanf("%d", &numCase);
	for (int nowCase = 1; nowCase <= numCase; nowCase++) {
		scanf("%s%d", cake, &flipSize);

		printf("Case #%d: ", nowCase);
		solve();
	}

	return 0;
}

Problem B. Tidy Numbers

입력이 tidy한 경우 그대로 출력한다. 입력이 tidy가 아닌 경우 112333445552 형태로 증가하다가 감소하는 지점이 있을텐데, 그 감소하기 직전의 반복되는 부분(여기서는 555)의 첫 숫자를 1 낮추고, 그 뒤쪽을 전부 9로 채우면 된다.

B.cpp
#include <cstdio>
#include <cstring>

const int MAX = 20;

char data[MAX];

void solve() {
	int len = strlen(data);
	int lastIncrease = 0;

	int now;
	for (now = 1; now < len; now++) {
		if (data[now-1] > data[now]) {
			break;
		} else if (data[now-1] < data[now]) {
			lastIncrease = now;
		}
	}

	if (now == len) {
		// monotonic
		puts(data);
	} else {
		char ans[MAX];
		for (int i = 0; i < lastIncrease; i++)
			ans[i] = data[i];
		ans[lastIncrease] = data[lastIncrease]-1;
		for (int i = lastIncrease+1; i < len; i++)
			ans[i] = '9';
		ans[len] = 0;

		for (int i = 0; i < data[i]; i++) {
			if (ans[i] != '0') {
				puts(ans+i);
				return;
			}
		}
	}
}

int main() {
	freopen("output.txt", "w", stdout);

	int numCase;
	scanf("%d", &numCase);
	for (int nowCase = 1; nowCase <= numCase; nowCase++) {
		scanf("%s", data);

		printf("Case #%d: ", nowCase);
		solve();
	}

	return 0;
}

Problem C. Bathroom Stalls

시뮬레이션으로 풀 수 있다. 당연히 한 명씩 넣는 건 아니고, 연속된 구간의 크기와 개수를 이용해 시뮬레이션 하면 지수적으로 수를 줄여나가면서 O(log K)만에 해결 가능하다. 한 가지 관찰이 필요한데, 반씩 줄여 나가는 방식으로 시뮬레이션 하더라도 어떤 시점에서 구간의 크기의 종류가 최대 두 종류라는 사실이다. (n) -> (a, a+1) -> (b, b+1)과 같이 연속한 두 수에 대해서만 관리하면 되고, atomic하게 처리하지 않는 경우에도 최대 네 종류만 관리하면 된다. 탐색 최대 크기가 작아 굳이 Balanced Binary Tree를 쓸 필요는 없었지만 코딩하기 귀찮아서 set을 발라서 해결했다.

C.cpp

#include <cstdio>
#include <set>

typedef long long ll;

ll total, k;

struct state {
	ll n;
	mutable ll count;

	bool operator < (const state &t) const {
		return n < t.n;
	}
};

void insertToSet(std::set < state > &set, ll n, ll count) {
	auto it = set.find(state {n, 0});
	if (it != set.end()) {
		it->count += count;
	} else {
		set.insert(state { n, count });
	}
}

void solve() {
	state start = { total, 1 };

	std::set < state > set;
	set.insert(start);

	while (k) {
		auto it = --set.end();
		if (it->count >= k) {
			printf("%lld %lld\n", it->n/2, (it->n-1)/2);
			return;
		} else {
			k -= it->count;
			insertToSet(set, it->n/2, it->count);
			insertToSet(set, (it->n-1)/2, it->count);
			set.erase(it);
		}
	}
}

int main() {
	freopen("output.txt", "w", stdout);

	int numCase;
	scanf("%d", &numCase);
	for (int nowCase = 1; nowCase <= numCase; nowCase++) {
		scanf("%lld%lld", &total, &k);

		printf("Case #%d: ", nowCase);
		solve();
	}

	return 0;
}

Problem D. Fashion Show

굉장히 마음에 드는 문제였다. 독립된 두 개의 문제를 하나의 문제인 것처럼 섞어서 꼬아 놓았는데, 두 제한조건이 사실 독립이라는 것을 깨달아야 해결할 수 있다. 임의의 같은 가로줄/세로줄에 있는 두 모델을 골랐을 때 둘 중 최소 하나가 +여야 한다는 말은, 바꿔서 말하면 +가 아닌 칸은 같은 가로줄/세로줄에 최대 하나 존재할 수 있다는 말이다. 비숍 배치 문제처럼 가로세로, 대각선 조건에 대해 각각 이분매칭으로 해결한 뒤 겹치는 칸은 o로, 겹치지 않는 칸은 x와 +로 설정해 주면 된다.

D.cpp
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 110;

class BipartiteMatcher {
public:
	const int size;
	int *matched;
	bool *visited;

	vector < int > *edge;

	BipartiteMatcher(int size) : size(size) {
		matched = new int[2*size];
		visited = new bool[2*size];
		edge = new vector < int >[2*size];

		for (int i = 0; i < 2*size; i++) {
			matched[i] = -1;
		}
	}

	~BipartiteMatcher() {
		delete[] matched;
		delete[] visited;
		delete[] edge;
	}

	void addConnection(int a, int b) {
		assert(0 <= a && a < size && 0 <= b && b < size);
		b += size;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	vector < pair < int, int > > match() {
		for (int left = 0; left < size; left++) {
			memset(visited, 0, sizeof(bool)*(2*size));
			tryMatch(left);
		}

		vector < pair < int, int > > ret;
		for (int left = 0; left < size; left++) {
			if (matched[left] != -1) {
				ret.push_back(make_pair(left, matched[left]-size));
			}
		}

		return ret;
	}

private: 
	bool tryMatch(int left) {
		for (auto right : edge[left]) {
			if (!visited[right]) {
				visited[right] = 1;
				if (matched[right] < 0 || tryMatch(matched[right])) {
					matched[right] = left;
					matched[left] = right;
					return 1;
				}
			}
		}
		return 0;
	}
};

int gridSize, numModel;
char original[MAX][MAX], ans[MAX][MAX];

void input() {
	scanf("%d%d", &gridSize, &numModel);

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			original[r][c] = '.';
		}
		original[r][gridSize+1] = 0;
		ans[r][gridSize+1] = 0;
	}

	for (int i = 0; i < numModel; i++) {
		char t[2];
		int r, c;
		scanf("%s%d%d", t, &r, &c);
		original[r][c] = t[0];
	}

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			ans[r][c] = original[r][c];
		}
	}
}

bool rowCheck[MAX], colCheck[MAX], ldiagCheck[MAX*2], rdiagCheck[MAX*2];

void solve() {
	memset(rowCheck, 0, sizeof(rowCheck));
	memset(colCheck, 0, sizeof(colCheck));
	memset(ldiagCheck, 0, sizeof(ldiagCheck));
	memset(rdiagCheck, 0, sizeof(rdiagCheck));

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			int rowNum = r-1;
			int colNum = c-1;
			int ldiagNum = r+c-2;
			int rdiagNum = r-c+gridSize-1;
			if (ans[r][c] != '.') {
				if (ans[r][c] != '+') {
					rowCheck[rowNum] = 1;
					colCheck[colNum] = 1;
				}
				if (ans[r][c] != 'x') {
					ldiagCheck[ldiagNum] = 1;
					rdiagCheck[rdiagNum] = 1;
				}
			}
		}
	}

	BipartiteMatcher xy(gridSize), diag(gridSize*2-1);

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			int rowNum = r-1;
			int colNum = c-1;
			int ldiagNum = r+c-2;
			int rdiagNum = r-c+gridSize-1;

			if (!rowCheck[rowNum] && !colCheck[colNum]) {
				xy.addConnection(rowNum, colNum);
			}
			if (!ldiagCheck[ldiagNum] && !rdiagCheck[rdiagNum]) {
				diag.addConnection(ldiagNum, rdiagNum);
			}
		}
	}

	for (auto p: xy.match()) {
		int rowNum = p.first;
		int colNum = p.second;

		int r = rowNum+1;
		int c = colNum+1;

		if (ans[r][c] == '.') ans[r][c] = 'x';
		else if (ans[r][c] == '+') ans[r][c] = 'o';
	}

	for (auto p: diag.match()) {
		int ldiagNum = p.first;
		int rdiagNum = p.second;

		int r = (ldiagNum+rdiagNum-gridSize+3)/2;
		int c = (ldiagNum-rdiagNum+gridSize+1)/2;
		
		if (ans[r][c] == '.') ans[r][c] = '+';
		else if (ans[r][c] == 'x') ans[r][c] = 'o';
	}

	int score = 0;
	int changed = 0;
	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			if (ans[r][c] != original[r][c]) {
				changed++;
			}
			score += ans[r][c] != '.';
			score += ans[r][c] == 'o';
		}
	}

	printf("%d %d\n", score, changed);

	for (int r = 1; r <= gridSize; r++) {
		for (int c = 1; c <= gridSize; c++) {
			if (ans[r][c] != original[r][c]) {
				printf("%c %d %d\n", ans[r][c], r, c);
			}
		}
	}
}

int main() {
	freopen("output.txt", "w", stdout);

	int numCase;
	scanf("%d", &numCase);
	for (int nowCase = 1; nowCase <= numCase; nowCase++) {
		input();

		printf("Case #%d: ", nowCase);
		solve();
	}

	return 0;
}

글쓴이 ·0개의 댓글

들어가며

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]로 가는 것이라고 하면, 내가 시작할 수 있는 상태는 두 가지가 있다.

  1. s[i]에서 시작(i-1번째 사람의 짐을 내려놓고 그 다음 i번째 사람의 짐을 들러 왔다)
  2. 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

리넘버링 해서 O(N^4)으로 사각형 두 개를 잡아서 루프를 돌며 세는 문제라고 생각했으나, 원 영역에 애매하게 걸치는 바람에 이동 후 사각형 밖에 존재하게 되어 버리는 점이 생기지 않는지를 엄밀하게 검증하기 싫어서 Beach Umbrellas 문제로 넘어갔다. 맞은 분들 솔루션 보니까 처음 생각한대로 풀면 되는 것 같다. 대회 끝나고 후기를 퇴고하면서 항상 가능하다는 걸 보였는데, 원 반지름을 무한으로 보내서 사각형이 겹치지 않는 경우 그 사이에 선을 긋고(여기까진 대회 도중 생각했다), 겹치는 경우에는 교점 두 개를 대상으로 선을 그어 공간을 분할하면 항상 사각형 두 개를 고르는 경우로 치환 가능하다는 걸 알게 되었다.

Beach Umbrellas

가장 끝에 들어갈 우산 두 개를 루프 돌리고, 나머지 빈 칸에 대해 중복조합과 순열을 이용해 열심히 계산하면 된다. 수식으로는 다음과 같고, modular inverse를 써서 계산한 뒤 2\times(n-2)!을 곱해 차례로 더하면 된다.

\,_{n+1}H_{free\_spot} = \,_{free\_spot+n}C_{free\_spot} = \,_{free\_spot+n}C_n

내 코드 시간복잡도가 O(N^2)인줄 알고 input 파일을 다운 받았는데 알고보니 O(N^3)이라서 망한 문제다. 최적화 하려면 할 수는 있는 부분이었지만 6분만에 익숙하지 않은 언어로 고치기는 불가능했다. 다행히 6분은 꽤 길기 때문에 시간 내에 답이 나올듯 말듯 진행됐는데, 30초쯤 남았을 때 95번 정도고 마지막에 최대 크기 데이터가 몰려 있는걸 보고 포기하고 코드 전시라도 하자 싶어서 그 때까지의 출력을 복사한 다음 뒤쪽을 다 0으로 채운 fuck.txt를 제출했다. 그런데 7초 남기고 100번까지 결과가 다 나왔다! 하지만 파일 포커스가 fuck.txt에 맞춰져 있어서 output.txt로 바꿔야 했고, Rust는 Working Directory의 src 폴더 안에 소스가 들어 있어서 output.txt와 main.rs가 들어 있는 디렉터리가 달라 제출 할 때 폴더 이동이 필요했다. 결국 클릭이 2초쯤 느려서 제출하지 못했다. 맞은 분들 코드 보니까 O(N^3)도 종종 보이는 걸 보고 아쉬웠다.

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));
    }
}

글쓴이 ·0개의 댓글

2016년 SCPC(삼성 대학생 프로그래밍 경진대회)에 참가했다. 올해로 2회를 맞는 젊은 대회인데, 국내 대회임에도 불구하고 구글 코드잼 같은 유명 세계대회를 뛰어넘는 엄청난 규모의 상금으로 유명하다. 작년에는 미국에 있었고 온라인 예선도 까먹고 안 쳐서 주변에 상금 받은 사람들을 보면서 부러워 했었는데 올해는 기회가 돼서 본선에 참가했다.

대회 시작은 오후 1시였는데 대회장 내부에 간단하게 체험 부스 등이 준비되어 있어서 미리 와서 이벤트에 참가하는 것을 권장하더라. 포토존이나 간식거리, 체험 게임 등 이벤트로서의 준비는 굉장히 잘 되어 있었는데, 대회로서의 준비는 아무래도 경험이 적어서 그런지 아쉬운 부분이 눈에 띄었다. 대회장 내부에 음료 반입 금지라든지, 대회 시작 전 컴퓨터가 열려 있어서 미리 코드를 짜 놓는 방식의 부정행위가 가능할 것 같다는 걱정도 있었고, 채점은 g++로 하면서 로컬에는 MSVC만 깔려 있다든지 이것저것 있었다.

풀이

연습문제 – Lumbering

이벤트 문제로 영어 문제가 나왔다. 문제 자체는 간단했는데 가장 먼저 푼 사람에게만 상품을 주기 때문에 이것 때문에 괜히 빨리 풀어야 한다는 생각에 사로잡혀서 그냥 푸는 것보다 오래 걸렸다. (자르는 높이 – 자르는 시간)이 가장 작은 도끼질 시간을 찾아서, 모든 나무를 그 도끼질 한 번으로 자른다고 생각하면 된다. 처음에는 스택이나 인덱스트리 쪽으로 생각했는데 그럴 필요가 전혀 없었다.

A – 재활용

Simple DP. 시작 위치와 끝 위치를 고정했을 때 쓰레기통을 하나 놓아서 거리가 최소화 되게 하는 지점을 O(N^2)로 전처리 한 뒤 이 배열을 사용해 O(N^2) DP를 돌리면 된다. 예선 2차 1번에서 N = 5000 제한 조건으로 같은 O(N^2)라도 커팅을 해야만 통과가 되도록 시간제한을 약간 빡빡하게 줬었던 기억이 나서 최대한 불필요한 테이블 계산을 줄이려고 노력했다. long long을 쓰지 않아 한 번 WA를 받았다.

B – 랩뮤직

B에서 삽질을 좀 오래 한 편이다. 전날 했던 벼락치기의 부작용 때문에 생각이 어려운 방향으로 흘러가서 Suffix Array도 짜고 LCP도 구하다가 깨달음을 얻고 BFS + KMP로 빠르게 풀었다. 반복문을 N까지 돌아야 되는데 N-1까지 돌아서 틀리는 등의 실수도 좀 해서 시간이 상당히 걸렸다.

C – 폭격

B를 풀고 시간이 두 시간 약간 넘게 남았다. C랑 D를 읽어봤는데 D는 생각도 어렵고 코드 짜는 게 너무 오래 걸릴 것이라 판단돼서 C를 잡았다. KOI 기출인 두부 모판 자르기랑 비슷한 문제인데 비트 DP가 아니라 3진수 DP를 해야 하고, 리넘버링도 해야 하고, 그냥 돌리면 느려서 큐를 사용해 최적화를 하면 풀리는 문제다. 해야 할 것들은 명확하지만 그걸 짜기가 어려운 유형의 문제. 어떤 y가 입력됐을 때 y-1, y, y+1 셋을 모두 추가하면 리넘버링 후에도 단순 격자 위에 있다고 생각할 수 있다는 걸 관찰해 코드의 복잡도를 줄일 수 있었다.

사소한 오타 등의 실수는 있었지만 전체 코드 설계는 처음부터 부드럽게 진행된 문제였다. 이건 벼락치기의 도움을 받았다고 생각하는데, 내가 공부해간 알고리즘들을 직접적으로 쓰는 문제는 없었지만 잘 짠 예제 코드들을 보다가 가서 설계를 잘 한 게 아닐까 생각하고 있다.

풀고 나니까 시간이 20분 정도 남았는데, D 부분점수를 노리기에도 시간이 빠듯해 그냥 C 푸는 사람이 적기를 기원하며 새로고침 누르면서 시간을 때웠다. 내가 C를 6번째로 풀었는데, 마지막에 C를 푼 사람이 7명밖에 되지 않아 안심하며 3등상을 예상하고 있었다.

뒷풀이

대회 끝나고 나서는 미니 토크 하고, 경품 추첨 하고, 설문조사 등을 하다가 시상식을 했다. 미니 토크에서는 시간제한이 적다고 말이 많았던 2차 3번에 대해 교수님이 풀이해 주셨는데, 말이 많았던 이유가 같은 O(N lg N) 풀이임에도 불구하고 통과가 되는 풀이가 있고 아닌 풀이가 있었기 때문이지만 “호호 여러분들 엔제곱 풀이를 생각하셨나 봐요” 같은 투로 말씀하셔서 여기서도 대회측이 참가자들의 여론을 잘 파악하지 못하고 있다는 것을 느꼈다. 설문조사에 이런 부분을 담으려고 노력했지만 잘 전달되었는지는 모르겠다.

경품 추첨에서는 운 좋게 기어 360을 받았다. 시계나 태블릿을 원했다. 참가만 해도 기계식 키보드를 주는데다가 상금도 많고 이벤트로 뿌린 경품도 많았다. 역시 삼성은 돈이 많다. 시상식에서는 대회 때 예상한대로 4~8위에게 주는 3등상을 받았다. 대회 나가기 전 예상으로 실수를 좀 하면 5등상(~38위), 평타 치면 4등상(~18위) 정도 받겠다고 생각했는데 예상보다 좋은 성적을 거두어 기분이 좋았다. 상 등급이 하나씩 오를 때마다 상금이 최소 두 배로 뛴다. 1등상은 요새 핫하신 dotorya님이 2천만원 받아가셨다.

사진 찍고 수상자 인터뷰 하고 짐 찾아서 아는 사람들이랑 고기 먹고 끝났다. 내일은 전대프연이 있는데 아마 이 사람들 대부분이 다시 나타날 것이다.