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月からは月一ぐらいしか参加できなそうなのになぁ・・・・

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/java123java123/20140723
 |