M-Judge 10158 Dungeon Wall

ACM-ICPC JAG Summer Camp 2010, Day 4
Problem D: Dungeon Wall
より

import java.util.*;
import java.lang.*;
import java.math.*;

public class Main{

    Scanner sc=new Scanner(System.in);

    int INF=1>>28;

    int w, h, n;
    int ix, iy, ox, oy;

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

    boolean[][] visited;
    int[][] dist;
    P[][] ps;

    void run(){
        w=sc.nextInt();
        h=sc.nextInt();
        n=sc.nextInt();
        can=new boolean[h][w][4];
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                for(int k=0; k<4; k++)
                    can[j][i][k]=true;

        for(int j=0; j<h; j++){
            can[j][0][3]=false;
            can[j][w-1][1]=false;
        }
        for(int i=0; i<w; i++){
            can[0][i][0]=false;
            can[h-1][i][2]=false;
        }

        for(int i=0; i<n; i++){
            int sx=sc.nextInt();
            int sy=sc.nextInt();
            int tx=sc.nextInt();
            int ty=sc.nextInt();
            int x1=Math.min(sx, tx);
            int x2=Math.max(sx, tx);
            int y1=Math.min(sy, ty);
            int y2=Math.max(sy, ty);

            if(x1==x2){
                for(int y=y1; y<y2; y++){
                    if(x1>0)
                        can[y][x1-1][1]=false;
                    if(x1<w)
                        can[y][x1][3]=false;
                }
            }else{
                // y1==y2
                for(int x=x1; x<x2; x++){
                    if(y1>0)
                        can[y1-1][x][2]=false;
                    if(y1<h)
                        can[y1][x][0]=false;
                }
            }
        }

        ix=sc.nextInt();
        iy=sc.nextInt();
        ox=sc.nextInt();
        oy=sc.nextInt();

        visited=new boolean[h][w];
        dist=new int[h][w];
        ps=new P[h][w];
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                ps[j][i]=new P(i, j);

        int minDist=bfs();
        int maxdist=minDist;
        for(int j=0; j<h; j++){
            for(int i=0; i<w; i++){
                if(can[j][i][0]){
                    can[j][i][0]=false;
                    can[j-1][i][2]=false;
                    int d=bfs();
                    if(d!=INF)
                        maxdist=Math.max(maxdist, bfs());
                    can[j][i][0]=true;
                    can[j-1][i][2]=true;
                }
                if(can[j][i][1]){
                    can[j][i][1]=false;
                    can[j][i+1][3]=false;
                    int d=bfs();
                    if(d!=INF)
                        maxdist=Math.max(maxdist, bfs());
                    can[j][i][1]=true;
                    can[j][i+1][3]=true;
                }
            }
        }
        // println(minDist+"");
        // println(maxdist+"");
        println((maxdist-minDist)+"");
    }

    int bfs(){
        for(int j=0; j<h; j++){
            for(int i=0; i<w; i++){
                visited[j][i]=false;
                dist[j][i]=0;
            }
        }
        LinkedList<P> q=new LinkedList<P>();
        q.addLast(ps[iy][ix]);
        visited[iy][ix]=true;
        for(; !q.isEmpty();){
            P p=q.removeFirst();
            if(p.x==ox&&p.y==oy)
                return dist[p.y][p.x];
            for(int d=0; d<4; d++){
                int x=p.x+dx[d];
                int y=p.y+dy[d];
                if(can[p.y][p.x][d]&&!visited[y][x]){
                    q.addLast(ps[y][x]);
                    visited[y][x]=true;
                    dist[y][x]=dist[p.y][p.x]+1;
                }
            }
        }
        return INF;
    }

    class P{
        int x, y;

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

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

    void println(String s){
        System.out.println(s);
    }

    void print(String s){
        System.out.print(s);
    }
}

M-Judge 10157 Save your cats

ACM-ICPC JAG Summer Camp 2010, Day 4
Problem C: Save your cats
より

import java.util.*;
import java.lang.*;
import java.math.*;

public class Main{

    Scanner sc=new Scanner(System.in);

    int n, m;
    int[] x, y;

