Sunday, September 22, 2013

acmicpc.net - 2013 인터넷 예선 대비 대회 7


이번에는 명우랑 역할분담이 잘되어서 릴레이 식으로 잘 푼 것 같다ㅎㅎ

Link : http://www.acmicpc.net/contest/view/14

A. 삼각 그래프 - Accepted
위상정렬 + dp이지만 그래프 특성상 위상정렬을 별도로 할 필요없음.

B. 피파 월드컵 - Accepted
2^x꼴로 만들어주면 된다.

C. 아즈텍 피라미드 - Accepted
계차수열임을 알면 쉽게 풀 수 있다.

D. 나이트 이야기 - Later Solved
그리디하게 100*100 안으로 넣은 다음에 bfs를 통해 구한 값을 이용해서 나이트의 최소 이동 횟수를 알 수 있다. 그 다음에는 bitmask dp를 통해서 풀면 됨. 종료 3분 후, Accepted 받음.

E. 정규형 - Accepted
명우가 혼자 풀었는데 특별히 어렵지는 않은 문제인 것 같다.

F. 월드 오브 큐브 - Not Solved
문제 보고 어려운 것 같아서 안 품.

G. 최대 공통 증가 수열 - Accepted
"D[n][m] : S가 1~n까지, A가 1~m까지일 때의 최대 길이"라고 정의하고 dp로 풀면된다.
O(N^3)을 떠올리기 쉽지만, 전처리를 통해서 O(N^2)으로 풀 수 있다.

H. 병원 - Accepted
문제 이해하기가 힘든 문제. O(VE)에 명우가 품.

I. 사탕 줍기 대회 - Accepted
어떤 k번째 행에서 i번째를 선택하면 i-1번째와 i+1번째를 선택하지 못하는 경우의 최대합을 구하는 함수를 dp(k)라 하자. 모든 행에 대해서 dp(k)를 수행하고 그 값들로 새로운 행을 만들어서 다시 dp(k)를 수행하면 된다.

J. 거의 최단 경로 - Accepted
별로 어렵지 않은 문제. 명우가 품.

Saturday, September 21, 2013

acmicpc.net - 2013 인터넷 예선 대비 대회 6


이번엔 myungwoo랑 팀플을 해봤는데..
앞/뒤로 나눠서 한 명은 코딩하고 다른 한 명은 생각하는 건 비효율적이고 안 좋다는 걸 깨달음.

Link : http://www.acmicpc.net/contest/view/13

A. 쌍둥이 역설 - Accepted
그냥 식에 대입해서 풀면 됨.

B. 두 교수 - Solved Later
1번 교수와 2번 교수가 싫어하는 특수한 조건을 제외하고 문제를 푼 뒤(그리디), 1번 교수와 2번 교수가 같은 강의실을 사용할 경우 답에 +1을 해줌. 그리고 답이 2보다 작다면 2로 갱신해주어야함.

C. YAPTCHA - Accepted
각 항의 값이 0 또는 1이 됨을 알면 규칙을 찾아서 쉽게 소수 찾는 알고리즘으로 풀 수 있음.

D. 팀의 난이도 - Accepted
이분매칭 + 멕시멈 플로우

E. 풍선 - Solved Later
거리 차의 절댓값을 기준으로 오름차순으로 정렬한 후, 차례로 보면서 A에 가까우면 A에 몰아주고 B에 가까우면 B에 몰아줌. 풍선의 개수가 부족하면 다른 풍선을 써주면됨.

F. 자물쇠와 열쇠
그리디하게 재귀적으로 풀면되는데 열쇠를 하나만 들고 다닐 수 있음에 유의.

G. 힙 세기 - Solved Later
답이 (n-1)! / (2~n번 노드들의 서브 트리의 개수들의 곱) 임을 알면 소인수 분해를 통해서 답을 구할 수 있다.

H. 스도미노쿠 - Accepted
백트랙킹

I. 전구 게임
문제도 안 읽어봄.

J. 전기 요금 - Accepted
간단하게 하라는 대로 풀면 되는 문제.

Thursday, September 19, 2013

ACM ICPC 2009 Greater New York Regional

A. Simple sorting O(N log N)

B. Greedy O(N^2)
The value of a divided subset has to be bigger than a element.
If you decide a value, you can check the fact that it is possible or not.

C. Dynamic Programming
D(i, j) : minimum value in total 'j' stairs, having 'i' balls.
D(i, j) = min( D(i-1, j), max(1+D(i-1,k-1), 1+D(i, j - k) )

D. Stack or Heap O(N) or O(N log N)

E. STL next_permutation()

F. Dynamic Programming
D(i, j, k) : The number of ways in length 'i', adjecent bit are 'j', situation 'k'(number in 'i'th)
D(i, j, 0) = D(i-1, j, 0) + D(i-1, j, 1)
D(i, j, 1) = D(i-1, j-1, 1) + D(i-1, j, 0)
the answer is D(n, m, 0) + D(n, m, 1)

G. Graham Scan

H. Graham Scan & Mathematics

I. BFS with bitmask

Tuesday, September 17, 2013

Google Codejam 2008 Round 3 - C ( = acmicpc.net 1014)

Link : http://www.acmicpc.net/problem/1014
Link : http://code.google.com/codejam/contest/32002/dashboard#s=p2 (Problem C : No Cheating)

1) Small case(n, m <= 10)
Bitmask Dynamic Programming : O(N^2*(2^(2*N)))
But actual time complexity is much smaller because of the impossible situations.

