아인스트라세의 SW 블로그

2020년 구글 코드잼 라운드 1C 후기

작년에 이어서 올해에도 구글 코드잼에 참가했는데, 작년에는 2라운드 진출까지만 하고, 2라운드에서는 그냥 던져버렸었다. 올해에는 좀 더 나아진 모습을 보여주고자 했는데 결국 라운드 1C까지 왔다.

구글 코드잼은 Qualification Round이후 Round 1로 넘어가는데, 1라운드의 경우 A,B,C로 총 3번의 기회가 있다. 각각의 라운드에서 1500등 안에 들면 다음 라운드인 Round 2로 진출하게 되고, A라운드에서 1500등 안에 들어서 다음 라운드로 진출하게 되면 다음 B, C라운드는 참여할 수 없다.

즉 각각 A,B,C 라운드 별 1500명이 다음 라운드로 진출하게 되어 결과적으로는 4500명이 Round 2로 진출하게 된다. 그런데 올해 구글 코드잼의 등록자는 역대급이라고 하며(근데 매년 등록자의 수가 늘어난다고는 한다) 라운드 1A, 1B에서 처참하게 발려버려서 자신감이 꽤나 떨어져있는 상태였다.

대충 처참한 나의 이전 라운드 성적이다.

하지만 이번 라운드에선 아슬아슬하긴 하지만 어째 저째 다음 라운드로 진출하게 될 것 같다.

In review 상태인데, 뭐 부정행위를 한 것도 아니고 1389등을 했으니 Round 2를 체험해볼 수 는 있을 것 같다. 다만 좀 걱정이 되는 것은 Round 2가 DEFCON CTF Qualification Round와 일정이 겹친다는 것... 뭐 코로나 때문에 일정이 더 밀릴수도 있긴 하겠지만 애매한 것은 사실이긴 하다.

어쨋든 기적적으로 라운드 2로 진출하게 되었으니 당분간은, 어차피 이 글을 쓰는 시기로 부터는 열흘밖에 시간이 없긴 하지만 PS 공부를 좀 더 해봐야 겠다.

1. Overexcited Fan

1번 문제인데, 생각보다 너무 쉽게 나왔어서 오히려 걱정이 되었다. 빨리 풀기 대결이 되지 않을까 하는 그러한 우려이다. 어차피 상대평가라 난이도가 너무 쉬우면 오히려 불리하게 작용할 때도 있었다.

움직이는 녀석을 가장 빨리 만날 수 있는 시간대를 찾는 문제인데, 이동 거리를 L1 Distance(맨하탄 거리)로 바로 알아낼 수 있고, 이동하거나 멈추거나 둘 다 가능하므로, 이동경로별로 원점에서의 맨하탄 거리보다 현재 시간이 더 긴 순간이 만나는 순간이 되겠다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'

const int dx[] = { +1, -1, 0, 0 };
const int dy[] = { 0, 0, +1, -1 };
int val(char c) {
	if (c == 'S') return 3;
	if (c == 'N') return 2;
	if (c == 'W') return 1;
	return 0;
}
void solve() {
	int x, y;
	string steps;
	cin >> x >> y;
	cin >> steps;
	int ans = -1;
	for (size_t i = 0; i < steps.size(); i++) {
		int k = val(steps[i]);
		x += dx[k];
		y += dy[k];
		int dist = abs(x) + abs(y);
		if (dist <= i + 1) {
			ans = i + 1;
			break;
		}

	}
	if (ans == -1) {
		cout << "IMPOSSIBLE\n";
	}
	else {
		cout << ans << endl;
	}
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}
C++

2. Overrandomized

꽤나 신박한 내용의 문제였다. TC가 3가지로 나뉘는데, 마지막 TC의 경우 $Q=-1$로 고정이라는 것이 어떻게 보면 힌트가 좀 되었다.

문제 조건을 보면, N, R, D가 각각 chosen independently and uniformly at random from~ 과 같은 제약사항이 있다.

따라서 랜덤의 upper-bound역시 랜덤이므로, 이 값들은 순서는 중구난방이겠지만, 결국은 계단과 같은 모양으로 나타나게 될 것이다. $10^4$개의 쿼리 값들을 알려주니 대충 아래와 같은 형식으로의 값들이 나타난다고 볼 수 있겠다.

rand() % 10

rand() % 20

rand() % 30

rand() % 40

...

rand() % 100

이렇게 되면 아무래도 맨 앞자리의 수가 1로 시작하는 수의 값이 맨 앞자리의 수가 2로 시작하는 녀석보다는 많을 것이고, 2로 시작하는 녀석은 3으로 시작하는 녀석보다 많을 것이고.. 와 같은 통계적 상관관계가 나타날 것이다.

이러한 점을 이용해서 가장 앞자리에 나타나는 알파뱃의 출연 빈도를 체크해서 내림차순으로 정렬하면 이 알파뱃들이 1부터 9의 숫자를 나타낼 것이다.

또한 0의 경우는 첫번째 자리에서만 나타날 수 없는 수이므로, 전체 나타난 알파뱃 중 맨 앞자리에 나타나는 알파뱃들을 빼면 나오게 될 것이다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
#define NUMTC 10000
typedef pair<ll, string> pis;
typedef pair<ll, char> pic;
ll cnt[30];
void solve() {
	set<char> occurs;
	set<char> nonzero;
	occurs.clear();
	nonzero.clear();
	memset(cnt, 0, sizeof(cnt));
	int U;
	pis arr[NUMTC + 5];
	vector<pic> ans;
	ans.clear();
	char output[11];
	cin >> U;
	for (int i = 0; i < NUMTC; i++) {
		cin >> arr[i].first >> arr[i].second;
	}
	for (int i = 0; i < NUMTC; i++) {
		auto& s = arr[i].second;
		nonzero.insert(s[0]);
		//첫번째만 셈
		cnt[s[0] - 'A']++;
		for (char c : s) {
			occurs.insert(c);	
		}
	}
	for (int i = 0; i < 30; i++) {
		if (cnt[i]) {
			ans.push_back(make_pair(cnt[i], i + 'A'));
		}
	}
	for (auto c : nonzero) {
		occurs.erase(c);
	}
	char zero = *occurs.begin();
	sort(ans.begin(), ans.end(), greater<pic>());
	for (int i = 0; i < 9; i++) {
		output[i+1] = ans[i].second;
	}
	output[0] = zero;
	output[10] = 0;
	printf("%s\n", output);
	return;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}
C++

3. Oversized Pancake Choppers

이 문제는 고생을 꽤 했다. 마지막 문제 답게 난이도도 꽤 어려웠던 것 같은 느낌이다.

근데 사실 아이디어는 어느정도 생각을 해서 Middle TC는 맞출 수 있을 것 같았는데 한가지 조건을 빼 먹어서 업솔빙하면서도 많이 틀려먹었다.

결국 wwiiiii님의 코드를 참고한 뒤 힌트를 얻었다.

analysis를 보고 미들 TC를 맞추는 풀이까지만 적용해서 풀어보았다.

조각의 크기를 $Ai$중 하나로만 가능하다고 생각한 고정관념에 따라 틀려버렸는데, 조각의 크기는 $Ai / k$가 가능하고, 이때 $k$는 1과 $D$사이의 수가 된다.

analysis에서 Time Complexity가 $O(D*N^2)$라고 했을때, D가 왜 들어가나 이해를 못했는데 이것 때문이었다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 305
ll A[MAXN];
void solve() {
	ll N, D;
	cin >> N >> D;
	ll ans = D - 1;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A, A + N);
	// K를 perfect-cut 개수라고 하면 D - K가 정답이 된다.
	for (int i = 0; i < N; i++) {
		for (ll k = 1; k <= D; k++) {
			ll unit = A[i];// 조각의 크기는 unit / k이다.
			ll pieces = 0; //조각의 개수
			for (int j = 0; j < N; j++) {
				ll chunk = A[j];
				pieces += chunk * k / unit;
			}
			if (pieces < D) continue; //다 잘라도 이 조각 개수가 안나오는 경우 skip
			pieces = 0;
			int K = 0; // 모두 다 떨어지는 조각 개수
			for (int j = 0; j < N; j++) {
				ll chunk = A[j];
				ll add = chunk * k / unit;
				if ((chunk * k) % unit == 0 && pieces + add <= D) {
					pieces += add;
					K++;
				}
			}
			ans = min(ans, D - K);
		}
	}
	cout << ans << endl;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}
