TopCoder 練習

AfraidOfEven(Member SRM 485 Div1 Easy)

■問題
Sashaはある等差数列{a_i}を黒板に書いた．偶数が嫌いなPashaは，数列上の各数a_iを偶数でなくなるまで2で割り続け，b_iとした．Pashaによって書き換えられた数列{b_i}から元の数列{a_i}を求めよ．候補が複数存在する場合は，辞書式順に最も早いものを答えとせよ．

■解法
1. a₀=b₀2^m，a₁=b₁2ⁿと決定する．
2. 公差d=a₁-a₀が求まるので，a_i>=2が実現可能かを調べる．具体的には，a_i=a₀+di=b_i2^kであるので，(a₀+di)/b_iが2のべき乗となるかどうか．
3. 全候補の内，辞書式順に最も早いものを答えとする．

計算時間は，a₀，a₁それぞれの決定に高々32ループ，実現可能かを調べるのに{a_i}の長さループなので余裕です．

■コード

import java.util.*;
import java.lang.*;
import java.math.*;

public class AfraidOfEven{
 public int[] restoreProgression(int[] seq){
  int[] ret=new int[seq.length];
  int[] arr=new int[seq.length];
  String s1=null;
  for(long a0=seq[0];a0<=Integer.MAX_VALUE;a0*=2){
   arr[0]=(int)a0;
   for(long a1=seq[1];a1<=Integer.MAX_VALUE;a1*=2){
    arr[1]=(int)a1;
    long d=a1-a0;
    long a=a1+d;
    boolean f=true;
    for(int i=2;i<seq.length;i++){
     arr[i]=(int)a;
     if(a<0) f=false;
     if(a%seq[i]!=0) f=false;
     long k=a/seq[i];
     if((k&(k-1))!=0) f=false;
     a+=d;
    }
    if(f){
     String s2=Arrays.toString(arr);
     if(s1==null||s2.length()<s1.length()||(s2.length()==s1.length()&&s2.compareTo(s1)<0)){
      System.arraycopy(arr,0,ret,0,seq.length);
      s1=s2;
     }
    }
   }
  }
  return ret;
 }
}