昨日SRMのメールが届いてて、「あれ？明日？」って思ったらMemberだった。
けど、レートに影響あるんだ。これどういう扱いなんだろうね。

Easy SpidersOnTheGrid

クモ問題。書くだけ。

205.09

Midium EasySequence

無限配列の部分配列(B[])が与えられて、そのindexを返せという問題。
無限配列の定義は、、、

• A[0], A[1], …, A[N-1] are given;
• A[i]=(A[i-1]+A[i-2]+…+A[i-N])%10 for all i>=N;

素直に解けば解けそう！と思ったので、わりかしすぐにコード書いてみた。
部分配列の頭の場所さえわかれば良いので、
indexと必要な長さの分だけ（=Math.max(A.length,B.length)）配列を覚えておくことにした。

多分、方針は間違ってない。

    public int find(int[] A, int[] B) {
    	LinkedList<Integer> substring = new LinkedList<Integer>();
    	final int N = A.length;
    	final int M = B.length;
    	int index = 0;

    	// substring.size() <= M
    	while (true) {
    		if (index >= N) {
	    		int sum = 0;
	    		for (int i = 1; i <= N; i++) {
	    			// 後ろからN個分足す。
	    			sum += substring.get(substring.size() - i);
				}
	    		substring.add(sum % 10);

    		} else {
    			substring.add(A[index]);
    		}

    		// メモリ気にする(max=50)
    		while (substring.size() > M && substring.size() > N){
    			substring.removeFirst();
    		}

    		if (substring.size() >= M) {
    			boolean res = true;
    			// M個比較する
    			for (int i = 1; i <= M; i++) {
					if (!substring.get(substring.size() - i).equals(B[M - i])) res = false;
				}
    			if (res) break;
    		}

    		if (substring.size() >= N && index >= N && index >= M) {
				boolean failed = true;
				// N個比較する
				for (int i = 1; i <= N; i++) {
					if (!substring.get(substring.size() - i).equals(A[N - i])) failed = false;
				}
				if (failed) return -1;
    		}

//    		System.out.println(index + "..." + substring.toString());

    		index++;
    	}

    	return index-M+1;
    }

ここまでは素直に書けたんだけど、終了条件が分からない。
無限配列だし、、、Integer.MAX_VALUEまでやるわけにはいかないし、、、
で、悩んだ末にA[]がまた出てきたら終わることにした。けど、通るわけなひよね。
とゆか送らなかった。

0.0

Challenge Phase

自分がMidiumの終端条件で悩んでいたので、それで攻めた。
index == A.length ^ 2で終わりにしてる人がいたので、それはないだろうと思い、
A.length = 3 で、部分配列を12くらいにして送ってみたら落ちた。

50.0

Total 255.09

しょっぱいけど、250ってある意味１枚目の壁だよね。
821(+113)
早くこの泥沼から抜け出したい。