    int INF=1>>28;

    int[] p;
    int[] rank;

    void run(){
        n=sc.nextInt();
        m=sc.nextInt();
        x=new int[n];
        y=new int[n];

        for(int i=0; i<n; i++){
            x[i]=sc.nextInt();
            y[i]=sc.nextInt();
        }

        double sumW=0.0;
        E[] es=new E[m];
        for(int i=0; i<m; i++){
            int p=sc.nextInt()-1;
            int q=sc.nextInt()-1;
            double w=Math.sqrt((x[q]-x[p])*(x[q]-x[p])+(y[q]-y[p])*(y[q]-y[p]));
            sumW+=w;
            es[i]=new E(p, q, w);
        }

        Arrays.sort(es, new Comparator<E>(){
            public int compare(E e1, E e2){
                return e1.w<e2.w?1:-1;
            }
        });

        p=new int[n];
        rank=new int[n];
        for(int i=0; i<n; i++)
            p[i]=i;

        double extW=0.0;
        for(E e : es){
            if(findSet(e.v)!=findSet(e.u)){
                extW+=e.w;
                union(e.v, e.u);
            }
        }
        println((sumW-extW)+"");
    }

    void union(int x, int y){
        x=findSet(x);
        y=findSet(y);
        if(rank[x]>rank[y]){
            p[y]=x;
        }else{
            p[x]=y;
            if(rank[x]==rank[y]){
                rank[y]++;
            }
        }
    }

    int findSet(int x){
        if(p[x]!=x)
            p[x]=findSet(p[x]);
        return p[x];
    }

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

    void println(String s){
        System.out.println(s);
    }

    void print(String s){
        System.out.print(s);
    }

    class E{
        int v, u;
        double w;

        E(int v, int u, double w){
            this.v=v;
            this.u=u;
            this.w=w;
        }
    }
}

ただし，実行時間3:00[s]超．

M-Judge 10156 Kaeru Jump

ACM-ICPC JAG Summer Camp 2010, Day 4
Problem B: Kaeru Jump
より

import java.util.*;
import java.lang.*;
import java.math.*;

public class Main{

    Scanner sc=new Scanner(System.in);

    int h, w;
    int[][] a;
    int x0, y0;
    int dir;

    int[] dx={0, 1, 0, -1};
    int[] dy={-1, 0, 1, 0};
    char[] dc={'U', 'R', 'D', 'L'};

    int nLeaf;

    LinkedList<Character> solution;

    void run(){
        solution=new LinkedList<Character>();
        h=sc.nextInt();
        w=sc.nextInt();
        a=new int[h][w];

        for(int j=0; j<h; j++){
            String s=sc.next();
            for(int i=0; i<w; i++){
                char c=s.charAt(i);
                if(c=='.'){
                    a[j][i]=-1;
                }else if(c=='o'){
                    a[j][i]=nLeaf++;
                }else{
                    a[j][i]=nLeaf++;
                    x0=i;
                    y0=j;
                    switch(c){
                    case 'U':
                        dir=0;
                        break;
                    case 'R':
                        dir=1;
                        break;
                    case 'D':
                        dir=2;
                        break;
                    case 'L':
                        dir=3;
                        break;
                    }
                }
            }
        }
        sol();
    }

    void sol(){
        // show();
        rec(x0, y0, dir, nLeaf);
        for(char c : solution)
            print(c+"");
        println("");
    }

    boolean solved=false;

    void show(){
        for(int j=0; j<h; j++){
            for(int i=0; i<w; i++){
                print(a[j][i]+", ");
            }
            println("");
        }
        println("");
    }

    void rec(int x, int y, int dir0, int leaf){
        if(leaf==1){
            // println(Arrays.toString(solution.toArray()));
            solved=true;
            return;
        }
        // show();
        int l=a[y][x];
        a[y][x]=-1;
        for(int d=-1; d<=1; d++){
            int dir=(dir0+d+4)%4;
            int i=x;
            int j=y;
            for(; i>=0&&i<w&&j>=0&&j<h; i+=dx[dir], j+=dy[dir]){
                if(a[j][i]>=0){
                    solution.addLast(dc[dir]);
                    rec(i, j, dir, leaf-1);
                    if(solved)
                        return;
                    solution.removeLast();
                    break;
                }
            }
        }
        a[y][x]=l;
    }

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

