Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-11SRM377,SRM378,SRM379 (Practice)

SRM 378 SolvePolynomial

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

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

  • 方針を検討
    • 2分探索?
      • いや、多分無理・・・
    • 解の候補を幾つか出してそれを試していけばいいのかなぁ
    • 分からん・・・

その後

  • 他の人のコードを読む。
    • なんか約数をとって候補としてる
      • なぜ?
    • あ、そっか
      • (多項式) = (x-a1)(x-a2)(x-a3) .... (x-an) と因数分解できるとする。
      • すると一番次数の小さい項は a1 * a2 * ... * an になってるはずだから・・・ということか
    • 定数項が0だったら候補を0に追加
    • 一番次数の小さい項xについて、x % i == 0 な i に対し i, -i, x/i, -x/i を候補に追加
  • 求めた候補に対して式を実際に計算し、0になるかどうか確かめる。
    • BigInteger使えばいいのかな・・・TLEしそうな気もするが
      • やっぱりダメだった
    • 他の人のコードを読むと、でかい素数のMODを2つぐらい取って0だったらOKとしてる
      • そんな適当でいいのか・・・?
  • そう書いたら通った。腑に落ちない・・・
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SolvePolynomial {

	long MOD = 1000000009;
	long MOD2 = 1000000007;
	
	public boolean isok(long x, int[] a) {
		int len = a.length;
		long l = 0;
		for (int i = len - 1 ; i >= 0 ; i--) {
			l = (l * x + a[i]) % MOD;
		}
		if (l == 0) {
			for (int i = len - 1 ; i >= 0 ; i--) {
				l = (l * x + a[i]) % MOD2;
			}
			if (l == 0) {
				return true;
			}
		}
		return false;
	}
	
	public int[] integerRoots(int[] X, int[] Y, int n) {
		int[] a = new int[n+1];
		int lx = X.length;
		int ly = Y.length;
		for (int i = 0 ; i <= n ; i++) {
			int p = i % lx;
			int q = (i + Y[i % ly]) % lx;
			a[i] = X[p];
			X[p] = X[q];
			X[q] = a[i];
		}
		
		
		Set<Integer> candidate = new HashSet<Integer>();
		if (a[0] == 0) {
			candidate.add(0);
		}
		for (int i = 0 ; i <= n ; i++) {
			if (a[i] != 0) {
				int ch = Math.abs(a[i]);
				for (int j = 1 ; j * j <= ch ; j++) {
					if (ch % j == 0) {
						candidate.add(j);
						candidate.add(ch/j);
						candidate.add(-j);
						candidate.add(-ch/j);						
					}
				}
				break;
			}
		}

		System.out.println(candidate.size());
		
		
		List<Integer> ok = new ArrayList<Integer>();
		for (int c : candidate) {
			if (isok(c, a)) {
				ok.add(c);
			}
		}
		if (ok.size() == 0) {
			return new int[]{};
		} else {
			int[] ans = new int[ok.size()];
			for (int i = 0 ; i < ok.size() ; i++) {
				ans[i] = ok.get(i);
			}
			Arrays.sort(ans);
			return ans;
		}
	}
}

utmathutmath2012/03/26 13:34SRM378 Medium 落としておきました。

hama_DUhama_DU2012/03/26 17:27うっ、嘘解法でしたからね・・・
どんなケースで落としたのか教えていただけるとうれしいです。

utmathutmath2012/03/27 15:563552*x^25 + 730*x^20 + 886*x^15 + 68*x^10 + 160*x^5 + 62*x + 4 です。x = 4 を代入すると、4 * (10^9+9) * (10^9 +7) になり、どちらで mod をとっても 0 になってしまいます。

hama_DUhama_DU2012/03/29 16:19なるほど、ありがとうございます。
というかこんなケースよく見つけましたね・・・