1012 - ヨゼフ?時間超過 2011/09/24

1012 -- Joseph
Javaです。 なんとかそれっぽい答えがでるようになって、submitすると時間超過....
グーグルさんに尋ねて調べると、あらかじめ計算させてその値をつかっていたりしてるようでした。
とりあえずkが10よりうえのものは計算済みのものを使っています。

package p1012; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { static class P { boolean dead = false; boolean goodP = false; public P(boolean goodP) { this.goodP = goodP; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (true) { int k = scanner.nextInt(); if (k == 0) break; List<P> list = new ArrayList<Main.P>(); for (int i = 0; i < k; i++) { list.add(new P(true)); } for (int i = k; i < k * 2; i++) { list.add(new P(false)); } int[] is = { 0, 0, 0, 0, 0, 0, 0, 0, 1740, 93313, 459901, 1358657, 2504881 }; if (10 <= k) { System.out.println(is[k - 1]); continue; } int m = 0; A: for (m = 2; m < 100000000; m += 1) { int pos = 0; List<P> list2 = new ArrayList<Main.P>(list); int deadcount = k * 2; while (deadcount != k) { pos += m - 1; if (list2.size() <= pos) { pos = pos % list2.size(); } if (pos < k) continue A; list2.remove(pos); deadcount--; } break A; } System.out.println(m); } } }

: