2010年7月8日木曜日

ACM/ICPC国内予選 コード

汚いけどコード晒しあげ.

A
import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class A{
Scanner sc;
PrintWriter pw, db;

int[] dx={-1, 0, 1, 0};
int[] dy={0, 1, 0, -1};

void run(){
init();
for(;;){
int m=sc.nextInt();
if(m==0)
break;
P[] ps=new P[m];
ps[0]=new P(0, 0);
for(int i=1; i<m; i++){
int n=sc.nextInt();
int d=sc.nextInt();
ps[i]=new P(ps[n].x+dx[d], ps[n].y+dy[d]);
}
int xmin=0, xmax=0;
int ymin=0, ymax=0;
for(P p : ps){
xmin=min(xmin, p.x);
xmax=max(xmax, p.x);
ymin=min(ymin, p.y);
ymax=max(ymax, p.y);
}
int w=xmax-xmin+1;
int h=ymax-ymin+1;
db.println(w+" "+h);
pw.println(w+" "+h);
}
close();
}

public static void main(String[] args){
new A().run();
}

void init(){
try{
sc=new Scanner(new FileInputStream("A"));
pw=new PrintWriter("A.out");
db=new PrintWriter(System.out);
}catch(IOException e){}
}

void close(){
sc.close();
pw.close();
db.close();
}

static class P{
int x, y;

P(int x, int y){
this.x=x;
this.y=y;
}
}

}

B
import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class B{
Scanner sc;
PrintWriter pw, db;

int w, h;
int[][] right, down;

void run(){
init();
for(;;){
w=sc.nextInt();
h=sc.nextInt();
if(w==0&&h==0)
break;
right=new int[h][w-1];
down=new int[h-1][w];
for(int k=0; k<h-1; k++){
for(int i=0; i<w-1; i++)
right[k][i]=sc.nextInt();
for(int i=0; i<w; i++)
down[k][i]=sc.nextInt();
}
for(int i=0; i<w-1; i++)
right[h-1][i]=sc.nextInt();
bfs();
}
close();
}

void bfs(){
int[][] map=new int[h][w];
LinkedList<P> q=new LinkedList<P>();
P s=new P(0, 0);
map[0][0]=1;
q.addLast(s);
while(!q.isEmpty()){
P p=q.removeFirst();
int x=p.x, y=p.y;
int d=map[p.y][p.x];

// up
int nx=x;
int ny=y-1;
if(ny>=0&&down[y-1][x]==0&&map[ny][nx]==0){
map[ny][nx]=d+1;
q.addLast(new P(nx, ny));
}

// down
nx=x;
ny=y+1;
if(ny<h&&down[y][x]==0&&map[ny][nx]==0){
map[ny][nx]=d+1;
q.addLast(new P(nx, ny));
}

// left
nx=x-1;
ny=y;
if(nx>=0&&right[y][x-1]==0&&map[ny][nx]==0){
map[ny][nx]=d+1;
q.addLast(new P(nx, ny));
}

// right
nx=x+1;
ny=y;
if(nx<w&&right[y][x]==0&&map[ny][nx]==0){
map[ny][nx]=d+1;
q.addLast(new P(nx, ny));
}
}
db.println(map[h-1][w-1]);
pw.println(map[h-1][w-1]);
}

public static void main(String[] args){
new B().run();
}

void init(){
try{
sc=new Scanner(new FileInputStream("B"));
pw=new PrintWriter("B.out");
db=new PrintWriter(System.out);
}catch(IOException e){}
}

void close(){
sc.close();
pw.close();
db.close();
}

static class P{
int x, y;

P(int x, int y){
this.x=x;
this.y=y;
}
}

}

C

import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class C{
Scanner sc;
PrintWriter pw, db;

LinkedList<Integer> list1, list2;
int[] dp1;

static final int INF=1>>28;

void run(){
init();
f();
for(;;){
int n=sc.nextInt();
if(n==0)
break;
int a1=dp1[n];
int a2=cal(n);
db.println(a1+" "+a2);
pw.println(a1+" "+a2);
}
close();
}

void f(){
int n=1000000;

list1=new LinkedList<Integer>();
list2=new LinkedList<Integer>();
for(int i=1;; i++){
int t=i*(i+1)*(i+2)/6;
if(t>n)
break;
list1.add(t);
if(t%2==1)
list2.add(t);
}

// 予め計算しておく
dp1=new int[n+1];
Arrays.fill(dp1, INF);
dp1[0]=0;
for(int j=1; j<=5; j++){
for(int i=0; i<n; i++){
if(dp1[i]!=j-1)
continue;
for(int k : list1){
if(i+k<=n)
dp1[i+k]=min(dp1[i+k], j);
}
}
}
}

int cal(int n){
int[] dp=new int[n+1];
Arrays.fill(dp, INF);
dp[0]=0;
for(int j=1;; j++){
for(int i=0; i<n; i++){
if(dp[i]!=j-1)
continue;
for(int k : list2){
if(i+k==n)
return j;
if(i+k<n)
dp[i+k]=min(dp[i+k], j);
}
}
}
}

public static void main(String[] args){
new C().run();
}

void init(){
try{
sc=new Scanner(new FileInputStream("C"));
pw=new PrintWriter("C.out");
db=new PrintWriter(System.out);
}catch(IOException e){}
}

void close(){
sc.close();
pw.close();
db.close();
}

}

