Pku JudgeOnline

ゼミが休みになったので少し解く．とりあえず順位をひとつあげる．とりあえず100位と34問差があるので当分2ページ目には載れそうだが，あと100解いてもまだ2ページ目なんだよな．

解いた問題は以上

• http://acm.pku.edu.cn/JudgeOnline/problem?id=3117
• http://acm.pku.edu.cn/JudgeOnline/problem?id=3186
• http://acm.pku.edu.cn/JudgeOnline/problem?id=3191
• http://acm.pku.edu.cn/JudgeOnline/problem?id=2868

ソースは以下の通り

Pku3117

いろいろ情報が入っているけど，単なる鶴亀算．

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int t = sc.nextInt();
			int n = sc.nextInt();
			if(t==0&&n==0)break;
			int sum = 0;
			for(int i=0;i<t;i++){
				sc.next();
				sum+=sc.nextInt();
			}
			System.out.println(3*n-sum);
		}
	}
}

Pku3186

DP

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int arr[] = new int[n];
		for(int i=0;i<n;i++){
			arr[i] = sc.nextInt();
		}
		int memo[][] = new int[n+1][n+1];
		for(int i=0;i<memo.length;i++){
			Arrays.fill(memo[i], Integer.MIN_VALUE);
		}
		memo[0][0] = 0;
		int max = Integer.MIN_VALUE;
		for(int a=1;a<=n;a++){
			for(int l=0;l<=a;l++){
				int r = a - l;
				if(l!=0)memo[l][r] = Math.max(memo[l][r], memo[l-1][r] + arr[l-1]*a);
				if(r!=0)memo[l][r] = Math.max(memo[l][r], memo[l][r-1] + arr[n-r]*a);
				max = Math.max(max, memo[l][r]);
			}
		}
		System.out.println(max);
	}
}

Pku3191

10進数を-2進数に変換しろという問題，再帰の部分がうまいこと一つにまとまらない．あとmainの部分とfの部分の統一がとれていないから余計な0を取り除く処理が必要になっている．

import java.util.*;

public class Main {
	static void f(long val,long base,List<Integer> lst){
		if(base==0)return ;
		if(base>0 && val >(base -1)/3){
			lst.add(1);
			f(val-base,base/(-2),lst);
		}else if(base<0 && -val >(-base-2)/3){
			lst.add(1);
			f(val-base,base/(-2),lst);			
		}else{
			lst.add(0);
			f(val,base/(-2),lst);
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long val = sc.nextLong();
		List<Integer> lst = new LinkedList<Integer>();
		for(long base = 1;;base*=-2){
			if(val*base>=0 && base-val>=0){
				f(val,base,lst);
				boolean flag = lst.size()==1?true:false;
				for(int i:lst){
					if(i==1)flag = true;
					if(flag)System.out.print(i);
				}
				System.out.println();
				break;
			}
		}
	}
}

Pku2868

こういう群数列っぽい問題はよく出るので，体系的に解く方法をもっておきたいんだけど，なんかその場限りで解いている気がする．

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			int q= sc.nextInt();
			if(n==0 && q==0)break;
			String arr[] = new String[n];
			for(int i=0;i<n;i++)arr[i] = sc.next();
			for(int i=0;i<q;i++){
				long k = sc.nextLong();
				int index = sol(n,k);
				System.out.println(arr[index]);
			}
			System.out.println();
		}
	}	
	static int sol2(long n,long k,long index){
		long a = index/k;
		long i = k - (index - a * k) -1;
		for(long j = 0; j < i;j++){
			a /= n;
		}
		return (int)(a % n);
	}
	static int sol(int n,long k){
		if(n==1)return 0;
		long base = n;
		long sum = 0;
		for(int i = 1;;i++){
			sum += base*i ;
			if(sum>=k){
				long index = k-(sum-base*i);
				return sol2(n,i,index -1);
			}
			base *= n;
		}
	}
}