그제인가 돌았던 매치인데 IntelliJ 로 돌아보았다. 그전에는 넷빈즈랑 이클립스로 div2 한 라운드씩 돌았는데, 지금까지는 IntelliJ 가 제일 낫다. 유료인데다 비싸지만 회사에서 사준 라이센스가 있어서...
결론은 음 나름 할만하네.. 라는 것. 특히 950 은 무려 넷웍플로인데, 넷웍플로 클래스 안쓰고 그냥 짰다. ㅋㅋ 오랜만에 해보네 이런거 ㅋㅋㅋ
소스가 깔끔한 것은 좋다.
250 Underprimes
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 Underprimes {
public int howMany(int A, int B) {
int ret = 0;
for(int i = A; i <= B; ++i) {
int tmp = i, factors = 0;
for(int j = 2; j*j <= tmp; ++j) {
while(tmp % j == 0) {
tmp /= j;
++factors;
}
}
if(tmp > 1) ++factors;
if(factors == 1) continue;
++ret;
for(int j = 2; j*j <= factors; ++j) {
if(factors % j == 0) {
--ret;
break;
}
}
}
return ret;
}
}
550 BedroomFloor
우리 집 바닥이 이렇게 생겼다.
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 BedroomFloor {
private long[] count(int y1, int x1, int y2, int x2) {
long[] ret = new long[6];
if(y1 >= y2 || x1 >= x2) return ret;
for(int y = rdn(y1); y <= y2; y += 5) {
for(int x = rdn(x1); x <= x2; x += 5) {
int xo = min(x+5, x2) - max(x, x1), yo = min(y+5, y2) - max(y, y1);
if(yo <= 0 || xo <= 0) continue;
if((y / 5) % 2 == (x / 5) % 2) {
ret[xo] += yo;
}
else {
ret[yo] += xo;
}
}
}
return ret;
}
private int rup(int x) {
return ((x + 4) / 5) * 5;
}
private int rdn(int x) {
return (x / 5) * 5;
}
private void add(long[] a, long[] b) {
for(int i = 0; i < a.length; ++i)
a[i] += b[i];
}
public long numberOfSticks(int x1, int y1, int x2, int y2) {
long[] required = new long[6];
if(x2 - x1 <= 5 || y2 - y1 <= 5) {
add(required, count(y1, x1, y2, x2));
}
else {
int x3 = rup(x1), x4 = rdn(x2), y3 = rup(y1), y4 = rdn(y2);
required[5] += ((x4 - x3) * (long)(y4 -y3)) / 5;
add(required, count(y1, x1, y3, x2));
add(required, count(y4, x1, y2, x2));
add(required, count(y3, x1, y4, x3));
add(required, count(y3, x4, y4, x2));
}
for(int i = 1; i <= 5; ++i) {
System.out.print(required[i] + " ");
}
System.out.println();
long ret = required[5];
ret += required[4];
required[1] -= required[4];
ret += required[3];
required[2] -= required[3];
if(required[2] >= 0) {
long buy = (required[2] + 1) / 2;
ret += buy;
required[1] -= (5 * buy) - required[2] * 2;
}
else {
required[1] += required[2] * 2;
}
ret += (max(0, required[1]) + 4) / 5;
return ret;
}
}
950 NowhereLand
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 NowhereLand {
int n;
int[][] flow, cap;
boolean[] visited;
private boolean dfs(int here) {
if(here == n+1) return true;
visited[here] = true;
for(int there = 0; there <= n+1; ++there) {
if(cap[here][there] - flow[here][there] > 0 && !visited[there]) {
if(!dfs(there)) continue;
flow[here][there]++;
flow[there][here] = -flow[here][there];
return true;
}
}
return false;
}
public int placeGuards(String[] cities, int k, String[] guards, String[] agencies) {
n = cities.length;
boolean[][] hasGuard = new boolean[n][k];
boolean[][] hasAgency = new boolean[n][k];
for(int i = 0; i < n; ++i) {
String[] toks = guards[i].split(" ");
for(String tok: toks) {
if(tok.length() == 0) continue;
hasGuard[i][Integer.parseInt(tok)] = true;
}
toks = agencies[i].split(" ");
for(String tok: toks) {
if(tok.length() == 0) continue;
hasAgency[i][Integer.parseInt(tok)] = true;
}
}
int ret = 0;
for(int agency = 0; agency < k; ++agency) {
flow = new int[n+2][n+2];
cap = new int[n+2][n+2];
for(int city = 0; city < n; ++city) {
if(hasGuard[city][agency]) {
cap[n][city] = 9999;
}
else if(!hasAgency[city][agency]) {
cap[city][n+1] = 9999;
}
for(int other = 0; other < n; ++other) {
if(cities[city].charAt(other) == '1') {
cap[city][other] = 1;
}
}
}
visited = new boolean[n+2];
while(dfs(n)) {
fill(visited, false);
++ret;
}
}
return ret;
}
}
950 NowhereLand (2)
결국 NetworkFlow 클래스 짰음.
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 NowhereLand {
private class NetworkFlow {
int n;
int[][] flow, cap;
boolean[] visited;
public NetworkFlow(int n) {
this.n = n;
flow = new int[n][n];
cap = new int[n][n];
visited = new boolean[n];
}
public void addEdge(int a, int b, int c)
{
cap[a][b] += c;
}
private int push(int src, int sink, int amt) {
if(src == sink) return amt;
visited[src] = true;
for(int next = 0; next < n; ++next) {
if(cap[src][next] - flow[src][next] > 0 && !visited[next])
{
int am = push(next, sink, min(amt, cap[src][next] - flow[src][next]));
if(am > 0) {
flow[src][next] += am;
flow[next][src] = -flow[src][next];
return am;
}
}
}
return 0;
}
public int solve(int src, int sink) {
int ret = 0;
visited[src] = true;
while(true) {
fill(visited, false);
int amt = push(src, sink, Integer.MAX_VALUE);
if(amt == 0) break;
ret += amt;
}
return ret;
}
}
public int placeGuards(String[] cities, int k, String[] guards, String[] agencies) {
int n = cities.length;
boolean[][] hasGuard = new boolean[n][k];
boolean[][] hasAgency = new boolean[n][k];
for(int i = 0; i < n; ++i) {
String[] toks = guards[i].split(" ");
for(String tok: toks) {
if(tok.length() == 0) continue;
hasGuard[i][Integer.parseInt(tok)] = true;
}
toks = agencies[i].split(" ");
for(String tok: toks) {
if(tok.length() == 0) continue;
hasAgency[i][Integer.parseInt(tok)] = true;
}
}
int ret = 0;
for(int agency = 0; agency < k; ++agency) {
NetworkFlow nf = new NetworkFlow(n+2);
for(int city = 0; city < n; ++city) {
if(hasGuard[city][agency]) {
nf.addEdge(n, city, 9999);
}
else if(!hasAgency[city][agency]) {
nf.addEdge(city, n+1, 9999);
}
for(int other = 0; other < n; ++other) {
if(cities[city].charAt(other) == '1') {
nf.addEdge(city, other, 1);
}
}
}
ret += nf.solve(n, n+1);
}
return ret;
}
