11/16の課題について

11/16の課題

32名が提出

問題A 解答例(1)

import java.io.*;

class Cards{
    int[] card;
    int n;
    Cards(int n0){
	n=n0;
	card=new int[n];
	for(int i=0;i < n;i++){
	    card[i]=n-i;
	}
    }
    void cut(int p,int c){
	int[] extracted=new int[c];
	for(int i=0;i<=c-1;i++){
	    extracted[i]=card[p-1+i];
	}
	for(int i=0;i<=p-2;i++){
	    card[c+p-2-i]=card[p-2-i];
	}
	for(int i=0;i<=c-1;i++){
	    card[i]=extracted[i];
	}
    }
}

class A{
    public static void main(String[]args) throws IOException{
	BufferedReader d=new BufferedReader(new InputStreamReader(System.in));
	String result="";
	for(;;){
	    String nr=d.readLine();
	    int n=Integer.parseInt(nr.split(" ")[0]);
	    int r=Integer.parseInt(nr.split(" ")[1]);
	    if(n==0&&r==0)
		break;
	    else if((r-1)*(r-50)>0||(n-1)*(n-50)>0)
		throw new IllegalArgumentException("数値が規定の範囲外です");
	    else{
		Cards cards=new Cards(n);
		for(int i=0;i < r;i++){
		    String pc=d.readLine();
		    int p=Integer.parseInt(pc.split(" ")[0]);
		    int c=Integer.parseInt(pc.split(" ")[1]);
		    cards.cut(p,c);
		}
		result=result+cards.card[0]+" ";
	    }
	}
	String[] results=result.split(" ");
	for(int i=0;i < results.length;i++){
	    System.out.println(results[i]);
	}
    }
}

Cardsクラスを作ってすっきりと書いていますね．以下の点がちょっと気になりました．

pc.split(" ")の呼び出しをp, cそれぞれに行っていますが，それなりに重い処理なので，1回にまとめて，
```
  String[] tokens=pc.split(" ");
  int p=Integer.parseInt(tokens[0]);
  int c=Integer.parseInt(tokens[1]);
```
とするのが普通です．なお，重くない処理(整数同士の加算)の場合は，余計な一時変数を作らない方が見やすくなる場合はあります．
文字列型の変数resultに結果を貯めて，後でsplitしていますが．普通は， forループの中で
```
  System.out.println(cards.card[0]);
```
として終わりにします．

問題A 解答例(2)

import java.io.*;   
class A{
    public static void main(String[] args) throws IOException{
	BufferedReader d=new BufferedReader(new InputStreamReader(System.in));
	String an="";
	while(true){
	    String s=d.readLine();
	    String is[]=s.split(" ");
	    int n=Integer.parseInt(is[0]);
	    int r=Integer.parseInt(is[1]);
	    if(n==0&&r==0)break;
	    String card="0102030405060708091011121314151617181920212223242526272829303132333435363738394041424344454647484950";
	    for(int i=0;i < r;i++){
		String t=d.readLine();
		String st[]=t.split(" ");
		int p=Integer.parseInt(st[0]);
		int c=Integer.parseInt(st[1]);
		String card1=card.substring(0,2*(n-c-p+1));
		String card2=card.substring(2*(n-c-p+1),2*(n-p+1));
		String card3=card.substring(2*(n-p+1),2*n);
		card=card1.concat(card3);
		card=card.concat(card2);
	    }
	    String a=card.substring(2*(n-1),2*n);
	    if(a.startsWith("0")) a=a.substring(1);
	    an=an.concat(a+":");
	}
	String ans[]=an.split(":");
	for(int i=0;i < ans.length;i++)System.out.println(ans[i]);
    }
}

文字列操作ですっきりと書きましたね．文字列の連結は，concatを使わなくても「+」で書けるので，

 card=card.substring(0,2*(n-c-p+1))+
     card.substring(2*(n-p+1),2*n)+
     card.substring(2*(n-c-p+1),2*(n-p+1));

と書けますね．nが50までなので

String card="0102030405060708091011121314151617181920212223242526272829303132333435363738394041424344454647484950";

と書けましたが，そうでなければ，

  String card="";
  java.text.DecimalFormat form=new java.text.DecimalFormat("00");
  for(int i=1;i <= n;i++)
    card+=form.format(i);

とやってその場で作ることもできます．

問題B 解答例(1)

import java.util.*;
import java.io.*;

class B {

  final static int RED = 0;
  final static int BLACK = 1;
  final static int ME = 2;

  static int[][] map;
  static int[][] visited;
  static int w = 0;
  static int h = 0;

  public static boolean isVisited(int x, int y) {
    if (0 <= x && x < w && 0 <= y && y < h && visited[x][y] == 0 && map[x][y] == BLACK) {
      return false;
    } else {
      return true;
    }
  }

  public static void search(int x, int y) {
    visited[x][y] = 1;
    if (!isVisited(x-1, y  )) search(x-1,   y);
    if (!isVisited(x+1, y  )) search(x+1,   y);
    if (!isVisited(  x, y+1)) search(  x, y+1);
    if (!isVisited(  x, y-1)) search(  x, y-1);
    return;
  }

  public static void main(String args[]) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    for(;;) {

      String s;
      if ((s=br.readLine()) == null) break;
      String wh[] = s.split(" ");
      w = Integer.parseInt(wh[0]);
      h = Integer.parseInt(wh[1]);
      if (w==0 && h==0) break;
      
      map = new int[w][h];
      visited = new int[w][h];
      
      // data input
      int x=0, y=0;
      for(int j=0; j < h; j++) {
        s = br.readLine();
        for(int i=0; i < w; i++) {
          if(s.charAt(i) == '#') {
            map[i][j] = RED;
          } else if (s.charAt(i) == '@') {
            x = i; y=j;
            map[i][j] = ME;
          } else {
            map[i][j] = BLACK;
          }
          visited[i][j] = 0;
        }
      }

      search(x, y);

      int n = 0;
      for(int j=0; j < h; j++)
        for(int i=0; i < w; i++)
          if (visited[i][j] == 1)
            n++;
      System.out.println(n);

    }
    
  }
}

