Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-15SRM399 (Practice)

SRM 399 AvoidingProduct

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

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


コーディングフェーズ

  • とりあえず {x, y, z} = {1〜n+1} での全探索を実装(←ここでもう間違ってる)
    • zのループに入る前に x * y が (n + 差の絶対値) を超えてたら探索しない(continue)という謎枝刈りをする
    • 配列aがたくさん埋まってたら間に合わないかもという考えつつも気にせず提出

  • 500を提出し250に戻ってくる
    • ちょっと気になったので配列aを1〜50で全埋めした場合をテスト
      • ローカルで1.7s。これはTLEする!
    • よく考えると枝刈りのとこcontinueじゃなくてbreakでいいよね なにやってんだ
    • 再提出

システムテスト後

  • あっさり落ちる。なんで!?
    • {1〜n+1}ではなく、最大の{1〜1001}で回すべき。それでも間に合うんだから
      • 念のため{1〜1501}で再実装。通した

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class AvoidingProduct {

	public int[] getTriple(int[] a, int n) {
		int minx = 9999;
		int miny = 9999;
		int minz = 9999;
		int mindist = Integer.MAX_VALUE / 4;
		
		
		boolean[] ok = new boolean[1501];
		Arrays.fill(ok, true);
		for (int x : a) {
			ok[x] = false;
		}

		
		List<Integer> il = new ArrayList<Integer>();
		for (int i = 1 ; i <= 1500 ; i++) {
			if (ok[i]) {
				il.add(i);
			}
		}
		
		for (int x : il) {
			for (int y : il) {
				for (int z : il) {
					int xyz = x * y * z;
					int val = Math.abs(xyz - n);
					if (xyz > n + mindist * 2) {
						break;
					}
					
					if (val < mindist) {
						mindist = val;
						minx = x;
						miny = y;
						minz = z;
					} else if (val == mindist) {
						if (minx > x) {
							minx = x;
							miny = y;
							minz = z;
						} else if (minx == x) {
							if (miny > y) {
								miny = y;
								minz = z;
							} else if (miny == y) {
								if (minz > z) {
									minz = z;
								}
							}
						}
					}
				}
			}
		}
		return new int[]{minx, miny, minz};
	}
}