C++

TC 3에 대한 솔루션 코드 업솔빙은 나중에 시간나면 해보도록 하겠다..... 나중에 스코어 보드를 보니, 한국인 참가자 중에서는 TC3를 맞춘 사람이 1명도 없었다. 코드를 보니 아이디어는 대충 비슷하게 구현은 한 것 같은데 다들 TLE가 나서 그런듯 하다.

TC3에 대한 심플한 솔루션 코드를 odh님이 작성하셨다. 참고해보면 좋을듯.

https://www.acmicpc.net/problem/1620

Rust언어를 공부하면서 책을 보고 예제를 보고는 있는데 그래도 코드를 좀 짜봐야지 익숙해질 것 같은 느낌이 든다. 그래서 백준 문제중에서 만만한 것들을 Rust로 좀 풀어보기로 하였다.

일단 만만한 문제의 기준은 https://solved.ac/class/에 있는 녀석 중 내가 아직 안 푼 문제들이다. 

일단근데 Rust는 Input 받는것 부터 잘 몰라서, 다음 깃허브에 있는 녀석들을 한번 참고하면 좋을 듯 하다.

https://github.com/EbTech/rust-algorithms

깃허브 자체가 Rust로 Contest나가는거니... scanner도 보인다.

문제 자체는 간단하다, String 배열로 받아서 저장해놓고 그때그때 맞는 녀석 출력하면 될 듯 하다. 한번 Rust로 짜보자..!

#![allow(unused_imports)]
#![allow(dead_code)]
use std::cmp::*;
use std::collections::*;
 
struct Scanner {
   buffer : std::collections::VecDeque<String>
}
 
impl Scanner {
 
   fn new() -> Scanner {
      Scanner {
         buffer: std::collections::VecDeque::new()
      }
   }
 
   fn next<T : std::str::FromStr >(&mut self) -> T {
 
      if self.buffer.len() == 0 {
         let mut input = String::new();
         std::io::stdin().read_line(&mut input).ok();
         for word in input.split_whitespace() {
            self.buffer.push_back(word.to_string())
         }
      }
 
      let front = self.buffer.pop_front().unwrap();
      front.parse::<T>().ok().unwrap()
   }

   fn next_str(&mut self) -> String {
    if self.buffer.len() == 0 {
       let mut input = String::new();
       std::io::stdin().read_line(&mut input).ok();
       for word in input.split_whitespace() {
          self.buffer.push_back(word.to_string())
       }
    }
    self.buffer.pop_front().unwrap()
    
 }
}
fn main() {
    let mut cin = Scanner::new();
    let n:usize = cin.next();
    let m:usize = cin.next();
    let mut arr = vec![]; // index to string
    let mut hash = HashMap::new(); // string to index
    
    for i in 0..n {
        let name = cin.next_str();
        arr.insert(i, name.clone());
        hash.insert(name.clone(), i);
    }
    for _ in 0..m {
        let query = cin.next_str();
        if query.parse::<i32>().is_ok() {
            let index: usize = query.parse::<usize>().unwrap();
            println!("{}", arr[index-1]);
        } else {
            match hash.get(&query) {
                Some(index) => println!("{}", index+1),
                None => println!("Error case!")
            }
        }
    }

}
Rust

어째 저째 대충 짜본 코드이다. 

스캐너로 input 받는것은 아래 레퍼런스를 참고했다.

http://codeforces.com/contest/702/submission/19589375

정답은 나올거같은데, TLE가 난다. 왜그런진 모르겟음

그래서 답답한 마음에 C++로 후다닥 다시 짜서 보았다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define MAXN 100005
string arr[MAXN];
map<string, int> mm;
int main() {
    int n, m;
    cin >> n >> m;
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    for(int i=1 ;i <= n; i++) {
        string s;
        cin >> s;
        arr[i] = s;
        mm[s] = i;
    }
    for (int i=0; i < m; i++) {
        string v;
        cin >> v;
        if (v[0] >= 'A') {
            cout << mm[v] << endl;
        } else {
            int idx = atoi(v.c_str());
            cout << arr[idx] << endl;
        }
    }
}
C++

하 C++로 하면 이렇게 간단하게 코드를 짤 수 있는데... 근데 보니깐 sync_with_stdio(false)를 넣지 않으면 TLE가 나는걸로 봐서는 아마 러스트 코드에서 TLE가 나는것은 Scanner가 느리거나, 인풋 받는데 vector를 선언해서 받고 하는데 이런게 느려서 그런거지 않을까 싶다.

고로... PS는 C++이 참 편하긴 한듯.

사이트에 들어가보면 다음과 같이 나타난다.

소스코드 보는 부분이 있으니 소스코드를 한번 보자.

보면 select 쿼리에서 agent로 검색을 하는데, HTTP_USER_AGENT 값을 이용해서 SQL 쿼리를 짠다.

UserAgent 값을 이용해서 SQLi를 하면 될 것 같다.

user agent에 대충 위와 같은 값을 넣어주면, 쿼리는 아래와 같이 나타날 것이다.

insert into chall8(agent,ip,id) values('einstrasse','dummyip','admin'),('asdf','{$ip}','guest')

그러면 2개의 값이 추가가 되게 된다.

2개가 동시에 추가가 된 듯 하다.

그리고 아까 추가한 user-agent값인 einstrasse라고 user-agent를 보내보자.

오른쪽을 보면 already solved라고 뜬다.

clear!

올해 킥스타트 B라운드는 주말 아침8시에 시작을 해서, 어째저째 술먹고 새벽에 퍼질러 자다가 비몽사몽한상태에서 용캐 일어나서 한번 풀어보았다.

코드잼 1Round에서 엄청 발렸던 기분을 Kickstart를 풀면서 조금 달래주려 했는데, 확실히 Kickstart는 Codejam에 비해서는 난이도가 낮은 듯 한 느낌을 많이 받았다.

총 4문제가 나왔고, 예전에는 Large set은 Full feedback을 안주고 Hidden verdict형식이었는데, 이번에는 다 Visible verdict로 진행이 되었다.

Bike Tour

봉우리 갯수를 새는 문제이다. for loop로 순회하면서 좌우 값을 봐서 그 보다크면 봉우리로 갯수를 카운트 하면 되는 간단한 문제이다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'

int arr[105];
void solve() {
	int n;
	int ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	for (int i = 1; i < n - 1; i++) {
		if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) ans++;
	}
	cout << ans << endl;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}
C++

Bus Routes

버스가 오는 시간 주기를 알때, 마지막 버스를 탈 수 있는 가장 늦은 시간을 구하는 문제이다. 배수개념으로 접근하면 될 것 같은데, 파라메트릭 서치를 이용하면 간단하게 풀 수 있다. 쿼리를 바이너리 서치로 확인하는건데, 쿼리 확인시에는 floor(v/x) * x를 해서 가장 가까운 배수를 찾아내면 된다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'

ll a[1005];
int n;
ll d;
bool q(ll v) {
	
	for (int i = 0; i < n; i++) {
		ll x = a[i];
		v = max(v, (v + x - 1) / x * x);
		if (v > d)
			return false;
	}
	return true;
}
void solve() {
	ll l, r;
	l = 1;
	//r = (ll)1e12;
	cin >> n >> d;
	r = d;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	while (l < r) {
		ll m = (l + r + 1) / 2;
		//printf("%lld %lld %lld\n", l, r, m);
		if (q(m)) {
			l = m;
		}
		else {
			r = m - 1;
		}
	}
	cout << l << endl;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}
C++

Robot Path Decoding

문제 내용 자체보다는, Operation code 파싱이 더 어렵다. (를 만나면 같은 depth의 )의 인댁스를 찾아서 재귀로 짜보려다가 $O(N^2)$인데 TLE안나려나 궁금했다가 그냥 스택으로 짜는게 더 나을거 같아서 머리를 쥐어 짜면서 스택으로 파서를 만들어 보았다. 생각보다 파서가 간단하게 만들어 졌던 것 같다. 좌표계가 wrap-around되므로 그 부분을 처리해주는 함수를 따로 만들어서 썼다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
const ll MOD = 1e9;
ll nor(ll v) {
	if (v < 0)
		v += MOD;
	if (v >= MOD)
		v %= MOD;
	return v;
}
struct Data {
	int op;
	ll x, y;
	void add(struct Data& rhs) {
		x += rhs.x;
		y += rhs.y;
		x = nor(x);
		y = nor(y);
	}
	void mult(int v) {
		x *= v;
		y *= v;
		x = nor(x);
		y = nor(y);
	}
};
Data calc(char c) {
	if (c == 'N') {
		return { 0, -1, 0 };
		//return make_pair(-1, 0);
	}
	else if (c == 'S') {
		return { 0, 1, 0 };
		//return make_pair(+1, 0);
	}
	else if (c == 'W') {
		return { 0, 0, -1 };
		//return make_pair(0, -1);
	}
	else if (c == 'E') {
		return { 0, 0, 1 };
		//return make_pair(0, +1);
	}
	else {
		assert(false);
	}
}

void solve() {
	string s;
	cin >> s;
	//ll x, y;
	//x = y = 0;
	stack<Data> ss;
	ss.push({ 0, 0, 0 });
	for (int i = 0; i < s.length(); i++) {
		char c = s[i];
		if (c >= '0' && c <= '9') {
			ss.push({ c - '0', 0, 0 });
			ss.push({ 0, 0, 0 });
		}
		else if (c == ')') {
			Data operand = ss.top(); ss.pop();
			Data mult = ss.top(); ss.pop();
			Data prev = ss.top(); ss.pop();
			operand.mult(mult.op);
			prev.add(operand);
			ss.push(prev);
		}
		else if (c >= 'A' && c <= 'Z') {
			Data cur = ss.top(); ss.pop();
			Data delta = calc(c);
			cur.add(delta);
			ss.push(cur);
		}
	}
	ll y = (ss.top().y + 1);
	ll x = (ss.top().x + 1);
	cout << y << ' ' << x << endl;
	while (ss.size()) ss.pop();
	//x++; y++;
	//cout << y << ' ' << x << endl;

}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}
C++

Wandering Robot

kickstart때는 못풀어서 나중에 Analysis랑 남의 코드들을 보고 업솔빙을 좀 했다. 아이디어 자체는 대충 냈었는데, 어차피 디테일부분을 못따라가서 구현법 팁을 알았어도 당시에는 못 풀었을 듯 하다.

1등한 사람의 코드도 좀 참고를 하고 이해안가는 부분을 동기형한테는 물어보고 해서 도움을 꽤 받았다.(사실 아직도 100%는 이해 안 된 것 같기도하고...)

이항계수를 구하는 부분에서 Precision Error가 많이 날 것 같았는데 결국 요구하는 정확도가 $10^{-5}$정도로 낮은 수준이기도 하고, log로 축소시켜서 계산한 뒤 다시 역로그(exp함수)로 되돌려서 계산하는 부분들이 신박했다.

근데 여기서 좀 쟁점이 되는 부분은 대각선이 딱 맞아떨어지지 않는 경우가 쟁점인데, 아래 그림을 보자.

참고로 아래 문단에서 구한다고 하는 것은 시작점을 $(0,0)$라고 가정하고 도착지점 좌표를 $(x,y)$라고 가정하면

$\frac{1}{2}^{x+y}*\binom{x+y}{x}$를 의미한다. 이를 $f(x,y)$라고 하자.

파란색들은 독립적으로 되기 때문에 각자 구해서 더하면 되는데, 파란색 위쪽에 비어있는 칸으로 가는 경우는 쟁점이 된다.

오른쪽 끝에 다다른 경우 무조건 아래로만 가기 때문에 해당 부분에 대한 내용들도 더해줘야 하는데, 이는 빨간색 박스에 도달하는 경우(실제로는 벽을 뚫을 순 없지만 뚫을 수 있다고 가정할 시)를 더해주면 된다. 어차피 벽을 뚫는경우 아래로 내려가는걸로 취급하면 되므로 그러하다.

근데 1등 코드를 확인해보면 노란색으로 가는 확률(f(노랑칸))에 1/2를 곱해서 더해버리는 식이다. 사실 노랑색 바로 아래 파란색(C) 입장에서는 바로 위 노란색(B)에서 아래로 1/2확률로 내려오는 것만 포함되어 있는데, 바로 위 노란색(B)에서 오른쪽으로 가는 경우의 확률도 더해져야 하므로 노란색으로 도달하는 확률에 1/2를 곱해서 더한다.

그리고 마찬가지로 가장 아래 노란색(B)으로 가는 확률은 바로 위 노란색(A)에서 1/2확률로 내려온경우는 포함되지만, 맨 위 노란색에서 오른쪽으로 가서 내려오는 경우확률이 빠져있으므로 이도 더해주는 식이라고 한다.(thanks for jrj) 각 부분의 정의를 명확하게 해줘야지 안햇갈린다고 한다.

설명하면서도 내가 약간 햇갈려서 첨언을 하자면, 대각선으로 구역을 나누는 경우 서로 겹치는 경우가 없으므로(독립이므로) 확률을 구해서 더해버리면 되는데, 노란색(B)의 경우와 아래 파란색(C)의 경우는 겹치는 경우가 있다. 그러므로 겹치지 않는 경우 중에 세어지지 않은 부분만 추가적으로 더해주는 것이다. 노란색(A, B)의 경우에서는 오른쪽으로 갈 확률이 0%이므로 이 부분만 따로 추가로 더해주는 것이고, 아래로 가는 확률이 100%, 오른쪽이 0%인데 이것이 50% 50%으로 더해져 있으므로, 부족한 아래로 가는 50%를 더해주는 것이다.

내가 착각을 했던 것이, A,B의 경우가 무조건 C까지 가야만 한다고 생각을 했는데, 어차피 C에는 A,B 경우의 수 중 절반은 더해져 있는 상황이고, 이 남은 절반만 더해주면 된다는 것이다. 이 남은 절반의 확률은 맨 오른쪽에서는 아래로만 내려가는 선택지만 생긴다는 특수한 상황때문에 생기는 것이기도 하다.

그리고 역으로 전체에서 중간 구멍으로 빠질 확률을 빼줘도 되는데, f(초록칸)을 죄다 구한 뒤 1/2를 곱해서 더하면 된다고 한다. 그리고 1에서 그 값을 빼줘도 될 것 같은데 아직 구현은 안해봤다.

아래 코드는 빨간칸을 구해서 다 더하는 방식의 코드이다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 200005
double lnfact[MAXN];
double bicof(int a, int b) {
	return lnfact[a] - lnfact[a - b] - lnfact[b];
}
void solve() {
	int W, H, L, U, R, D;
	cin >> W >> H >> L >> U >> R >> D;

	int dist = L + D - 2;
	double ans = 0;
	if (D < H) {
		for (int i = 1; L - i > 0; i++) {
			int x = L - i;
			int y = D + i;
			double logval = bicof(dist, x - 1);
			logval -= dist;
			ans += pow(2, logval);
		}
	}
	dist = R + U - 2;
	if (R < W) {
		for (int i = 1; U - i > 0; i++) {
			int x = R + i;
			int y = U - i;
			double logval = bicof(dist, x - 1);
			logval -= dist;
			ans += pow(2, logval);
		}
	}
	cout << fixed << setprecision(8);
	cout << ans << endl;
}
int main() {
	for (int i = 2; i < MAXN; i++) {
		lnfact[i] = lnfact[i - 1] + log(i) / log(2);
	}
	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		cout << "Case #" << t << ": ";
		solve();
	}
}
C++

2020년 구글 코드잼 Qualification 라운드 후기 글이다.

이번에는 총 5문제가 나왔고, TC set이 1개짜리부터 3개짜리까지 다양하게 있었다.

결과만 말하자면 4번째 문제 Hidden set과 5번째 문제 Hidden set 빼고는 다 풀었다.

등수는 4769등인데, 이 추세로는 Round 2도 못갈듯하다. 올해 참가자가 역대 최대라는 이야기가 있던데, 올해 목표인 코드잼 티셔츠 받기는 힘들것 같기도 하다 ㅠㅠ

4번문제 Hidden Set은 Solution은 이미 생각해서 짰는데, 버그 하나때문에 날려먹은 케이스이다.

끝나고 나서 다시 디버그 해서 풀어보니 잘 맞았었는데  애석한 상황이다.

끝나고 나서 맞은 상황이다. Interactive Problem이라서 디버깅 환경 구축하는 것도 꽤 귀찮고 했었다.

일단 푼 문제들 간단하게 리뷰를 해보자.

1. Vestigium (7pt)

첫번째 문제 답게 매우 쉬웠던걸로 기억한다. Latin square matrix라고 각 오와 열에 1부터 N까지의 수가 1번씩만 나타나는 녀석에서 왼쪽위부터 오른쪽아래로 되는 대각선의 값들의 합이 trace라고 하는데 임의의 matrix가 주어질 때, 이 trace를 구하고, Latin square rule을 위반하는 row와 column의 수를 출력하면 되는 그런문제이다.

하나하나 다 따라가면서 체크하면 답이 나온다. 문제 이해하는데 시간을 더 쓴 것 같다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
void solve() {
	int trace = 0, duprow = 0, dupcol = 0;
	int matrix[105][105];
	int n;
	cin >> n;
	int check[105];
	for (int i = 0; i < n; i++) {
		memset(check, 0, sizeof(check));
		for (int j = 0; j < n; j++) {
			int v; 
			cin >> v;
			matrix[i][j] = v;
			check[v]++;
			if (i == j) trace += v;
		}
		int correct = 0;
		for (int i = 1; i <= n; i++) {
			if (check[i] == 1) correct++;
		}
		if (correct != n) {
			duprow++;
		}
	}
	for (int i = 0; i < n; i++) {
		memset(check, 0, sizeof(check));
		for (int j = 0; j < n; j++) {
			int& v = matrix[j][i];
			check[v]++;
		}
		int correct = 0;
		for (int i = 1; i <= n; i++) {
			if (check[i] == 1) correct++;
		}
		if (correct != n) {
			dupcol++;
		}
	}
	cout << trace << ' ' << duprow << ' ' << dupcol << endl;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}
C++

2. Nesting Depth (5pts, 11pts)

문자열 다루는 문제 같은 문제인데, 숫자가 나오면, 각각의 숫자는 자신을 둘러싼 괄호가 자신의 숫자만큼 나와야 한다. Greedy하게 이전 숫자보다 큰 숫자가 나오면 여는 괄호를 더 열어주고, 더 작은 숫자가 나오면 닫아주고, 마지막에 다 닫아주면 된다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
void solve() {
	string s;
	string ans = "";
	cin >> s;
	//int opened = 0;
	int prev = 0;
	for (char c : s) {
		int cur = c - '0';
		if (cur > prev) {
			int diff = cur - prev;
			//diff만큼 더 연다
			for (int i = 0; i < diff; i++) {
				ans += "(";
			}
		}
		else if (cur < prev) {
			int diff = prev - cur;
			for (int i = 0; i < diff; i++) {
				ans += ")";
			}
		}
		prev = cur;
		ans += c;
	}
	if (prev > 0) {
		while (prev--) {
			ans += ")";
		}
	}
	cout << ans << endl;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}
C++

3. Parenting Partnering Returns(7pts, 12pts)

부모 두명이서 아기 돌보는 스케쥴?을 각자 스케쥴링 하는데, 가능하게 스케쥴링 하면 되는 문제이다. 각각 task가 시작하는 시간 기준으로 정렬을 한 뒤, 그리디하게 지금 일 가능한 녀석들을 스케쥴링 해주면 된다.

소팅하기 전에 원래 Index 기준으로 답을 입력해야 하는 것을 깜빡해서 한번 WA를 받았다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
string mark[2] = { "C", "J" };
void solve() {
	int fins[2];
	fins[0] = fins[1] = 0;
	int resp[1005];
	memset(resp, -1, sizeof(resp));
	int n;
	vector<pair<pii, int>> tasks;
	tasks.clear();
	cin >> n;
	for (int i = 0; i < n; i++) {
		int s, e;
		cin >> s >> e;
		tasks.push_back(make_pair(make_pair(s, e), i));
	}
	sort(tasks.begin(), tasks.end());
	for (auto task : tasks) {
		bool alloced = false;
		for (int candid = 0; candid < 2; candid++) {
			if (fins[candid] <= task.first.first) {
				fins[candid] = task.first.second;
				//ans += mark[candid];
				resp[task.second] = candid;
				alloced = true;
				break;
			}
		}
		if (alloced == false) {
			cout << "IMPOSSIBLE" << endl;
			return;
		}
	}
	string ans = "";
	for (int i = 0; i < n; i++) {
		ans += mark[resp[i]];
	}
	cout << ans << endl;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}
C++

4. ESAb ATAd(1pt, 9pts, 16pts)

interactive 문제이다. 오랜만에 interactive 문제를 봐서 환경 구축도 귀찮았다. 일단 interactive_runner.py랑 judge.py를 코드잼측에서 제공을 해준다.

두 녀석들 다 받은 뒤, 내가 짠 코드 바이너리가 ps.exe라고 할때 다음과 같이 명령어를 수행하면 test가 가능하다.

$ python3 interactive_runner.py python3 judge.py 0 -- ps.exe
C++

interactive_runner.py는 -- 기준으로 왼쪽에 있는 command와 오른쪽에 있는 command를 각각 쓰레드로 실행시킨 뒤, stdin/stdout를 각각 연결해주는 역할을 한다.

python3 judge.py 0라고 실행하면 서버가 어떻게 응답하는지를 확인해볼 수 있다. 0을 인자로 넣으면 1번째 test set(b=10)이 나오고, 1를 인자로 넣으면 2번째 test set(b=20)이 적용된다.

맨처음에 문제 내용을 이해하는데에도 꽤나 오래걸렸었다. 문제를 잘 이해못하고 테스팅 툴을 이해못해서, 파이썬 코드를 뜯어서 분석해 보기도 했었다.

문제 내용을 대충 설명해보자면, B bit의 임의의 수를 서버에서 지정한다. 이 값을 우리가 맞추면 되는데, 최대 150번의 쿼리가 가능하다. 각 쿼리를 하기 위해서 1~B에 해당하는 정수 하나를 보내면 그 쿼리 번째 bit값을 리턴해준다. 근데 10번 요청을 할 때 마다 서버에 저장된 B bit가 랜덤한 확률로 값이 바뀌게 된다. 50%확률로 Negation 연산이 일어나고(1이 0이 되고, 0이 1이 된다), 50%확률로 Reverse 연산이 일어나서 1번 비트가 B번 비트로, 2번 비트가 B-1번 비트가 되고 이런식으로 바뀌게 된다.

따라서 25%확률로 Negation만 일어나고 25%확률로 Reverse만 일어나고 25%확률로 Negation과 Reverse가 동시에 일어나고, 25%확률로 아무일도 안일어난다.

서버에 저장된 bit를 맞추는 것은 Negation, Reverse가 일어난것을 다 쳐서, 답을 맞추는 시점에 맞는 bit이기만 하면 정답처리가 된다. 그리고 정답을 제출하는 것은 Query로 안친다고 한다.

1번째 test set는 각 비트별로 값을 한번씩 다 물어본 뒤 이어서 응답을 주면 풀린다. 10번 쿼리를 했지만, 답변하는 것은 쿼리가 아니므로 비트 변조가 안일어난 상태이다.

2번째만을 위한 답 코드 말고 3번째에도 해당되는 솔루션을 생각했는데 대략 다음과 같다.

