Hatena::Grouptopcoder

tochukasoの日記

2014-07-23

SRM628 Div2

| 20:58

1完

easy

概要

・チェス盤とビショップの駒が与えられる。

・ビショップの現在位置の座標と移動したい場所の座標が与えられる。

・移動出来ない場合は-1,移動できる場合は移動に掛る回数を返却する。

解答方法

・x軸の距離とy軸の距離が等しい場合、1回で移動できる。

・x軸の距離とy軸の距離の偶奇が等しくない場合、移動できない。

 等しい場合、2回で移動できる。

	public int howManyMoves(int r1, int c1, int r2, int c2)
	{
	    
	    int p1 = Math.abs(r1 - r2);
	    int p2 = Math.abs(c1 - c2);
	    
	    if(p1 == 0 && p2 == 0) return 0;
	    
	    if(p1 == p2) {
	        return 1;
	    } else if (p1 % 2 == p2 % 2) {
	        return 2;
	    } 
	    return -1;
        }

medium

概要

・(,),{,},[,],Xで構成される文字列が与えられる。

・各カッコの同期が取れているかを操作する。また、Xは任意の文字に置き換えることが出来る。

XMLファイルの様に入れ子構造は許容しないものとする。

解答方法

・各種カッコが連続しているものを除外する。

・Xをそれぞれ6種類の文字に置き換えて、上記の処理を回す。

    private boolean dfs(String s) {
        while(s.contains("[]") || s.contains("{}") || s.contains("()")) {
            s = s.replaceAll("\\(\\)", "");
            s = s.replaceAll("\\[\\]", "");
            s = s.replaceAll("\\{\\}", "");
        }
        
        if(s.length() == 0) {
            return true;
        } else {
            if(s.contains("X")) {
                return dfs(s.replaceFirst("X", "[")) ||
                        dfs(s.replaceFirst("X", "{")) ||
                        dfs(s.replaceFirst("X", "(")) ||
                        dfs(s.replaceFirst("X", "]")) ||
                        dfs(s.replaceFirst("X", "}")) ||
                        dfs(s.replaceFirst("X", ")")) ;
                
            }
        }
        
        return false;
    }
    
	public String ifPossible(String expression)
	{
	    boolean b = dfs(expression);
	    return  b ? "possible" : "impossible";
        }

実際には、easyの問題は幅優先探索を使用して、

何回で移動出来るか試してたので、実装にちょっと時間かかりましたorz

medium問題は、Xのうまい取扱い方法が分からなくて

実装ミスりました。Xが5回以内しか出現しないという緩めの制約だったので、

全通り試せばいいとは思ってたんですが・・・・

918⇒891

グレーに落ちました。

8月からは月一ぐらいしか参加できなそうなのになぁ・・・・

2014-07-12

SRM627

| 00:31

easy

 ・棒の長さを表す数列が与えられる。

 ・同一の長さの棒を4本使用して正方形を作る。

 ・何個の正方形を作ることが出来るかを返却する。

 ・同一の棒の長さをカウントして、4で割った商の和を求める。

	public int howManySquares(int[] sticks)
	{
	    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
	    for (int i = 0; i < sticks.length; i++) {
	        int cnt = 0;
	        if(map.containsKey(sticks[i])) {
	            cnt = map.get(sticks[i]);
	        }
	        cnt ++;
            
	        map.put(sticks[i], cnt);
	            
        }
	    int res = 0;
	    for (int i : map.values()) {
	        res += i / 4;
        }
	    return res;
	}

medium

 kawai Editの問題?

 問題文がうまく開かなかったので手をつけず。

hard

 ・数列が与えらる

 ・数列の部分数列を数回反転させることが出来る。

  ・反転させるエリアは重複を許さない。

 ・その後、バブルソートを行う。

  バブルソートでスワップする回数が最も少なくなるように反転させた場合、

  スワップ処理を何回行う必要があるか。

 DFSで解いたけど、TLEで爆死

 計算量がO(N^4K)ぐらいになった。N,K共に最大50なんで、50^5 = 3億1千万

 よく考えるとちょっと枝刈すれば間に合いそうだな・・・ぐぬぬ・・・

 チャレンジモードも一問失敗。

 ただ、その解答はチャレンジ成功されてたんで、Qが問題だった。

