실로 오랜만의 SRM. 첫 자바 매치!!! 두둥!!!
코드를 좀 깔끔하게 짜려는 노력을 하게 되다 보니 (그리고 아직 문법이 100% 익숙하지 않아서 IntelliJ 에 의존해야 하다 보니) 코딩이 많이 느리다. 반복된 연습이 역시 대안이지 싶은데 귀찮아서.. 그래도 둘다 패스했으니 별 불만은 없다. 이지+미디엄에서 시간이 너무 오래 걸려서 하드를 짤 시간이 없어서 결국 포기하고 챌페이즈 진입. 하지만 결국 챌린지 못하고 5x 등. 레이팅은 -7. :-(
그래도 패스패스에 의미를 둬야겠다. 아 그리고 하드도 나중에 결국 풀음.
250 DoubleXor
그냥 구현하면 되는 문제. 실제로는 이 operator 가 commutative 하지 않다는걸 생각 안하고 연산 순서 바꾼 사람들이 있어서 좀 챌린지 꺼리가 있었다고 한다.
lang:java
public class DoubleXor {
private int dxor(int a, int b) {
int mult = 1, ret = 0;
while(a > 0 || b > 0) {
int ad = a % 10, bd = b % 10;
ret += mult * ( (ad ^ bd) % 10 );
mult *= 10;
a /= 10;
b /= 10;
}
return ret;
}
public int calculate(int N) {
if(N == 1) return N;
int ret = dxor(N, N-1);
for(int i = N-2; i >= 1; --i)
ret = dxor(ret, i);
return ret;
}
}
500 NumbersAndMatches
Standard DP. 숫자 스트링으로 변환하는 법도 구글해서 찾아봐야 하는 이 상황 -_-
lang:java
public class NumbersAndMatches {
private final int required[] = { 6, 3, 5, 5, 4, 5, 6, 3, 7, 6 };
private final String maskRep[] = { "1110111", "0010011", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
private int[] mask, given;
private String rep;
private long[][][] cache;
private long go(int here, int excess, int allowed) {
if(here == given.length) {
if(excess == 0) return 1;
return 0;
}
long ret = cache[here][excess+128][allowed];
if(ret != -1) return ret;
ret = 0;
for(int newDigit = 0; newDigit < 10; ++newDigit) {
int remove = mask[given[here]] &~ mask[newDigit];
int add = mask[newDigit] &~ mask[given[here]];
if(allowed >= Integer.bitCount(remove)) {
ret += go(here + 1, excess + Integer.bitCount(remove) - Integer.bitCount(add), allowed - Integer.bitCount(remove));
}
}
cache[here][excess+128][allowed] = ret;
//System.out.println("here = " + here + " excess = " + excess + " allowed = " + allowed + " => " + ret);
return ret;
}
public long differentNumbers(long N, int K) {
mask = new int[10];
for(int i = 0; i < 10; ++i) {
mask[i] = 0;
for(int j = 0; j < 7; ++j) {
mask[i] = mask[i] * 2 + (int)(maskRep[i].charAt(j) - '0');
}
if(Integer.bitCount(mask[i]) != required[i] || maskRep[i].length() != 7) {
System.out.println("Sanity check fail");
}
}
rep = Long.toString(N);
given = new int[rep.length()];
for(int i = 0; i < rep.length(); ++i) {
given[i] = (int)(rep.charAt(i) - '0');
}
cache = new long[given.length + 1][256][127];
for(long[][] row: cache) {
for(long[] r2: row) {
fill(r2, -1);
}
}
return go(0, 0, K);
}
}
1000 MegaSum
원하는 칸의 위치가 (y, x) 라고 하면, 맨 왼쪽 위 칸은 yx 번 더해지고, 그 오른쪽 칸은 y(x-1) 칸 더해지고... 이런 식에서 패턴을 찾아서 O(sqrt(N)) 에 푼다. 실제로는 mul() 에서 a 나 b 가 mod 를 초과할 경우에 ((a % mod) * (b % mod)) % mod 해야 하는데 (a * b) % mod 해서 한번 틀림. :-(
lang:java
public class MegaSum {
private final long MOD = 1000000007;
// returns 1+2+3+..+n
private long sum(long n) {
return (n*(n+1)) / 2;
}
// returns 1^2+2^2+3^2+..+n^2
private long sumsq(long n) {
if(n > 100000) {
System.out.println("oops" + n);
}
return (n*(n+1)*(2*n+1)) / 6;
}
private long mul(long a, long b) {
return ((a % MOD) * (b % MOD)) % MOD;
}
private long add(long a, long b) { return (a+b+MOD) % MOD; }
private long increasing(long a, long n, long m, long d) {
// returns d * (am + (a+1)(m-1) + (a+2)(m-2) + .. + (a+n-1)(m-n+1))
// = d * sum(i = 0 to n-1){ (a+i)(m-i) }
// = d * sum(i = 0 to n-1){ am - i^2 + mi - ai }
// = d * (anm - sum(i){i^2} + (m-a)*sum(i){i} )
long ret = 0;
ret = add(ret, mul(mul(a, n), m)); // anm
ret = add(ret, -sumsq(n-1)); // -sum(i){i^2}
ret = add(ret, mul(add(m, -a), sum(n-1))); // (m-a)*sum(i){i}
return mul(ret, d);
}
private long decreasing(long a, long n, long m, long d) {
// returns d * (am + (a-1)(m-1) + (a-2)(m-2) + .. + (a-n-1)(m-n+1))
// = d * sum(i = 0 to n-1){ (a-i)(m-i) }
// = d * sum(i = 0 to n-1){ am + i^2 - mi - ai }
// = d * (anm + sum(i){i^2} - (m+a)*sum(i){i} )
long ret = 0;
ret = add(ret, mul(mul(a, n), m)); // anm
ret = add(ret, sumsq(n-1)); // sum(i){i^2}
ret = add(ret, -mul(add(m, a), sum(n-1))); // (m-a)*sum(i){i}
return mul(ret, d);
}
// coords are one-based
private long solve(long y, long x) {
long ret = 0;
long maxring = max(y, x);
for(long ring = 1; ring <= maxring; ++ring) {
if(ring % 2 == 0) {
// vert are increasing
if(ring <= x) {
long firstValue = (ring - 1) * (ring - 1) + 1;
long length = min(ring, y);
long decrement = x - ring + 1;
ret = add(ret, increasing(firstValue, length, y, decrement));
}
// horz are decreasing
if(ring <= y) {
long firstValue = ring * ring;
long length = min(ring - 1, x);
long decrement = y - ring + 1;
ret = add(ret, decreasing(firstValue, length, x, decrement));
}
}
else {
// vert are decreasing
if(ring <= x) {
long firstValue = ring * ring;
long length = min(ring, y);
long decrement = x - ring + 1;
ret = add(ret, decreasing(firstValue, length, y, decrement));
}
// horz are increasing
if(ring <= y) {
long firstValue = (ring - 1) * (ring - 1) + 1;
long length = min(ring - 1, x);
long decrement = y - ring + 1;
ret = add(ret, increasing(firstValue, length, x, decrement));
}
}
}
return ret;
}
public int calculate(long N) {
long ring = 1;
while(ring * ring < N) {
++ring;
}
long rem = ring * ring - N;
long x = min(rem, ring - 1);
long y = ring - 1 - (rem - x);
// every coord is 1-based
++x; ++y;
if(ring % 2 == 1) {
long t = x;
x = y;
y = t;
}
System.out.println(N + " => (" + y + ", " + x + ")");
return (int)(solve(y, x) % MOD);
}
}