일단 bit값들을 앞에서부터 5개, 뒤에서부터 5개씩 해서 10개씩 받는다. 그러면 그 10개의 뭉치는 바뀌어도 같은 시점에 바뀌기 때문에 초기 값은 같은그룹들을 모을 수 있다.

첫번째 그룹은 [1~5]비트와 [96~100] 비트가 된다. 두번째 그룹은 [6~10]비트와 [91~95]비트가 된다.

같은 그룹끼리는 Reverse가 되어도 같은 그룹끼리 바뀌게 되므로 같이 움직인다고 볼 수 있다.

그러면 여기서 1번 비트와 해당하는 100번 비트가 둘다 같은 숫자이면 Reverse되어도 그대로이다. 그리고 1번 비트와 100번 비트가 서로 다른 숫자라면 Negation되어도 Reverse되는 것과 같은 효과가 난다.

이러한 점을 이용해서 같은 그룹내에 대칭인 bit와 아닌 bit가 둘 다 있다면, 이 2개의 비트를 확인해서 Negation이 되었는지 Reverse가 되었는지를 확인할 수 있다.

그리고 만약 한 그룹이 모두 대칭인 수로만 이루어져 있거나, 모두 비대칭인 수로만 이루어져 있다면 더욱 쉽다. 대칭인 수로만 이루어져 있으면 Neg만 확인하면 되고, 비대칭인 수로만 이루어져 있으면 Rev랑 Neg랑 동일하게 칠 수 있다.

이를 이용해서 그룹의 수를 모두 알아내고(100번의 쿼리로), 각각 그룹 별 Neg랑 Rev가 일어났는지를 체크를 한다. 각각 그룹당 2번 이하의 쿼리로 일어났는지를 확인할 수 있으므로 10번의 쿼리마다 5개의 그룹을 확인할 수 있다. 그리고 10번의 쿼리가 일어난 뒤는 Bit fliping이 어떻게 일어났는지 알기 위해서 기준이 되는 그룹을 하나 두고(이 그룹은 비대칭과 대칭이 둘다 있어야지 Rev와 Neg를 둘다 확인가능) 그녀석으로 체크를 한다.

그래서 10번의 쿼리마다 최소 4개의 그룹의 상태를 확인가능하다.

그러면 130번 쿼리 내에 모든 그룹의 상태를 확인할 수 있다.

디버깅 할때에는 query 함수를 디버깅용 서버 상태를 알려주는 녀석으로 만들어서 했다.

모두 대칭이거나 비대칭인 경우의 체크를 조금 잘못해서 3번째 set에서 틀리긴 했었는데 고쳐서 이제는 모두 정답이 나온다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define TOTAL_BIT_NUM 105
#define GROUP_NUM 12
int tc, n;
int bits[TOTAL_BIT_NUM];
int mirror[TOTAL_BIT_NUM];
int mirror_cnt[GROUP_NUM];
int neged[GROUP_NUM];
int reved[GROUP_NUM];
int g_neged, g_reved;
void solve10() {
	for (int t = 1; t <= tc; t++) {
		string ans = "";
		for (int i = 1; i <= n; i++) {
			cout << i << endl;
			cout.flush();
			string s;
			cin >> s;
			ans += s[0];
		}
		cout << ans << endl;
		cout.flush();
		string res;
		cin >> res;
		if (res[0] == 'N') exit(1);
	}
}
pii get_canary(int gnum) {
	int neg_canary, rev_canary;
	neg_canary = rev_canary = -1;
	for (int i = gnum * 5; i < gnum * 5 + 5; i++) {
		if (mirror[i] && neg_canary == -1) {
			neg_canary = i; //rev 되도 변하지 않음
		}
		if (!mirror[i] && rev_canary == -1) {
			rev_canary = i; //rev 되면 변함
		}
	}
	return make_pair(neg_canary + 1, rev_canary + 1);
}
//debug
/*
int samples[] = {0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1 };
int query(int pos) {
static int count = 0;
int ret = samples[pos - 1];

count++;
if (count == 10) {
cout << "---------------------------------------" << endl;
count = 0;
if (rand() % 2 == 0) {
cout << "Negation !!!" << endl;
for (int i = 0; i < 100; i++) {
samples[i] ^= 1;
}
}
if (rand() % 2 == 0) {
cout << "Reversed !!!" << endl;
for (int i = 0; i < 50; i++) {
swap(samples[i], samples[99 - i]);
}
}
cout << "---------------------------------------" << endl;
}
return ret;
}
*/

int query(int pos) {
	cout << pos << endl;
	cout.flush();
	int ret;
	cin >> ret;
	return ret;
}


void solve_large() {
	while (tc--) {
		//입력받기
		memset(bits, -1, sizeof(bits));
		memset(mirror, 0, sizeof(mirror));
		memset(mirror_cnt, 0, sizeof(mirror_cnt));
		memset(neged, -1, sizeof(neged));
		memset(reved, -1, sizeof(reved));
		g_neged = g_reved = 0;
		for (int i = 0; i < n / 10; i++) {
			// [i*5+1, i*5+5]이랑 [n-5*i-4, n-5*i]
			//10개씩 뭉텅이로 받되, 앞에서부터 5개, 뒤에서부터 5개가 하나의 셋트이다.
			//앞에서부터 5개
			for (int j = i * 5; j < i * 5 + 5; j++) {
				bits[j] = query(j + 1);
			}
			//뒤에서부터 5개
			for (int j = n - 5 * i - 5; j < n - 5 * i; j++) {
				bits[j] = query(j + 1);
			}
		}
		//base group를 찾는다.
		//base는 palindrome한 쌍과 palindrome 아닌 것 값 하나를 알아내면 된다.
		//팰린드롬은 complement 연산을 했는지를 확인하는 용도이다.
		//palindrome아닌 것은 reverse연산을 했는지 확인하는 용도이다.
		//base 그룹은 mirror_cnt가 1~4 사이의 값이다.
		for (int i = 0; i < n / 2; i++) {
			int j = n - i - 1;
			if (bits[i] == bits[j]) {
				mirror[i] = mirror[j] = 1;
				mirror_cnt[i / 5]++; //해당 그룹에 palindrome 인 수 개수.
			}
		}
		// mirror_cnt가 5인 그룹에는 rev 연산이 무의미함
		// mirror_cnt가 0인 그룹은 rev 연산과 neg 연산이 같다.
		int base_gnum = -1;
		for (int i = 0; i < n / 10; i++) {
			if (mirror_cnt[i] > 0 && mirror_cnt[i] < 5) {
				base_gnum = i;
				break;
			}
		}
		if (base_gnum == -1) {
			//모든 그룹이 palindrome이거나 그 반대인경우
			//neg만 체크하면 된다.
			for (int i = 0; i < n / 10; i++) {
				int k = i * 5 + 1;
				int res;
				res = query(k);
				if (bits[k - 1] != res) {
					//real time negation
					//앞에서부터 5개
					for (int j = i * 5; j < i * 5 + 5; j++) {
						bits[j] ^= 1;
					}
					//뒤에서부터 5개
					for (int j = n - 5 * i - 5; j < n - 5 * i; j++) {
						bits[j] ^= 1;
					}
				}
			}
			string s = "";
			for (int i = 0; i < n; i++) {
				if (bits[i]) {
					s += "1";
				}
				else {
					s += "0";
				}
			}
			cout << s << endl;
			cout.flush();
			//get response
			string res;
			cin >> res;
			if (res[0] == 'N') exit(1);
		}
		else {
			//일반적인 섞여있는 경우
			pii base_canary = get_canary(base_gnum); // {neg, reg}
			int query_left = 8;
			if (query(base_canary.first) != bits[base_canary.first - 1]) {
				neged[base_gnum] = 1;
			}
			else {
				neged[base_gnum] = 0;
			}
			if (query(base_canary.second) != (bits[base_canary.second - 1] ^ neged[base_gnum])) {
				reved[base_gnum] = 1;
			}
			else {
				reved[base_gnum] = 0;
			}
			(void)0;
			for (int i = 0; i < n / 10; i++) {
				if (i == base_gnum) continue; //base 그룹은 미리 구해놨으므로 안구해도 된다.
				if (query_left < 2) {
					if (query_left == 1) query(1);
					query_left = 8;
					if (query(base_canary.first) != (bits[base_canary.first - 1] ^ neged[base_gnum] ^ g_neged)) {
						g_neged ^= 1;
					}
					if (query(base_canary.second) != (bits[base_canary.second - 1] ^ neged[base_gnum] ^ reved[base_gnum] ^ g_neged ^ g_reved)) {
						g_reved ^= 1;
					}
				}
				if (mirror_cnt[i] > 0 && mirror_cnt[i] < 5) {
					pii canary = get_canary(i);
					query_left -= 2;
					if (query(canary.first) != (bits[canary.first - 1] ^ g_neged)) {
						neged[i] = 1;
					}
					else {
						neged[i] = 0;
					}
					if (query(canary.second) != (bits[canary.second - 1] ^ g_neged ^ g_reved ^ neged[i])) {
						reved[i] = 1;
					}
					else {
						reved[i] = 0;
					}
				}
				else {
					query_left--;
					if (query(i * 5 + 1) != ((bits[i * 5] ^ g_neged) ^ (mirror_cnt[i] == 0 ? g_reved : 0))) {
						neged[i] = 1;
					}
					else {
						neged[i] = 0;
					}
					reved[i] = 0;
				}
			}
			//apply answers
			for (int i = 0; i < n / 10; i++) {
				int cneged = (g_neged ^ neged[i]);
				int creved = (g_reved ^ reved[i]);
				if (cneged) {
					for (int j = i * 5; j < i * 5 + 5; j++) {
						bits[j] ^= 1;
					}
					//뒤에서부터 5개
					for (int j = n - 5 * i - 5; j < n - 5 * i; j++) {
						bits[j] ^= 1;
					}
				}
				if (creved) {
					for (int j = i * 5; j < i * 5 + 5; j++) {
						int k = n - j - 1;
						swap(bits[j], bits[k]);
					}
				}
			}
			string s = "";
			for (int i = 0; i < n; i++) {
				if (bits[i]) s += "1";
				else s += "0";
			}
			cout << s << endl;
			cout.flush();
			string res;
			cin >> res;
			if (res[0] == 'N') exit(1);

		}
	}
	return;
}
int main() {
	cin >> tc >> n;
	if (n == 10) {
		solve10();
	}
	else {
		solve_large();
	}

}
C++