D
import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class D{
Scanner sc;
PrintWriter pw, db;

static final int INF=1<<28;
static final double EPS=1e-6;

int w, h;
int[][] field;

int n;
B[] bs;
B root;

boolean stable;

boolean[][] visited;

void run(){
init();
for(;;){
w=sc.nextInt();
h=sc.nextInt();
sc.nextLine();
if(w==0&&h==0)
break;
field=new int[h][w];
for(int j=0; j<h; j++){
String s=sc.nextLine();
for(int i=0; i<w; i++){
char c=s.charAt(i);
if(c=='.')
field[j][i]=-1;
else
field[j][i]=Integer.parseInt(""+c);
}
}
identify();
bs=new B[n];
for(int i=0; i<n; i++)
bs[i]=new B();
genG();
genTree();
stable=true;
dfs(root);
db.println(stable?"STABLE":"UNSTABLE");
pw.println(stable?"STABLE":"UNSTABLE");
}
close();
}

// id付け
void identify(){
n=0;
visited=new boolean[h][w];
for(int j=0; j<h; j++){
for(int i=0; i<w; i++){
if(!visited[j][i]&&field[j][i]!=-1){
search(i, j, field[j][i]);
n++;
}
}
}
}

void search(int x, int y, int i){
if(x<0||x>=w||y<0||y>=h)
return;
if(visited[y][x])
return;
if(field[y][x]!=i)
return;
visited[y][x]=true;
search(x-1, y, i);
search(x+1, y, i);
search(x, y-1, i);
search(x, y+1, i);
field[y][x]=n;
}

// 重心の生成
void genG(){
LinkedList<Double>[] lists=new LinkedList[n];
for(int i=0; i<n; i++)
lists[i]=new LinkedList<Double>();

for(int j=0; j<h; j++)
for(int i=0; i<w; i++)
if(field[j][i]!=-1)
lists[field[j][i]].add(i+0.5);
for(int i=0; i<n; i++){
double sumx=0;
for(double x : lists[i])
sumx+=x;
bs[i].g=sumx/4;
}
}

// 木の生成,接地面のx座標の計算,根の決定
void genTree(){
for(int j=0; j<h-1; j++){
for(int i=0; i<w; i++){
int f1=field[j][i];
int f2=field[j+1][i];
if(f1==-1||f2==-1||f1==f2)
continue;
B b1=bs[f1];
B b2=bs[f2];
b1.left=min(b1.left, i);
b1.right=max(b1.right, i+1);
if(!b2.children.contains(b1))
b2.children.add(b1);
}
}
root=null;
for(int i=0; i<w; i++){
int id=field[h-1][i];
if(field[h-1][i]!=-1){
root=bs[id];
root.left=min(root.left, i);
root.right=max(root.right, i+1);
}
}
}

void dfs(B rt){
if(!stable)
return;
if(rt==null)
return;
double mass=0;
double mg=0;
for(B b : rt.children){
dfs(b);
mass+=b.mass;
mg+=b.mass*b.g;
}
// マージ
rt.g=(mg+rt.mass*rt.g)/(mass+rt.mass);
rt.mass+=mass;

if(rt.g>rt.left+EPS&&rt.g+EPS<rt.right)
;
else
stable=false;
}

class B{
LinkedList<B> children;
double left, right;
double g;
double mass;

B(){
children=new LinkedList<B>();
left=INF;
right=-INF;
mass=1;
}
}

public static void main(String[] args){
new D().run();
}

void init(){
try{
sc=new Scanner(new FileInputStream("D"));
pw=new PrintWriter("D.out");
db=new PrintWriter(System.out);
}catch(IOException e){}
}

void close(){
sc.close();
pw.close();
db.close();
}

}

0 件のコメント: