예전에 연습했더라도 홈페이지에 연습 로그가 없으면 다 한다는 각오로 돌고 있다. 자바로 돈 두번째 세트. 실제 알고리즘보다 코딩에 신경을 더 쓰게 되는 사태가... 연습방에서 이전에 내가 문제 푼 게 있는데, C# 으로 짜놨더라. 나도 레인보우 코딩 가나여...
250 PerfectPermutation
넘쉽당 'ㅅ'
lang:java
import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import java.math.*;
import java.util.*;
public class PerfectPermutation {
public int reorder(int[] P) {
int n = P.length;
boolean[] taken = new boolean[n];
int cycles = 0;
for(int i = 0; i < n; ++i) {
if(!taken[i]) {
++cycles;
int here = i;
while(!taken[here]) {
taken[here] = true;
here = P[here];
}
}
}
if(cycles == 1) return 0;
return cycles;
}
}
500 StrangeCountry
사이클이랑 트리로 나눠서 생각했다가 틀렸는데 (바보냐), 사이클에도 중복 간선이 여러 개 있는 경우가 있다. 그리고, 간선의 개수가 유지된다는 점을 생각해 보면, 간선의 개수가 충분한 한 항상 합칠 수 있다는 것을 알 수 있다. /pigeonhole/php/good
lang:java
import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import java.math.*;
import java.util.*;
public class StrangeCountry {
private void dfs(String[] g, int[] c, int here) {
c[here] = 1;
for(int there = 0; there < g.length; ++there) {
if(c[there] == -1 && g[here].charAt(there) == 'Y') {
dfs(g, c, there);
}
}
}
public int transform(String[] g) {
int n = g.length;
if(n == 1) return 0;
for(String s: g) {
if(s.indexOf('Y') < 0) return -1;
}
int edges = 0;
for(String s: g) for(char c: s.toCharArray()) if(c == 'Y') ++edges;
edges /= 2;
if(edges < n-1) return -1;
int[] component = new int[n];
fill(component, -1);
int cmp = 0;
for(int i = 0; i < n; ++i) {
if(component[i] == -1) {
dfs(g, component, i);
++cmp;
}
}
return cmp-1;
}
}
1000 PaperAndPaint
/segmenttree 직접 구현해서 풀었다. 남자는 근성임! erase(unique) 이디엄 등이 없어서 너무 불편하다. ㅠㅠ 아직 API 도 잘 모르니, 구현의 양이 많아지면 느려질 수밖에. ArrayList 접근 방식이 배열과 다른 것도 사실 불편....;; 대신 메모리 관리 등에 들어가는 비용이 줄어들어서, C++ 에선 매우 귀찮았을 실제 트리를 작성해 버렸다는 사실.
lang:java
public class PaperAndPaint {
ArrayList<Integer> yy1, xx1, yy2, xx2;
private class Event implements Comparable {
int y1, y2, x, amt;
private Event(int y1, int y2, int x, int amt) {
this.y1 = y1;
this.y2 = y2;
this.x = x;
this.amt = amt;
}
public int compareTo(Object o) {
return x - ((Event)o).x;
}
}
private class Node {
int width;
int left, right, mid, contained, sum;
Node lc, rc;
private Node(int[] yset, int left, int right) {
this.width = yset[right] - yset[left];
this.left = left;
this.right = right;
if(right - left > 1) {
this.mid = (left + right) / 2;
lc = new Node(yset, left, mid);
rc = new Node(yset, mid, right);
}
}
private void add(int lo, int hi, int amt) {
if(right <= lo || hi <= left) return;
if(lo <= left && right <= hi)
contained += amt;
else if(right - left > 1) {
lc.add(lo, hi, amt);
rc.add(lo, hi, amt);
}
if(contained > 0) {
sum = width;
}
else {
sum = (right - left > 1 ? lc.sum + rc.sum : 0);
}
}
}
private long areaSum() {
TreeSet<Integer> ys = new TreeSet<Integer>();
for(int y: yy1) ys.add(y);
for(int y: yy2) ys.add(y);
int[] yset = new int[ys.size()];
int sz = 0;
TreeMap<Integer,Integer> m = new TreeMap<Integer,Integer>();
for(Integer j: ys) {
m.put(j, sz);
yset[sz++] = j;
}
Node root = new Node(yset, 0, sz-1);
Event[] events = new Event[yy1.size() * 2];
for(int i = 0; i < yy1.size(); ++i) {
//System.out.println("(" + yy1.get(i) + "," + xx1.get(i) + ") ~ (" + yy2.get(i) + "," + xx2.get(i) + ")");
events[i*2] = new Event(m.get(yy1.get(i)), m.get(yy2.get(i)), xx1.get(i), 1);
events[i*2+1] = new Event(m.get(yy1.get(i)), m.get(yy2.get(i)), xx2.get(i), -1);
}
sort(events);
long ret = 0;
for(int i = 0; i < events.length; ++i) {
if(i > 0 && events[i].x != events[i-1].x) {
ret += (events[i].x - events[i-1].x) * (long)root.sum;
}
root.add(events[i].y1, events[i].y2, events[i].amt);
}
return ret;
}
public long computeArea(int width, int height, int[] xfold, int[] cnt, int[] x1, int[] y1, int[] x2, int[] y2) {
yy1 = new ArrayList<Integer>();
xx1 = new ArrayList<Integer>();
yy2 = new ArrayList<Integer>();
xx2 = new ArrayList<Integer>();
for(int i = 0; i < xfold.length; ++i) {
int h = height / (cnt[i] + 1);
for(int j = 0; j <= cnt[i]; ++j) {
int top = -1, bottom = -1;
if(j % 2 == 0) {
// not reversed
top = h * j + y1[i];
bottom = h * j + y2[i];
}
else {
// reversed
top = h * (j+1) - y2[i];
bottom = h * (j+1) - y1[i];
}
// x reversed
int left = max(0, xfold[i] - x2[i]), right = max(0, xfold[i] - x1[i]);
if(right > 0) {
yy1.add(top); yy2.add(bottom);
xx1.add(left); xx2.add(right);
}
// x not reversed
left = min(width, xfold[i] + x1[i]); right = min(width, xfold[i] + x2[i]);
if(left < width) {
yy1.add(top); yy2.add(bottom);
xx1.add(left); xx2.add(right);
}
}
}
return height * (long)width - areaSum();
}
}
