SRM359

この問題セットで1問も解けないというのはかなりひどいな．いろいろと反省する必要がある．

250

{"Canada", "France", "Germany", "Italy", "Japan", "Russia", "United Kingdom", "United States"}のような文字列が与えられるので

C                    R                  
-------------------  -------------------
  Canada               Russia           
F                    U                  
-------------------  -------------------
  France               United Kingdom   
G                      United States    
-------------------                     
  Germany                               
I                                       
-------------------                     
  Italy                                 
J                                       
-------------------                     
  Japan                                 

のように二段組みに整形して，出せ*1というだけの問題，細かいルールはすべて問題文に与えられている．左と右とに分ける処理を1つの配列でやろうとして，いろいろとパニクったせいで結局解けなかった．

冷静に考えると最初に左右別々に列として取ってあとで右側を左側につけるという2パスでやればそんなに難しくない

import java.util.*;
public class Glossary {
    public String[] buildGlossary(String[] items) {
    	Arrays.sort(items,new Comp());
    	int count[] = new int[26];
    	for(String s:items){
    		char f = s.charAt(0);
    		count[Character.toUpperCase(f) - 'A']++;
    	}
    	int left = 0;
    	int right = 0;
    	for(char c ='A';c<='Z';c++){
    		if(count[c - 'A']==0)continue;
    		if(c<='M')left += count[c - 'A'] + 2;
    		else right += count[c - 'A'] + 2;
    	}
    	int rowNum = Math.max(left, right);
    	String[] tmp = new String[left+right];
        String[] res = new String[rowNum];
        int counter = 0;
        int itemIndex = 0;
        for(char c = 'A';c<='Z';c++){
        	if(count[c - 'A']==0)continue;
    		tmp[counter++] = c+space(18);
    		tmp[counter++] = rep('-',19);
        	for(int i=0;i<count[c - 'A'];i++){
        		String str = items[itemIndex++];
        		tmp[counter++] =space(2)+ str + space(17 - str.length());
        	}
        }
        for(int i=0;i<rowNum;i++){
        	if(i<left)res[i] = tmp[i];
        	else res[i] = space(19);
        	res[i] +=space(2);
        	if(i<right)res[i] += tmp[left+i];
        	else res[i] += space(19);
        }
        return res;
    }
	private String space(int num){return rep(' ',num);}
	private String rep(char c,int num){
		String res = "";
		for(int i=1;i<=num;i++)res += c;
		return res;
	}
	static class Comp implements Comparator<String>{
		public int compare(String o1, String o2) {
			return o1.compareToIgnoreCase(o2);
		}
	}
}

500

なんでこれできてないかな，問題は複数の点が与えられて，その上の任意の一つに人がいたときにそこから水平方向に飛んで行って点上にあるコインを取ってた時に取れる最大のコインの枚数を求めよというもの．最大速度と重力加速度は与えられる．

高さの高い順に点をソートして，その点から次の点にいけるときに枝を張ることを考えると高さ順にソートするというのがトポロジカルソートするのと等価になり，そういう配列を左からなめていけば各点に着いたときにとることのできる最大のコインの数が求まるので答えはその中で最大のものとなる．ある点から次の点に行けるというのは簡単な算数で求まる．

import java.util.*;
public class PlatformJumper {
	class Point implements Comparable<Point>{
		int x,y,val;
		Point(String str){
			Scanner sc = new Scanner(str);
			x = sc.nextInt();
			y = sc.nextInt();
			val = sc.nextInt();
		}
		public int compareTo(Point o) {
			return o.y - y;
		}
		// t^2 = 2 * dy / g
		// if "this -> p" can reach v * t >=  dx
		public boolean canGo(Point p,long  v, long g){
			if(y<=p.y)return false;
			long dy  = y - p.y;
			long dx = Math.abs(x - p.x);
			return g*dx * dx <= 2 * v * v * dy;
 		}
	}
    public int maxCoins(String[] platforms, int v, int g) {
        Point ps[] = new Point[platforms.length];
        for(int i=0;i<ps.length;i++)
        	ps[i] = new Point(platforms[i]);
        Arrays.sort(ps);
        int memo[] = new int[ps.length];
        for(int i=0;i<memo.length;i++)memo[i] = ps[i].val;
        for(int i=0;i<ps.length;i++)
        	for(int j=i+1;j<ps.length;j++)
        		if(ps[i].canGo(ps[j], v, g))
        			memo[j] = Math.max(memo[j], memo[i] + ps[j].val);
        int res = 0;
        for(int i:memo)res = Math.max(res, i);
        return res;
    }
}

*1:正確には返り値として整形した文字列の配列を返す