1016⇒920

 

2014-06-29

SRM626

| 22:52

・Easy

 数値型の配列が与えられる。

 配列のサブ配列の総和を求める。

 例.[1,2,3]の場合、1, 2, 3, 1 + 2, 2 + 3, 1 + 2 + 3の合計 = 20となる

 選択する文字の長さ、開始位置、N文字分で3重ループして計算する

	public int findSum(int[] array)
	{
	    int sum = 0;
	    int N = array.length;
	    for (int i = 1; i <= N; i++) {
	        for (int j = 0; j + i<= N; j++) {
	            for(int k = 0; k < i; k++) {
	                sum += array[j+k];
	            }
	        }
	    }
	    return sum;
	}

 データの制約が緩い(配列の要素数は50)にも関わらず、

 時間がかかると思って効率的な解法を探して小一時間使った。

 結局3重ループの解法でいいと気付いた。

 なんという時間の無駄。

Medium

 2人が互いにサイコロを振りあう。

 サイコロはN面体。

 Aが勝つことは決まっている。

 Aの目の期待値を答える。

 Bの目を上から順番に見ていって、AがBの目を越える事がある場合に、

 総和と回数を足していく。(Bの目に対してAが勝つ場合にカウントする)

 最後に総和/回数を行う

	public double getExpectation(int a, int b)
	{
		double res = 0;
		
	    int sumCount = 0;
	    int sum = 0;
	    for (int i = b; i > 0; i --) {
	        if (a > i) {
	            int tmp = a - i;
	            sumCount += tmp;
	            for (int j = 0; j < tmp; j++) {
	                sum += a - j;
	            }
	        }
	    }
		
		
		return (double) sum /  sumCount;
	}

C問題。

時間なくて解けなかった。

時間あっても、解けないかな。

課題として、easy問題とmedium問題を確実に素早く解く力が必要

毎日必ず、Div2のeasyとmediumを解こう。

1072 ⇒ 1016

2014-06-21

SRM625

| 16:46

SRM625 Div2参戦

Easy問題

a*b+c=x

xが与えられるので、a,b,cの値を返却しろという問題

ただし、a,b,cに0,1を使用してはならない。

a,b,c,xに使用できる値の制約が厳しいので

何も考えずにシミュレーションすればOK.

	public int[] makeExpression(int y)
	{

        int res[] = new int[3];

        for (int i = 1000; i >= -1000; i--) {
            if (i == 0 || i == 1) {
                continue;
            }
            
            int tmp = y - i;
            for (int j = 2; j < 10; j++) {
                for (int j2 = j; j2 < 100; j2++) {
                    if(tmp == j * j2) {
                        res[0] = j;
                        res[1] = j2;
                        res[2] = i;
                        return res;
                    }
                }
            }
        }
	    
	    return res;
	}

ちなみにこれは修正版です。

テストの際は間違えてました。

Medium問題

intの配列と一回に加算できる数値が与えられる。

加算は何回でも出来る。

intの配列にkを加えて、1,2,3・・・・n(配列の長さ)にすることが出来るかを判定する。

1,2,3・・・・・nの数値を達成することが出来たかを管理する

booleanの配列を持って、

オリジナルのint配列と照らし合わせる。

既にその数値が達成されている場合にKを加算する。


	public String canItBeDone(int k, int[] A)
	{
	    String OK = "POSSIBLE";
	    String NOT = "IMPOSSIBLE";
	    boolean[] res = new boolean[A.length + 1];
	    
	    for (int j = 0; j < A.length; j++) {
	        int tmp = 0;
	        int i = A[j];
	        while(i + tmp * k <= A.length) {
    	        if (!res[i + tmp * k]) {
    	            res[i + tmp * k] = true;
    	            break;
    	        }
    	        tmp++;
	        }
	    }
	    
	    for (int i = 1; i <= A.length; i++) {
	        if (!res[i]) {
	            return NOT;
	        }
	    }
	    return OK;
	}