塗りつぶしの問題です．4近傍を再帰的に呼び出す解法となります．良く書けていますが，以下のよう点は改良可能です．

isVisitedは

  public static boolean isVisited(int x, int y) {
    return !(0 <= x && x < w && 0 <= y && y < h && 
             visited[x][y] == 0 && map[x][y] == BLACK);
  }

のように書ける．

searchを

  public static int search(int x, int y) {
    int count=1;
    visited[x][y] = 1;
    if (!isVisited(x-1, y  )) count+=search(x-1,   y);
    if (!isVisited(x+1, y  )) count+=search(x+1,   y);
    if (!isVisited(  x, y+1)) count+=search(  x, y+1);
    if (!isVisited(  x, y-1)) count+=search(  x, y-1);
    return count;
  }

のように，塗った数を返すようにすると，後で数え直す必要がない．

visited[x][y]を1にする代わりに，map[x][y]をREDにしてしまうと，2つの配列を管理しなくても良い．

問題B 解答例(2)

import java.io.*;

class B{
    public static void main(String[] args)throws IOException{
	BufferedReader d=new BufferedReader(new InputStreamReader(System.in));
	char c;
	String s1;
	for(;;){
	    String is[]=(d.readLine()).split(" ");
	    int W=Integer.parseInt(is[0]);
	    int H=Integer.parseInt(is[1]);
	    if(W>20||H>20||W < 1||H < 1) break;
	    int[][] b=new int[W][H];
	    for(int j=0;j < H;j++){
		s1=d.readLine();
		for(int i=0;i < W;i++) {
		    c=s1.charAt(i);
		    if(c=='@') b[i][j]=1;
		    if(c=='.') b[i][j]=2;
		    if(c=='#') b[i][j]=3;
		}
	    }
	    int count=0;
	    for(;;){
		int lcount=count;
		count=0;
		for(int i=0;i < W;i++){
		    for(int j=0;j < H;j++){
			if(b[i][j]==2){
			    if(i>=1){if(b[i-1][j]==1) b[i][j]=1; }
			    if(i <=W-2){if(b[i+1][j]==1) b[i][j]=1; }
			    if(j>=1){if(b[i][j-1]==1) b[i][j]=1; }
			    if(j <=H-2){if(b[i][j+1]==1) b[i][j]=1; }
			}
		    }
		}
		for(int i=0;i < W;i++){
		    for(int j=0;j < H;j++){
			if(b[i][j]==1) count++;
		    }
		}
		if(lcount==count) break;
	    }
	    System.out.println(count);
	}
    }
}

再帰で呼び出しをせずに，近傍点への伝播を変化がなくなるまで繰り返すプログラムです．効率はさきほどのものよりも良くないのですが，簡潔に書けます．さきほどと同様に，countの計算をb[i][j]を書き換えた時だけやる方法はあります．

問題C 解答例(1)

import java.io.*;
import java.math.*;

class C{
    public static int a,n;
    public static int sub(Bunsu b,int c,int length,int aa){
	int x,y;
	int result=0;
	if(length>=n) return 0;
	b.kiyaku();
	
	if(b.p==1 && length==1) result++;
	for(int i=c;i<=Math.sqrt(a/aa);i++){
	    x=b.p*i-b.q;y=b.q*i;
	    if(x<=0) continue;
	    Bunsu temp=new Bunsu(x,y);
	    temp.kiyaku();
	    if(temp.p==1){
      		if(temp.q>=i && i*temp.q<=a/aa){
		    result++;
		}
		result+=sub(temp,i,length+1,aa*i);
		
	    }
	    else {
		result+=sub(temp,i,length+1,aa*i);
	    }
	}
	return result;
    }
    public static void main(String[] args) throws IOException{
	String input;
	String[] tokens;
	int p,q;
	BufferedReader d=new BufferedReader(new InputStreamReader(System.in));
	
	while(true){
	    input=d.readLine();
	    tokens=input.split(" ");
	    
	    p=Integer.parseInt(tokens[0]);
	    q=Integer.parseInt(tokens[1]);
	    a=Integer.parseInt(tokens[2]);
	    n=Integer.parseInt(tokens[3]);

	    if(p==0 && q==0 && a==0 && n==0){
		break;
	    }
	    
      	    System.out.println(sub(new Bunsu(p,q),1,1,1));
	    //a=200;n=5;
	    // System.out.println(sub(new Bunsu(3,2),2,2,2));
	}
    }
}

class Bunsu{
    public int p,q;
    Bunsu(int pp,int qq){
	p=pp;q=qq;
    }
    public void kiyaku(){
	for(int i=2;i < q+1;){
	    //	    System.out.println(p+" "+q);
	    if(p%i==0 && q%i==0){
		p=p/i;q=q/i;
	    }
	    else{
		i++;
	    }
	}
    }
}

分数を扱うクラスBunsuを作って，すっきりと解いています．既約分数を作るには，ユークリッドの互除法を使って分子と，分母の最大公約数を求めて，両方をそれで割るのが一般的ですが，速度を気にしなければ，上のプログラムの方法でも解けます．

11/16の課題について

11/16の課題

問題A 解答例(1)

コメント

問題A 解答例(2)

コメント

問題B 解答例(1)

コメント

問題B 解答例(2)

コメント

問題C 解答例(1)

コメント