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}の長さループなので余裕です．

■コード

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4.   
5. public class AfraidOfEven{  
6.  public int[] restoreProgression(int[] seq){  
7.   int[] ret=new int[seq.length];  
8.   int[] arr=new int[seq.length];  
9.   String s1=null;  
10.   for(long a0=seq[0];a0<=Integer.MAX_VALUE;a0*=2){  
11.    arr[0]=(int)a0;  
12.    for(long a1=seq[1];a1<=Integer.MAX_VALUE;a1*=2){  
13.     arr[1]=(int)a1;  
14.     long d=a1-a0;  
15.     long a=a1+d;  
16.     boolean f=true;  
17.     for(int i=2;i<seq.length;i++){  
18.      arr[i]=(int)a;  
19.      if(a<0) f=false;  
20.      if(a%seq[i]!=0) f=false;  
21.      long k=a/seq[i];  
22.      if((k&(k-1))!=0) f=false;  
23.      a+=d;  
24.     }  
25.     if(f){  
26.      String s2=Arrays.toString(arr);  
27.      if(s1==null||s2.length()<s1.length()||(s2.length()==s1.length()&&s2.compareTo(s1)<0)){  
28.       System.arraycopy(arr,0,ret,0,seq.length);  
29.       s1=s2;  
30.      }  
31.     }  
32.    }  
33.   }  
34.   return ret;  
35.  }  
36. }  

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;
 }
}