5. Indicium(7pts, 25pts)

마지막 문제인데, Small tc만 풀이법을 알겠고, large는 모르겠다.

원하는 Trace에 해당하는 Latin square matrix를 찾거나, 불가능하다고 말해줘야하는 그런 문제이다.

Backtracking으로 풀 수 있고, 특정 K값을 트레이스로 갖는지 알아야 한다.

만약 K가 주어지면, 1~N의 범위의 수 N개의 합으로 K를 만들 수 있는 조합들을 구해본다.

그리고 그 조합들의 수로 대각선으로 나열한 뒤, 남은 칸에다가 수를 채워서 Latin square matrix를 만들 수 있는지만 확인하면 된다.

이때 만약 수 조합이 1 2 2 3 4 라는 조합으로 12라는게 되는지 확인해야 할 때, 순서는 중요치 않다는 것을 알 수 있는데, 이때 하나의 성질을 활용하면 된다.

즉 1 2 2 3 4로 Latin square 매트릭스를 만들 수 있으면 1 3 4 2 2 로도 만들 수 있는데, Latin square matrix는 행 단위로 순서를 바꾸거나 열 단위로 서로 순서를 바꾸어도 Latin square matrix이다. 왜 그런지는 조금만 생각해보면 알 수 있다.

따라서 조합별로 가능한 라틴 스퀘어 매트릭스가 있는지를 다 체크해보면 Small tc는 맞출 수 있다.

Large tc는 이분매칭을 쓴다는 것 같은데, 나중에 다시 공부해봐야 겠다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
int n, k;
//n개의 숫자(1~n) 합으로 k를 만드는 경우의 수를 다 만들어야한다.
int val[6];
struct Chunk {
	int v[5];
};
vector<Chunk> comb[26];
void dfs(int offset) {
	if (offset <= n) {
		for (int i = val[offset - 1]; i <= n; i++) {
			val[offset] = i;
			dfs(offset + 1);
		}
	}
	else {
		Chunk chunk;
		int sum = 0;
		for (int i = 1; i <= n; i++) {
			sum += val[i];
			chunk.v[i - 1] = val[i];
		}
		comb[sum].push_back(chunk);
	}
}
int row[5], col[5];
int field[5][5];
bool backtrack(int i, int j) {
	if (i >= n) {
		//모두 성공한 경우
		cout << "POSSIBLE\n";
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cout << field[i][j] << ' ';
			}
			cout << endl;
		}
		return true;
	}
	if (j >= n) {
		//다음줄로 이동
		return backtrack(i + 1, 0);
	}
	if (field[i][j] != -1) {
		//이미 지정된 경우(diagonal)
		return backtrack(i, j + 1);
	}
	for (int v = 1; v <= n; v++) {
		if (((row[i] & (1 << v)) == 0 && (col[j] & (1 << v)) == 0)) {
			//set
			field[i][j] = v;
			row[i] |= (1 << v);
			col[j] |= (1 << v);
			//search
			if (backtrack(i, j + 1)) {
				return true;
			}
			//unset
			row[i] &= (~(1 << v));
			col[j] &= (~(1 << v));
			field[i][j] = -1;
		}
	}
	return false;
}
void solve() {
	cin >> n >> k;

	for (int i = n; i <= n * n; i++) {
		comb[i].clear();
	}
	//n에 대한 가능한 모든 숫자 조합들을 만들어냄
	dfs(1);
	for (int i = 0; i < comb[k].size(); i++) {
		memset(row, 0, sizeof(row));
		memset(col, 0, sizeof(col));
		memset(field, -1, sizeof(field));
		for (int j = 0; j < n; j++) {
			int v = comb[k][i].v[j];
			field[j][j] = v;
			row[j] |= (1 << v);
			col[j] |= (1 << v);
		}
		if (backtrack(0, 0)) return;
	}
	cout << "IMPOSSIBLE\n";
	return;
}
int main() {
	val[0] = 1;
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}
C++

느닷없이 Rust를 배우고 싶어져서 Rust 개발환경을 한번 구축해보도록 하겠습니다.

사실 지금 글을 쓰는 이 시점에는 Rust를 공식적으로 지원하는 IDE나 그런 녀석들은 잘 없는데, 그래도 제일 많이 쓰이는 조합이 Visual Studio Code + Rust plugin인 것 같다. 해당 조합은 VS코드에서 Syntax highlighting을 지원합니다.

그리고 RLS라는 Rust Language Server라는 녀석이 있는데 이 녀석은 백그라운드로 실행되면서 코드 에디터나 다른 툴에게 Rust에 대한 정보를 넘겨주는 그런 녀석입니다. syntax상 에러 같은거를 알려주고, 선언부로 이동하기 라던지 IDE에서 제공하는 기능들을 모듈화 된 프로그램이라고 보면 됩니다.

근데 아직 RLS도 Stable 버전이 나온 상태는 아니라서 다른 언어에 비해좀 느리거나 중간에 동작하지 않거나 하는 경우가 좀 있다고 합니다. 그래도 쓸만하다고 하네요.

제가 구축할 환경은 Windows 10 + Sublime Text3 + Rust plugin 이 되겠습니다.

Rustup 설치

Rustup은 rust 툴체인 인스톨러라고 합니다. Rustup을 쓰지 않더라도 러스트를 설치할 수 있지만, rustup을 이용하면 다른 컴포넌트들을 쉽게 설치할 수 있어서 추천한다고 합니다.

https://rustup.rs/

홈페이지로 가서 다운받은 뒤 설치를 완료해봅시다.

만약 WSL를 사용하시는 분이라면 아래 curl로 시작하는 명령어를 치라고 하네요. 저는 고전 방식으로 rustup-init.exe를 다운받은 뒤 설치를 진행해보도록 하겠습니다.