    void println(String s){
        System.out.println(s);
    }

    void print(String s){
        System.out.print(s);
    }
}

M-Judge 10146 Carrot Tour

ACM-ICPC JAG Summer Camp 2010, Day 3
Problem B: Carrot Tour
より

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

public class Main{
    Scanner sc=new Scanner(System.in);

    final int INF=1>>28;
    final double EPS=1e-9;

    int n;
    double r;
    double theta;
    int[] xs, ys;
    double[][] cost;
    boolean[][][] can;

    void run(){
        n=sc.nextInt();
        r=sc.nextDouble();
        theta=sc.nextDouble();
        xs=new int[n];
        ys=new int[n];
        cost=new double[n][n];
        can=new boolean[n][n][n];
        for(int i=0; i<n; i++){
            xs[i]=sc.nextInt();
            ys[i]=sc.nextInt();
        }
        
        for(int j=0; j<n; j++){
            for(int i=0; i<n; i++){
                double dx=xs[j]-xs[i];
                double dy=ys[j]-ys[i];
                if(i==j)
                    cost[j][i]=INF;
                else
                    cost[j][i]=Math.sqrt(dx*dx+dy*dy);
            }
        }

        // i->j->k
        for(int k=0; k<n; k++){
            for(int j=0; j<n; j++){
                if(j==k)
                    continue;
                for(int i=0; i<n; i++){
                    if(i==k||i==j)
                        continue;
                    double x1=xs[j]-xs[i];
                    double y1=ys[j]-ys[i];
                    double x2=xs[k]-xs[j];
                    double y2=ys[k]-ys[j];
                    double cost=(x1*x2+y1*y2)
                            /Math.sqrt((x1*x1+y1*y1)*(x2*x2+y2*y2));
                    if(Math.cos(Math.toRadians(theta))<cost+EPS)
                        can[i][j][k]=true;
                }
            }
        }

        double dp[][]=new double[n][n];
        double t[][]=new double[n][n];

        for(int j=0; j<n; j++)
            for(int i=0; i<n; i++)
                t[i][j]=INF;
        for(int j=0; j<n; j++)
            t[0][j]=cost[0][j];

        for(int c=0;; c++){
            boolean f=false;
            for(int j=0; j<n; j++)
                for(int i=0; i<n; i++)
                    if(t[j][i]<r+EPS)
                        f=true;
            if(!f){
                println(c+"");
                return;
            }

            for(int k=0; k<n; k++){
                for(int j=0; j<n; j++){
                    dp[j][k]=INF;
                    for(int i=0; i<n; i++){
                        if(can[i][j][k]){
                            dp[j][k]=Math.min(dp[j][k], t[i][j]+cost[j][k]);
                        }
                    }
                }
            }
            for(int j=0; j<n; j++)
                for(int i=0; i<n; i++)
                    t[j][i]=dp[j][i];
        }
    }

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

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    void println(){
        System.out.println();
    }

}

M-Judge 10145 Ennichi

ACM-ICPC JAG Summer Camp 2010, Day 3
Problem A: Ennichi
より

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

public class Main{
    Scanner sc=new Scanner(System.in);

    final int INF=1>>30;
    final double EPS=1e-9;

    int h, w, n;
    char[][] a;

    void run(){
        h=sc.nextInt();
        w=sc.nextInt();
        n=sc.nextInt();
        a=new char[h][w];
        for(int j=0; j<h; j++){
            String s=sc.next();
            for(int i=0; i<w; i++){
                a[j][i]=s.charAt(i);
            }
        }

        for(int j=0; j<h; j++){
            for(int i=0; i<w-1; i++){
                if(a[j][i]==a[j][i+1])
                    continue;

                // swap(i,j)<->(i+1,j)
                char c=a[j][i];
                a[j][i]=a[j][i+1];
                a[j][i+1]=c;

                if(check()){
                    println("YES");
                    return;
                }

                c=a[j][i];
                a[j][i]=a[j][i+1];
                a[j][i+1]=c;
            }
        }
        println("NO");
    }