Hard問題

嘘つきと正直者が輪になって座っている。

それぞれの人に右隣の人が嘘つき(L)か正直者(H)かを尋ねる。

嘘つきは常に嘘を、正直者は常に正直に答える。

ただし、質問されていない人(?)もいる。

最小の嘘つきの人数を答える。

ただし、ゲームが成立していない場合?、-1を返却する。

LLLの場合、一人目が嘘つきでも正直者でも矛盾が発生する。

    char[] array = null;
    boolean isLast = false;
    int sum = -1;
	public int minimumLiars(String answers)
	{

	    array = answers.toCharArray();
	    dfs(0, 0, false);
	    isLast = true;
	    dfs(0, 0, true ); 
        return sum;
	}
    void dfs(int x, int lier, boolean isHonest) {
        for (int i = x; i < array.length; i++) {
            if (isHonest) {
                if (array[i] == 'L') {
                    lier++;
                    isHonest = false;
                } else if (array[i] == 'H') {
                } else {
                    if (i + 1 < array.length && array[i + 1] == '?') {
                        
                    } else {
                        dfs(i + 1, lier, true);
                        dfs(i + 1, lier + 1, false);
                        return;
                    }
                    
                }
            } else {
                if (array[i] == 'L') {
                    isHonest = true;
                } else if (array[i] == 'H') {
                    lier++;
                } else {
                    if (i + 1 < array.length && array[i + 1] == '?') {
                        
                    } else {
                    dfs(i + 1, lier, true);
                    dfs(i + 1, lier + 1, false);
                    return;
                    } 
                }
            }
        }
        
        if (isHonest == isLast) {
            if (sum == -1) {
                sum = 10000;
            }
            sum = Math.min(sum, lier);
            return ;
        }
        
    }

誤答。

上の解答はプラクティスモードで通したものです。

解答方法はテスト中に思いついたものと同じなんだけど、

?が50この時にO(2^50)で間に合わないと思ったけど、

?が連続した場合は分岐しなくていいから、maxでもO(2^25)で

間に合うなぁ。残念。

Mediumのみ正解だったけど、

チャレンジモードで75点稼いで

レートアップに成功。

1054⇒1072

2014-06-12

SRM624 Div2

| 02:29

・250

ダンススクールに通いたい苦学生の話

コストの低い順にソートして、

選択したいコース分コストを計算する。

	public int minimum(int K, int[] danceCost)
	{
	    int sum = 0;
	    Arrays.sort(danceCost);
	    for (int i = 0 ;i < K; i++) {
	        sum+=danceCost[i];
	        if (i == danceCost.length - 1) {
	            break;
	        }
	    }
	    
	    return sum;
	    
	}

・500

ビルからビルへジャンプする?人の話

同じ高さの階にしか飛べないのでビルに足場を増やしてあげる。

追加する階層の量を返却する。

	public int minimum(int M, int[] heights)
	{
		if (M == 1) return 0;
		int N = heights.length;
		int min = Integer.MAX_VALUE;
		Arrays.sort(heights);
		for (int i = N - 1; i > 0 ; i--) {
		    for (int j = i; j - M + 1 >= 0; j--) {
		        int sum = 0;
		        int k = M - 1;
		        for (;k > 0 && j - k >= 0; k--) {
		            sum += heights[i] - heights[j - k];
		        }
		        if (k == 0) {
	                min = Math.min(min, sum);
		        }
 		    }
		}
	    return min;
	}

・1000

N角系の辺と対角線をプレイヤー同士が選択しあって、

先に選択できる線が無くなった方が負け。

Nが与えられた場合にどちらが勝つかを予想する。

選択した線と交わる線、隣接する線は選択出来なくなる。

・・・・・解答方法不明。

1113⇒1054

1000の問題が解けないと駄目だったのかorz