1번을 선택한 뒤 계속 진행해보도록 하겠습니다.

설설치가 완료된 뒤 cmd창에서 rustc라고 쳐보도록 하겠습니다.

rustc 컴파일러가 설치된 것을 확인할 수 있네요.

Sublime text3에 Rust 플러그인 설치

Rust 플러그인은 Sublime text 3이전 버전은 지원할 계획이 없다고 합니다.

서브라임 택스트에서 Ctrl + Shift + P를 누르면 명령 창이 나타나게 됩니다.

여기서 Package install을 입력한 뒤, Package Control: Install Package를 선택하고 엔터를 눌러봅시다.

그러면 패키지 목록들이 나타나는데, 그 중 Rust enhanced를 설치해보도록 하지요.

조금 기다리면 설치가 완료됩니다.

Rust 프로젝트 만들기

서브라임 텍스트는 단순 에디터이니, 터미널을 통해서 프로젝트를 생성해줍니다.

그리고 서브라임 텍스트로 프로젝트 디렉토리를 열어줍니다.

$ cargo new hello_world --bin
$ subl ./hello_world
Bash

Sublime Text3를 위한 RLS 설치 및 연동

설치

Rust는 nightly, beta, stable의 3가지 버전이 있는데 unstable한 기능들은 nightly rust에서만 가능하다고 합니다. RLS가 아직 unstable해서 그런지 nightly rust에서만 사용이 가능하다고 합니다.

nightly rust toolchain를 사용해야 하는데, 만약 설치가 되어 있지 않다면 다음 과정에서 설치가 됩니다.

Nightly rust tool-chain은 rustup을 이용해서 설치를 할 수 있는데, 저는 이미 stable이 rustup설치시 같이 설치가 된 상태인 것 같군요.

다음 명령어로 설치된 toolchain 상태들을 알 수 있습니다.

$ rustup show
Bash

그리고 다음 명령어로 nightly toolchain으로 설정할 수 있습니다.

$ rustup default nightly
Bash

만약 nightly 툴체인이 설치되어 있지 않다면 설치도 같이 진행을 합니다.

그리고 나서 RLS를 설치합니다.

$ rustup update
$ rustup component add rls rust-analysis rust-src
Bash

그리고 rls가 제대로 동작하는지를 다음 명령어로 확인합니다.

$ rustup run nightly rls --version
rls 1.41.0 (5fde462 2020-02-21)
Bash

이제 RLS가 잘 설치된 것 같군요.

서브라임 텍스트와의 연동

서브라임 텍스트에서 RLS와 연동하려면 Package Control에서 LSP라는 녀석을 설치하면 됩니다.

아까처럼 Ctrl+shift+p로 명령어창을 띄운 뒤 , package install을 치고 엔터를 누릅니다.

좌측 하단에 Progress bar가 나타난뒤, 패키지 목록 검색 창이 뜨면 LSP를 고르면 됩니다.

Detail 설명란에 Language Server Protocol이라고 나와있는 녀석입니다.

설치가 완료되면 위와 같은 메시지가 뜨네요.

그리고 LSP for Rust를 활성화를 시켜줘야 하는데, Rust Project를 아무거나 열고, main.rs나 lib.rs같은 파일을 하나 엽니다.

그리고 아까처럼 커맨드 팔렛트를 연뒤 (Ctrl+Shift+P) LSP:Enable 로 검색하면 아래와 같이 뜹니다.

둘 중 하나를 고르면 됩니다. 이 프로젝트에서만 활성화 할 것인지, 아닌지를 고를 수 있네요.

그리고 언어도 골라야하는데, rust를 선택해줍니다.

어허 또 무슨 에러일까요.

RLS가 실행이 안되어서 그런 것 같으니, 터미널을 하나 열어서 따로 실행을 시켜줍니다.

실행을 하고 나서 다시 LSP: Enable 설정을 해 주면 설정이 완료되었습니다.

RLS가 잘 동작하는지 확인해보기위해서, rs 확장자로 된 파일에 적당히 수정을 해 보도록 하겠습니다.

use std::fmt;를 추가해주고 저장을 하니 unsed import라고 warning이 뜨는군요. RLS가 잘 설정된 것으로 보입니다.

Visual Studio Code 를 위한 RLS 설치 및 연동

VS Code에서 RLS 설치 및 연동은 서브라임 텍스트에 비해 비교적 쉬운편입니다.

일단 Visual Studio Code와 Rustup가 설치가 되어있다는 가정하에 진행해보도록 하겠습니다.

VScode에서 Rust Extension을 설치해보도록 하겠습니다. Ctrl + P를 눌러서 ext install rust를 입력해서 검색을 합니다.

이중에서 Rust (rls)를 눌러서 Install을 합니다.

설치가 다 된 이후 reload를 하면 되는데 Ctrl + Shift + P를 눌러서 커맨드 팔렛트를 연 뒤 reload를 치면 됩니다.

그리고 Rust 프로젝트 디렉토리를 열면 자동적으로 Rustup component를 설치하려고 합니다.

rs 확장자로 된 파일을 하나 열면 아래에 저런 창이 뜹니다.

rustup을 찾지 못하는 것 같으니, nightly를 아까 서브라임 환경 설정할 때 처럼 설정해주도록 합시다. 아니면 VS code를 다시 시동을 하면 아마 인식을 할 것 같네요.

이제는 Rustup을 못찾는다는 이야기는 안하고 RLS가 설치되어 있지 않다고 합니다. Yes를 눌러서 설치를 해줍니다.

터미널에 무언가가 뜨면서 설치가 진행되는 것 같습니다.

설치가 완료되었네요. 좌측 하단 상태바에서도 RLS가 돈다고 뜹니다.

저런 tooltip도 뜹니다. 성공적으로 된 것 같네요.

빌드와 실행도 잘 됩니다.

굿!

https://github.com/sublimelsp/LSP

https://rinthel.github.io/2017/08/20/rust-vscode-macos/

https://github.com/rust-lang/rustup
https://github.com/rust-lang/rust-enhanced

저저번주쯤 주말에 올해 2020년의 첫 킥스타트 라운드 A가 있었는데, 아무것도 모르고 주말에 잠을 퍼질러 자다가 참여를 못하게 되었다.

A라운드는 근데 문제 난이도가 낮아서 빨리풀기 대회였다니 뭐 이런이야기들을 들었는데, 대회 당시에는 참여를 못했지만 나중에 업솔빙이라도 해볼 겸 시간 날때 풀어보았다.

이번해의 킥스타트는 저번과는 다르게 Large dataset도 제출한 뒤 바로 full-feedback을 준다고 한다. 맞았는지 틀렸는지를 바로 알려준다는 것은 뭔가 좋은 것 같으면서도 안 좋은것 같기도 하다.

바로 한번 문제 풀어보도록 하겠다.

문제들은 여기에서 확인하고 다시 풀어볼 수 있다.

총 4문제가 있다. 정답률을 보니 난이도가 왼쪽 < 오른쪽 문제로 가는 것 같다.

1. Allocation

문제는 간단하다. N개의 집이 있고, 각각의 집의 가격은 Ai원이다. 그리고 총 B달러가 있을때 가장 많은 집을 사고 싶다고 한다. 몇개를 살 수 있는가?

그냥 Ai를 오름차순으로 소팅한 뒤 예산을 넘지 않는 만큼만 진행하면 된다. $O(NlgN)$로 풀리며, N이 $10^5$이므로 쉽게 풀린다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int A[100005];
void solve() {
	int N, B;
	cin >> N >> B;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A, A + N);
	int ans = 0;
	for (int i = 0; i < N; i++) {
		if (B >= A[i]) {
			B -= A[i];
			ans++;
		}
		else {
			break;
		}
	}
	printf("%d\n", ans);
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}
C++

2. Plates

접시를 골라서 그 값들을 최대로 해야하는데, 접시는 위에서부터 연속된 것들만 고를 수 있다. 접시를 고르는 총 개수도 정해져있다.