    void show(char[][] a){
        for(int j=0; j<h; j++){
            for(int i=0; i<w; i++){
                print(a[j][i]+"");
            }
            println("");
        }
    }

    boolean check(){
        boolean[][] clear;
        char[][] a=new char[h][w];
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                a[j][i]=this.a[j][i];

        for(;;){
            // 落下
            for(int i=0; i<w; i++){
                for(int j=1; j<h; j++){
                    if(a[j][i]!='.')
                        continue;
                    for(int k=j; k>0; k--)
                        a[k][i]=a[k-1][i];
                    a[0][i]='.';
                }
            }

            boolean cl=false;
            clear=new boolean[h][w];

            for(int y=0; y<h; y++){
                for(int x=0; x<w; x++){
                    // (x, y)から縦/横を調べる
                    if(a[y][x]=='.')
                        continue;

                    boolean f=true;
                    for(int y2=y; y2<y+n; y2++){
                        if(y2>=h||a[y2][x]!=a[y][x]){
                            f=false;
                            break;
                        }
                    }
                    if(f){
                        for(int y2=y; y2<h&&a[y2][x]==a[y][x]; y2++)
                            clear[y2][x]=true;
                        cl=true;
                    }

                    f=true;
                    for(int x2=x; x2<x+n; x2++){
                        if(x2>=w||a[y][x2]!=a[y][x]){
                            f=false;
                            break;
                        }
                    }
                    if(f){
                        for(int x2=x; x2<w&&a[y][x2]==a[y][x]; x2++)
                            clear[y][x2]=true;
                        cl=true;
                    }
                }
            }

            for(int j=0; j<h; j++)
                for(int i=0; i<w; i++)
                    if(clear[j][i])
                        a[j][i]='.';

            if(!cl)
                break;
        }
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                if(a[j][i]!='.')
                    return false;
        return true;
    }

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

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    void println(){
        System.out.println();
    }
}

M-Judge 10136 友だちの誘い方

ACM-ICPC JAG Summer Camp 2010, Day 2
Problem B: 友だちの誘い方
より

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

public class Main{
    Scanner sc=new Scanner(System.in);

    final int INF=1>>30;
    final double EPS=1e-9;

    int n;
    int[] a, b, c;

    int max=131072;
    int[] tree;

    void run(){
        tree=new int[max*2-1];
        n=sc.nextInt();
        a=new int[n];
        b=new int[n];
        int r=0;
        for(int i=0; i<n; i++){
            a[i]=sc.nextInt();
            b[i]=sc.nextInt();
            update(a[i], b[i]+1, 0, 0, max);
            r=Math.max(r, b[i]);
        }

        for(int i=r; i>=2; i--){
            int c=query(i);
            if(i<=c+1){
                println((i-1)+"");
                return;
            }
        }
        println("0");
    }

    void update(int a, int b, int k, int left, int right){
        // println(""+a+","+b+","+k+","+left+","+right);
        if(right<=a||b<=left)
            return;
        if(a<=left&&right<=b){
            tree[k]++;
            return;
        }
        update(a, b, k*2+1, left, (left+right)/2);
        update(a, b, k*2+2, (left+right)/2, right);
    }

    int query(int k){
        int ret=0;
        for(int i=k+max-1;;){
            ret+=tree[i];
            if(i==0)
                break;
            i=(i-1)/2;
        }
        return ret;
    }

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

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    void println(){
        System.out.println();
    }
}

ただし，実行時間3:00[s]超．

M-Judge 10135 雅先生の地球侵略日誌

ACM-ICPC JAG Summer Camp 2010, Day 2
Problem A: 雅先生の地球侵略日誌
より

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

public class Main{
    Scanner sc=new Scanner(System.in);

    final int INF=1>>30;
    final double EPS=1e-9;

    void run(){
        long n=sc.nextLong()-1;
        long r=1;
        int ans=0;
        for(; n/r!=0; r*=3, ans++);
        println(""+ans);
    }

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

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    void println(){
        System.out.println();
    }
}