2) Large case(n,m <= 80)
Bipartite matching , Maximum Flow

#include <iostream>
#include <memory.h>
#include <string>
using namespace std;
int C, N, M;
string bd[100];
int nbx[100][100], nby[100][100], v[100][100];
int T=0;
bool dfs(int a, int b) {
 if (a<0) return true;
 if(v[a][b]==T) return false;
 v[a][b]=T;
 for (int i=a-1;i<=a+1;i++) {
  for (int j=b-1;j<=b+1;j+=2) {
   if (i>=0 && i<M && j>=0 && j<N && bd[i][j]=='.') {
    if (dfs(nbx[i][j], nby[i][j])) {
     nbx[i][j]=a; nby[i][j]=b;
     nbx[a][b]=i; nby[a][b]=j;
     return true;
    }
   }
  }
 }
 return false;
}
int play() {
 memset(nbx,-1,sizeof(nbx));
 memset(nby,-1,sizeof(nby));
 memset(v, -1, sizeof(v)); T=-1;
 int rst=0;
 for(int i=0;i<M;i++) for(int j=0;j<N;j++) {
  if (bd[i][j]=='.') {
   rst++;
   if (j%2) {
    T++;
    if (dfs(i,j)) rst--;
   }
  }
 }
 return rst;
}
int main() {
 cin>>C;
 for (int i=1; i<=C; i++) {
  cin>>M>>N;
  for (int r=0;r<M;r++) cin>>bd[r];
  cout<<play()<<endl;
 }
 return 0;
}

Sunday, September 15, 2013

acmicpc.net - 2013 인터넷 예선 대비 대회 5


Link : http://www.acmicpc.net/contest/view/11

A. 콘센트 - Accepted
Greedy. Note that if n and m is 0, the answer is 1

B. K번째 숫자 - Accepted
Segment tree, Merge Sort or Binary search

C. 포켓볼 - Accepted
Easy to solve with STL Map or Set.

D. 토너먼트 조작 - Accepted
Given n = (2^k) teams, and a team 1 such that for every team t that 1 cannot beat, 1 can beat a team t` that can beat t and 1 can beat as least half of the teams.
For every round (k in total) of the tournament
1) Match as many teams t that beat 1 to teams t` that can win them.
2) Let 1 play against a team from which it can win.
3) Let any remaining teams play against each other.
4) Remove the losers.

E. 책 쌓기 - Accepted
Pulling out a book in the sorted top is never useful, so always pull out the first non-sorted book
To move a big book from the top to position i, takes ( 2 ^ i )−1 steps.
Through the fact, we can solve this in O(N).

F. RFID 추적
Not solved yet.

G. L퍼즐
2 - SAT. Make connections for 'B'  with 4 directions and 'W' with all of  'B'.

H. 열차 지연 - Accepted
1) Dijkstra with heap or priority queue or 2) Bellman-Ford Algorithm.
D[x][t] = when the time is 't', the minimum cost of station 'x'.

I. 수영장 만들기
Not solved yet.

J. 정수 직사각형 - Accepted
Preprocess - sorting and counting

Saturday, September 7, 2013

acmicpc.net - 2013 인터넷 예선 대비 대회 2


Link : https://www.acmicpc.net/contest/scoreboard/7

A. RNG - Accepted
Change the form of the equation
y = a(x^2)+bx+c mod (2^n)  into  a(x^2)+bx+c`=0 mod (2^n)
if x is a solution for n, (x mod 2^(n-1)) is a solution for n-1
So, if x is an unique solution for n-1
1) x is possible solution for n
2) x + 2^(n-1) is possible solution for n
Maintaining solutions for increasing n
1) if solution is unique, continue.
2) else we can't get the unique solution.

B. 나쁜과학자
Minimum vertex cover

C. 큐빙
I didn't read the problem because the cube makes me tired.

D. 차원 워프 드라이브
I didn't read the problem.

E. 아! - Accepted
Simple strings' length comparison.

F. 도어맨 - Accepted
Greedy method.

G. 전화번호 목록 - Accepted
Ordinary Trie problem.
http://en.wikipedia.org/wiki/Trie

H. 무글 맵스 - Accepted
Dynamic programming. d[i][j] = min(d[k][j-1] + s[k][i])

I. 대충 정렬
I didn't read the problem.

J. 연결
It might be solved with Minimum Cost-Maximum Flow(MCMF)
Similar problem : http://poj.org/problem?id=2195