이전에 fail fail fail 한 패망의 매치. 돌아보았는데 여전히 틀림 [....] 나는 갈길이 멀었단 것을 깨달았다. -_-; IntelliJ 에서 각종 오버라이딩 코드나 constructor 를 자동으로 짜 주니까 코드를 좀 오버엔지니어링 하게 되는 감이 있는데.. 좀 잘 밸런스를 맞춰봐야 할 듯.. ㅠㅠ
250 UnluckyIntervals
일단 2 4 처럼 가운데 하나 끼어 있는 unlucky number 는 luckiness (?) 가 0 이다 까지는 알았는데, 첫 숫자가 2 일때 1은.. 생각 못했네. -_-
lang:java
public class UnluckyIntervals {
private class Candidate implements Comparable {
int lo, me, hi;
private Candidate(int lo, int me, int hi) {
this.lo = lo;
this.me = me;
this.hi = hi;
assert(lo < me && me < hi);
//System.out.println("Candidate: " + lo + " < " + me + " < " + hi + " => " + intervals());
}
private long intervals() {
long A = hi - lo - 1;
long B = me - lo - 1;
return (B+1) * (A-B);
}
public int compareTo(Object o) {
Candidate other = (Candidate)o;
long A = intervals();
long B = other.intervals();
if(A < B) return -1;
if(A > B) return 1;
return me - other.me;
}
}
public int[] getLuckiest(int[] luckySet, int n) {
sort(luckySet);
int[] ret = new int[n];
ArrayList<Integer> zeros = new ArrayList<Integer>();
for(int l: luckySet) zeros.add(l);
for(int i = 1; i < luckySet.length; ++i) {
if(luckySet[i-1] + 2 == luckySet[i]) {
zeros.add(luckySet[i-1]+1);
}
}
if(luckySet[0] == 2) zeros.add(1);
sort(zeros);
if(n <= zeros.size()) {
for(int i = 0; i < n; ++i) {
ret[i] = zeros.get(i);
}
return ret;
}
int am = 0;
for(int z: zeros) { ret[am++] = z; }
PriorityQueue<Candidate> c = new PriorityQueue<Candidate>();
HashSet<Integer> seen = new HashSet<Integer>();
int prev = 0;
for(int here: luckySet) {
if(here - prev > 2) {
seen.add(prev + 1);
seen.add(here - 1);
c.add(new Candidate(prev, prev + 1, here));
c.add(new Candidate(prev, here - 1, here));
}
prev = here;
}
while(c.size() > 0 && am < n) {
Candidate h = c.remove();
ret[am++] = h.me;
for(int delta = -1; delta <= 1; delta += 2) {
if(h.lo >= h.me + delta || h.hi <= h.me + delta || seen.contains(h.me + delta)) continue;
seen.add(h.me + delta);
c.add(new Candidate(h.lo, h.me + delta, h.hi));
}
}
int mx = luckySet[luckySet.length-1] + 1;
while(am < n) {
ret[am++] = mx++;
}
return ret;
}
}
진짜 무식하게 짰네...
500 EndlessStringMachine
Program 의 첫 글자가 $ 라는 제약 안 보고 시작했다가, 백만 년 고민...
lang:java
public class EndlessStringMachine {
String input, program;
int n, a, b;
private ArrayList<Long> lengths;
private char getChar(int skip, int iter) {
if(lengths.get(iter) <= skip) return '-';
if(iter == 0) {
return input.charAt(skip);
}
for(int i = 0; i < program.length(); ++i) {
if(program.charAt(i) == '$') {
long len = lengths.get(iter-1);
if(len > skip) {
return getChar(skip, iter-1);
}
skip -= len;
}
else {
if(skip == 0) {
return program.charAt(i);
}
--skip;
}
}
return '_';
}
public String getFragment(String input, String program, int s, int min, int max) {
this.input = input;
this.program = program;
n = input.length();
a = b = 0;
for(char ch: program.toCharArray()) if(ch == '$') { ++a; } else { ++b; }
--min; --max;
char[] ret = new char[max - min + 1];
if(a == 1) {
fill(ret, '-');
long len = n + s * (long)b;
for(int i = min; i <= max; ++i) {
if(i < input.length()) {
ret[i-min] = input.charAt(i);
} else if(b > 0 && i < len) {
ret[i-min] = program.charAt(1 + (i - input.length()) % b);
}
}
}
else {
lengths = new ArrayList<Long>();
lengths.add((long)input.length());
for(int i = 1; i <= s; ++i) {
long t = lengths.get(i-1) * a + b;
lengths.add(t);
if(t >= max) break;
}
System.out.println("Original s was " + s);
s = min(s, lengths.size()-1);
System.out.println(s + " iterations result in length " + lengths.get(s) + " .. is enough");
for(int i = min; i <= max; ++i) {
ret[i-min] = getChar(i, s);
}
}
return new String(ret);
}
}
1000 FeudaliasWar
별 생각 없이 대회 때 짰던 이분매칭을 짰더니 너무 느렸다. (그래프 노드 개수 상한 하드코딩을 했음에도 불구하고.) 그래서 가능한 답들의 셋을 모두 계산하고 여기에서 discrete binary search. 근데 이렇게 하면 epsilon 때문에 틀릴수 있다는 [....] 아아아아.... oTL 그거 하고 나니까 이번엔 또 너무 느려... 결국 BipartiteMatch 클래스를 다시 짜야 했다.
.. 자바 하지 말걸그랬나?
lang:java
public class FeudaliasWar {
private class BipartiteMatch {
private class Edges extends ArrayList<Integer> {};
Edges[] adj;
int[] bmatch;
int n, m;
boolean[] seen;
private BipartiteMatch(int n, int m) {
this.n = n;
this.m = m;
adj = new Edges[n];
for(int i = 0; i < n; ++i) adj[i] = new Edges();
bmatch = new int[m];
seen = new boolean[n];
fill(bmatch, -1);
}
private void addEdge(int a, int b) {
adj[a].add(b);
}
private boolean improve(int here) {
if(seen[here]) return false;
seen[here] = true;
for(int i = 0; i < adj[here].size(); ++i) {
int there = adj[here].get(i);
if(bmatch[there] == -1 || improve(bmatch[there])) {
bmatch[there] = here;
return true;
}
}
return false;
}
private int solve() {
int ret = 0;
for(int i = 0; i < n; ++i) if(adj[i].size() > 0) {
fill(seen, false);
if(improve(i)) ++ret;
}
return ret;
}
}
int n, m;
int[] bx, by, sx, sy;
double[][] hit;
double takeOff, recharge, speed;
public double getMinimumTime(int[] baseX, int[] baseY, int[] siloX, int[] siloY, int takeOffTime, int rechargeTime, int missileSpeed) {
bx = baseX; by = baseY; sx = siloX; sy = siloY;
n = sx.length;
m = bx.length;
takeOff = takeOffTime / 60.0;
recharge = rechargeTime;
speed = missileSpeed;
hit = new double[n][m];
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
hit[i][j] = hypot(sx[i] - bx[j], sy[i] - by[j]) / speed;
}
}
ArrayList<Double> cands = new ArrayList<Double>();
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
for(int k = 0; k < m; ++k) {
double D = (takeOff + recharge) * j + takeOff + hit[i][k];
cands.add(D);
}
}
}
sort(cands);
int lo = -1, hi = cands.size()-1;
System.out.println(cands.size() + " candidates");
while(lo + 1 < hi) {
System.out.printf("%d/%d\n", lo, hi);
int guess = (lo + hi) / 2;
double mid = cands.get(guess);
int M = min(m, (int)((mid - takeOff) / (takeOff + recharge)) + 1);
BipartiteMatch bm = new BipartiteMatch(n*M, m);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < M; ++j) {
double launch = (takeOff + recharge) * j + takeOff;
if(launch > mid) break;
double travel = mid - launch;
for(int k = 0; k < m; ++k)
if(hit[i][k] <= travel + 1e-8)
bm.addEdge(i * M + j, k);
}
}
if(bm.solve() < m)
lo = guess;
else
hi = guess;
}
return cands.get(hi);
}
}
훗훗훗 ㅇ_ㅇ