2012-05-08

AOJの過去のステータスを見るツールを作った

AOJ

過去に投げたソースを検索しやすくするためにRuby（特にフレームワークは使用せず）で書きました。
http://k8n.biz/aojsts/

2012-05-06

0558-Cheese

AOJ

問題概要

日本語なので略

解法

N回BFSを行なう

実装(Java)

import java.util.*;

public class Main {
	Scanner cin;
	class State{
		int time,x,y;
		State(int time,int x,int y){
			this.time=time;
			this.x=x;
			this.y=y;
		}
	}
	void run(){
		cin=new Scanner(System.in);
		int H=cin.nextInt(),W=cin.nextInt(),N=cin.nextInt();
		String[] MAP=new String[H];
		int []dx={1,0,-1,0},dy={0,1,0,-1};
		int result=0;
		for(int i=0;i<H;i++)MAP[i]=cin.next().replaceAll("S","0");
		for(int i=0;i<N;i++){
			int sx=-1,sy=-1;
			Queue<State> que=new LinkedList<State>();
			Boolean[][] visited=new Boolean[H][W];
			for(int p=0;p<H;p++){
				for(int q=0;q<W;q++){
					visited[p][q]=false;
					if(MAP[p].charAt(q)==i+'0'){
						sx=q;sy=p;
					}	
				}	
			}	
			que.add(new State(0,sx,sy));
			while(!que.isEmpty()){
				State now=que.poll();
				if(MAP[now.y].charAt(now.x)==i+1+'0'){
					result+=now.time;
					break;
				}
				for(int k=0;k<4;k++){
					int nx=now.x+dx[k],ny=now.y+dy[k];
					if(nx>=0&&nx<W&&ny>=0&&ny<H){
						if(visited[ny][nx]==false&&MAP[ny].charAt(nx)!='X'){
							visited[ny][nx]=true;
							que.add(new State(now.time+1,nx,ny));
						}
					}
				}
			}
		}
		printf("%d\n",result);
	}

	void printf(String format,Object... args){
		System.out.printf(format, args);
	}

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

}

2012-05-05

PKU 1383-Labyrinth

PKU

問題概要

マス目上に木となっている地図が与えられる。最大の距離となる2点の距離を求めよ。

解法

木の2点間最長距離を求めるには、任意の頂点から探索を行ない一番遠かった点から再度探索を行なう。
これをBFSで実装した。

実装(C++)

#include <cstdio>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
typedef pair<int,int> P;
queue<P> que;
int H,W;
int T;
char in[1001];
char MAP[1001][1001];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int sx,sy;
int cost[1001][1001];
int calc(int &sx,int &sy){
  memset(cost,0x3F,sizeof(cost));
  cost[sx][sy]=0;
  que.push(P(sx,sy));
  while(!que.empty()){
    P now=que.front();que.pop();
    sx=now.first;sy=now.second;
    int time=cost[sx][sy];
    for(int i=0;i<4;i++){
      int nx=sx+dx[i],ny=sy+dy[i];
      if(MAP[nx][ny]=='.'){
        if(cost[nx][ny]>time+1){
          cost[nx][ny]=time+1;
          que.push(P(nx,ny));
        } 
      }
    }
  }
  return cost[sx][sy];
}
int main(){
  scanf("%d",&T);
  for(;T--;){
    scanf("%d%d",&W,&H);
    for(int y=0;y<H;y++){
      scanf("%s",in);
      for(int x=0;x<W;x++){
        MAP[x][y]=in[x];
      }
    }
    for(int y=1;y<H-1;y++){
      for(int x=1;x<W-1;x++){
        if(MAP[x][y]=='.'){
          int cnt=0;
          for(int k=0;k<4;k++){
            if(MAP[x+dx[k]][y+dy[k]]=='.')cnt++;
          }
          if(cnt<=1){
            sx=x;sy=y;
            x=W;
            y=H;
            break;
          }
        }
      }
    }
    calc(sx,sy);
    printf("Maximum rope length is %d.\n",calc(sx,sy));
  }   
}

2012-05-05

PKU 3219-Binomial Coefficients

PKU

問題概要

0<=k<=n<2^31について、nCkの偶奇判定をせよ

解法

nCk=n!/k!/(n-k)!なので、整数m!に含まれる素因数2の個数を求めることが出来れば簡単に判定出来る。
これは、mをどんどん2で割っていくことで求めることが出来る。

実装(C)

#include <stdio.h>
int calc_2(int a){
  int res=0;
  a>>=1;
  while(a>0){
    res+=a;
    a>>=1;
  }
  return res;
}
int n,k;
int main(){
  while(~scanf("%d%d",&n,&k)){
    if(calc_2(n)-calc_2(k)-calc_2(n-k)>0){
      puts("0");
    }else{
      puts("1");
    }
  }
}

2012-05-05

PKU 1037-A decorative fence

PKU