dp문제인데, 맨처음에 dp인 것 같다가 시간복잡도가 안될 것 같았다는 생각이 좀 들어서 약간 긴가민가 했었다. 근데 문제를 부분문제로 나눌 수 있고 독립되게 풀린다는 것이 보여서  dp가 맞는 듯 했다.

2차원 dp로 풀 수 있는데 각 항의 정의는 다음과 같다.

$dp[i][j]$는 i번째 줄까지 쭉 진행했을 때, j개의 접시를 골라서 낼 수 있는 최대 점수

이러면 $dp[i][j]$를 이용해서 다음 줄에서 k개의 접시를 구하는 경우$dp[i+1][j+k]$를 쉽게 구할 수 있다.

for-loop를 돌리는 식으로 구현해보았다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int a[55][33];
int dp[55][1505]; //dp[i][j]는 i번째 라인까지 j개의 plate를 골라서 얻을 수 있는 최대 점수.
void solve() {
	int N, K, P;
	cin >> N >> K >> P;
	memset(dp, 0, sizeof(dp));
	memset(a, 0, sizeof(a));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			cin >> a[i][j];
			a[i][j] += a[i][j - 1];
		}
	}

	
	for (int i = 1; i <= K; i++) {
		dp[1][i] = a[1][i];
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= i * K; j++) {
			for (int k = 0; k <= K; k++) {
				dp[i + 1][j + k] = max(dp[i + 1][j + k], dp[i][j] + a[i + 1][k]);
			}
		}
	}
	printf("%d\n", dp[N][P]);
	return;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}
C++

3. Workout

이거는 증가하는 수열에서 인접한 수열 사이의 차이를 일정 값 이하로 만들고 싶은 상황이다. 이 때  수열 사이 사이에 임의의 값을 갖는 녀석을 끼워넣을 수 있다. 이 때 인접한 수열 사이의 차이값의 최소값을 구하는 그런 문제이다.

최소값 구하는 문제, 최대값 구하는 문제 중 이러한 류의 문제들, 차이값의 최소 와 같은 좀 복잡한 값의 최소/최대문제는 보통 결정문제로 변경해서 푸는 파라메트릭 서치 문제이다.

인접한 값의 차이를 d 이하로 만들 수 있는가? 의 결정 문제로 바꾼 뒤 이녀석을 통해서 binary search를 돌리면 풀린다.

그리고 이 결정 문제는 보통 그리디나 선형 시간복잡도로 풀리게 된다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;

int M[100005];
int N, K;
bool ok(int v) {
	int k = K;
	for (int i = 1; i < N; i++) {
		int diff = M[i] - M[i - 1];
		k -= (diff + v - 1) / v - 1;
	}
	return k >= 0;
}
int solve() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> M[i];
	}
	int l = 1;
	int r = 1e9;
	while (l < r) {
		int m = (l + r) / 2;
		if (ok(m)) {
			r = m;
		}
		else {
			l = m + 1;
		}
	}
	return r;
}
int main() {
	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		cout << "Case #" << t << ": " << solve() << endl;
	}
}
C++

4. Bundling

문자열들을 같은 크기의 Group들로 균일하게 나눈 뒤, 그 그룹들의 Longest prefix의 길이만큼 점수를 얻는데 이 점수를 최대화하는 그런 문제이다. 그룹을 어떻게 나눌 것인가까지는 알 필요 없이 점수만을 계산할 수 있다고 한다. 맨처음 이 문제를 보고 문자열 그냥 소팅한 뒤 K개씩 그룹핑 하면 되지 않을까 했는데 조금 생각해보니 바로 반례가 나왔다..

K가 만약 3이라고 하면 문자열이 다음과 같이 나왔을때 그리디하게 하면 최적화되지 않은 그룹핑이 된다.

A A A B C C C D E E E F

이런 경우 하나씩만 있는 B, D, F는 어차피 점수를 낼 수 없으므로 자기내들끼리 묶여서 남에게 피해를 주지 않아야 하는데 greedy하게 묶으면 망한다.

솔루션을 보니, Trie를 구축한 뒤, Trie Node별로 나타난 횟수를 체크해놓고, 나타난 횟수를 A라고 할때 각 노드별 floor(A/K)를 더하면 된다고 한다.

A % K에 해당하는 K개가 되지 못한 그룹녀석들은 어차피 어디에 끼여도 점수를 낼 수 없으므로 버리게 된다.

조금 생각해보니 correct한 알고리즘인 것이 이해가 되었다.

Trie는 malloc으로 구현하는 것이 귀찮아서 배열을 두고 정적할당과 같은 테크닉으로 구현을 해 보았다.

그리고 dfs로 모든 노드를 순회하면서 점수를 계산했다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;

#define MAXN 2000006
class Node {
public:
	char c;
	int num;
	int next[28];
	Node() {
		clear();
	}
	void clear() {
		memset(next, 0, sizeof(next));
		num = 0;
		c = 0;
	}
};
Node nodes[MAXN];
int cnt;
int dfs(int v, int k) {
	auto& cnode = nodes[v];
	int ret = cnode.num / k;
	for (char c = 'A'; c <= 'Z'; c++) {
		if (cnode.next[c - 'A'])
			ret += dfs(cnode.next[c - 'A'], k);
	}
	return ret;
}
int solve() {
	int n, k;
	cin >> n >> k;
	//clear prev data
	for (int i = 0; i <= cnt; i++) {
		nodes[i].clear();
	}
	cnt = 0;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		int ptr = 0;
		for (char c : s) {
			auto& next = nodes[ptr].next[c - 'A'];
			if (!next) {
				next = ++cnt;
				nodes[next].c = c;
			}
			ptr = next;
			nodes[ptr].num++;
		}
	}
	
	return dfs(0, k);
}
int main() {
	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		cout << "Case #" << t << ": " << solve() << endl;
	}
}
C++

CTF에서 크립토계열 문제들을 보면 이따금씩 등장하는 공격기법이다.

딱히 어려운 공격법은 아니니 곧바로 예시를 들면서 설명을 들어가자.

HMAC(Hash-based Message Authentication Code)

HMAC이 뭐냐면 Hash 기반의 MAC이다. 여기서 MAC은 Message Authentication Code인데, 일종의 전자서명이라고 보면 된다.

만약 A라는 사람이 B에게 "마트에서 계란 5개 사와"라는 메시지를 보낸다고 치자. 그런데 이 메시지가 B에게 도착했는데, A가 보낸게 맞고 다른 공격자가 임의로 변조시킨 메시지가 아니라는것을 알고 싶다고 하자.

이때 쓰이는 것이 MAC이다. A와 B가 공통적으로 공유하는 키 값이 있다고 하고, 공격자는 이 키를 모른다고 하자.

그러면 A는 메시지를 보내면서 key 값 뒤에 메시지를 붙인 뒤 해쉬를 취한 값으로 서명값을 만든다.

다음과 같은 모양이 나오게 된다.

signature = sha256( key + message )

만약 공유하는 비밀 키의 내용이 "CarpeDiem"이라고 하자.

그러면 서명값은 sha256("CarpeDiem마트에서 계란 5개 사와") 의 값이되게 된다.

그리고 이 서명값을 메시지와 같이 보낸다고 하자.

그러면 B는 메시지와 서명값을 받고, 본인이 가지고 있는 키를 기반으로 서명값을 만들었을때 이 서명값이 전달된 서명값과 일치하면 이 메시지는 A가 만든것이 맞다는 것을 알 수 있다.

공격자는 A와 B가 공유하고 있는 키 값을 알 수 없으므로 정당한 서명값을 만들 수 없다.

Hash Length extension attack

이러한 HMAC을 쓰는 경우 특정 조건이 맞으면 이 해쉬 길이 확장공격을 사용할 수 있다.

이 공격으로 공유되는 비밀 키 값은 알수가 없지만, 어떤 메시지와 서명값의 쌍을 안다면 메시지 뒤에 다른 문자열이 추가된 메시지와 그에 맞는 정당한 서명값을 만들 수 있다.

사전 조건

공격을 하기 위해 필요한 조건들은 몇 가지 정보들이다. 다음 내용들을 알면 공격이 가능하다.

1. 키의 길이

2. message의 내용