JMK no matter what

아까 저녁에 (자바로) 다시 건드려 봤는데 수면부족이라 그런지, 한번 말렸던 셋이라 트라우마-_- 가 있어서 그런지 어찌나 머리가 안굴러 가던지.

푼것들은 생각해보면 trivial 하다. orz

250 LateProfessor

대회 당시에는 교수가 도착하는 시간이 정해져 있을 때 latetime 처리를 안해줘서 챌린지당했었다.. 이것만 고치면 맞나? 라고 생각했지만 그거 고쳐서 내봐도 틀리네. -_-; 선형시간인데.. 그냥 무식하게 푸는게 짱이거늘.. 내가 대체 왜 룰기반으로 풀생각을 했을까. 당시 대회의 top10 을 봤는데 if 문으로 푼사람은 하나도 없다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

그냥 찌질 orz

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 LateProfessor {
    private int[] overlap(int[] a, int lo, int hi) {
        a[0] = max(a[0], lo);
        a[1] = min(a[1], hi);
        return a;
    }
    public double getProbability(int waitTime, int walkTime, int lateTime, int bestArrival, int worstArrival) {
        if(bestArrival == worstArrival) {
            int r = bestArrival % (walkTime + waitTime);
            if((0 <= r && r <= waitTime) || r + lateTime > waitTime + walkTime) return 0;
            return 1;
        }
        if(lateTime >= walkTime) return 0;
        int arrive = -(walkTime + waitTime);
        int unsafe = 0;
        do {
            arrive += walkTime + waitTime;
            int[] region = {bestArrival, worstArrival};
            region = overlap(region, 0, arrive);
            region = overlap(region, arrive - walkTime, arrive - lateTime);
            unsafe += max(0, region[1] - region[0]);
        } while(arrive < worstArrival);
        return (double)unsafe / (worstArrival - bestArrival);
    }
}

500 SuperSum

대회 당시에도 S(n,k) 찍는 프로그램을 파이썬으로 짜서 돌려봤는데, 이항계수란것도 모르고, 대각선 대칭이란 것도 몰랐다니. 좀 더 들여다볼걸 그랬나. -_- 거참. BigInteger 쓰면 그냥 초간단...

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 SuperSum {
    public int calculate(int k, int n) {
        BigInteger c = BigInteger.ONE;
        // return C(n+k, k+1)
        for(int i = 0; i < k+1; ++i) {
            c = c.multiply(BigInteger.valueOf(n+k-i));
        }
        for(int i = 2; i <= k+1; ++i) {
            c = c.divide(BigInteger.valueOf(i));
        }
        System.out.println("=> " + c.toString());
        c = c.remainder(BigInteger.valueOf(1000000007));
        return c.intValue();
    }
}

1k 는 아직 보는 중.