問題概要

長さが1〜Nの木がそれぞれあり、それを使って柵を作りたい。
ただし、柵はジグザグな形になるようにするようにしたい。
C番目の作り方を求めよ。

解法

dp[進行方向の残りの木の本数][全体の残りの木の本数]とすることで、O(N^2)でパターン数を求めることが出来る。
パターン数から作り方を復元する。

実装(C++)

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long lli;
int N;
lli C;

bool input(){
  static int testcase=-1;
  if(testcase<0){
    cin>>testcase;
  }
  if(testcase==0)return false;
  cin>>N>>C;
  C--;
  testcase--;
  return true;
}
lli dp[30][30];
// forward：進行方向の数、n；全体の残りの数)
lli solve(int forward,int n){
  if(dp[forward][n]>=0)return dp[forward][n];
  if(n==0)return 1;
  lli sum=0;
  for(int i=0;i<forward;i++){
    sum+=solve(i+n-forward,n-1);
  }
  return dp[forward][n]=sum;
}
int main(){
  memset(dp,-1,sizeof(dp));
  while(input()){
    int s=0,b;
    for(int i=1;i<=N;i++){ //最初の数を決める
      if(C<solve(i-1,N-1)){
        b=-1;
        s=i;
        break;
      }else{
        C-=solve(i-1,N-1);
      } 
      if(C<solve(N-i,N-1)){
        b=1;
        s=i;
        break;
      }else{
        C-=solve(N-i,N-1);
      }
    }
    bool used[21];
    memset(used,0,sizeof(used));
    used[s]=true;
    cout<<s;
    int back=s;
    for(int i=1;i<N;i++){
      if(b==1){
        int cnt=0;
        for(int j=1;j<back;j++){
          if(used[j]==false)cnt++;
        }
        for(int j=back+1;j<=N;j++){
          if(used[j])continue;
          if(C<solve(cnt,N-i-1)){
            cout<<" "<<j;
            back=j;
            used[j]=true;
            break;
          }else{
            C-=solve(cnt,N-i-1);
          }
          cnt++;
        }
      }else{
        int cnt=0;
        for(int j=1;j<=N;j++){
          if(used[j]==false)cnt++;
        }
        for(int j=1;j<back;j++){
          if(used[j])continue;
          cnt--;
          if(C<solve(cnt,N-i-1)){
            cout<<" "<<j;
            back=j;
            used[j]=true;
            break;
          }else{
            C-=solve(cnt,N-i-1);
          }
        }
      }
      b=b*-1;
    }
    cout<<endl;
  }
}

2012-05-05

PKU 1083-Moving Tables

PKU

問題概要

廊下を通って荷物を運ぶことを考える。それぞれの荷物運びに関しては独立に廊下を共有しないものに関しては同時に運ぶことが出来る。
何回運べば、全ての荷物を運び終えることが出来るか。

解法

ある廊下の前を通る最大の数を求める

実装(C)

int main(){
  int T,N,a,b,i,j;
  scanf("%d",&T);
  for(;T--;){
    int r[200];
    int ans=0;
    memset(r,0,sizeof(r));
    scanf("%d",&N);
    for(i=0;i<N;i++){
      scanf("%d%d",&a,&b);
      a=(a-1)/2;b=(b-1)/2;
      if(a>b){
        j=b;
        b=a;
        a=j;
      }
      for(j=a;j<=b;j++){
        r[j]+=1;
        if(r[j]>ans)ans=r[j];
      }
    }
    printf("%d\n",ans*10);
  }
  return 0;
}

2012-05-03

PKU 3626-Mud Puddles

PKU

問題概要

格子状のマス目があり、いくつかに障害物がおかれている。(0,0)から(x,y)への移動の最短距離を求めよ3

解法

BFS

実装(C++)

#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int,int> P;
queue<P> que;
int MAP[1010][1010];
int cost[1010][1010];
int d[4]={1,0,-1,0};
int main(){
  int x,y,n;
  cin>>x>>y>>n;
  x+=505;y+=505;
  for(int i=0;i<n;i++){
    int tx,ty;
    cin>>tx>>ty;
    tx+=505;
    ty+=505;
    MAP[tx][ty]=1;
  }
  que.push(P(505,505));
  memset(cost,0x7f,sizeof(cost));
  cost[505][505]=0;
  while(!que.empty()){
    P now=que.front();que.pop();
    int turn=cost[now.first][now.second];
    if(now.first==x&&now.second==y)break;
    for(int i=0;i<4;i++){
      int nx=now.first+d[i],ny=now.second+d[i^1];
      if(MAP[nx][ny])continue;
      if(nx>0&&nx<1009&&ny>0&&ny<1009){
        if(cost[nx][ny]>turn+1){
          que.push(P(nx,ny));
          cost[nx][ny]=turn+1;
        }
      }
    }
  }
  cout<<cost[x][y]<<endl;

}