Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-07SRM482(DIV1)

LockersDivOne

|  LockersDivOne - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  LockersDivOne - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=11110

普通に探索すると間に合わないけど、

配列に「次の空いてるドア」を覚えさせとけば大丈夫。

学校の課題で、Cでリンクリスト実装したときのことを思い出しながら書いた。


public class LockersDivOne {

	public int lastOpened(int N) {
		int l[] = new int[N+1];
		for (int i = 0 ; i <= N ; i++) {
			l[i] = i+1;
		}
		int closed = N;
		int opened = 1;
		int times = 1;
		while (closed > 0) {
			int count = 0;
			int before = 0;
			int index = l[0];
			while (index <= N) {
				if (--count < 0) {
					l[before] = l[index];
					opened = index;
					count = times;
					closed--;
				}
				before = index;
				index = l[index];
			}
			times++;
		}
		return opened;
	}
}