Hatena::Grouptopcoder

tochukasoの日記

 | 

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

 |