TopCoder Member SRM 482

Member SRM 482(9/16 0:00~2:00)

先週に引き続き．

■LockersDivOne(DIV1 Easy)

□Problem
1~N(1≦N≦2000000)まで番号付けされたロッカーがある．全てのロッカーは，閉じられている．
DaveとEarlは，番号の昇順にロッカーを見ていき，最初に見つけた閉じられているロッカーを開ける．その後，閉じられているロッカーを2個見つける度にそのロッカーを開けていく．番号Nまで戻ったら，はじめに戻り，2個飛ばしを3個飛ばしにし，同様のことをする．以降，4,5,6,…とロッカーを飛ばす個数を増やしていく．最後に残ったロッカーの番号は何か．

最初はLinkedListで実装しましたが，最大ケースを試したところ，メモリが足りないと言われかなり焦りました．しょうが無いので配列による実装に落ち着きましたが，最初から配列による実装にしていれば，もっと早く提出出来たと思います．ただ，今回は，Resubmitを一度もしないで済んだので，104.04pでした．

□Code

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

public class LockersDivOne{
 public int lastOpened(int N){
  int[] a=new int[10000];
  int[] b=new int[N];
  for(int i=0;i<N;i++){
   for(int k=2;k<a.length;k++){
    if(a[k]==0){
     a[k]++;
     b[i]=k;
     // System.out.println("i="+i+", k="+k);
     break;
    }else{
     a[k]++;
    }
    if(a[k]==k)
     a[k]=0;
   }
  }
  int ret=0;
  for(int i=0;i<N;i++){
   if(b[i]>b[ret])
    ret=i;
   //if(b[i]<2)
   // System.out.println("Error!");
  }
  //System.out.println(Arrays.toString(b));
  //System.out.println(Arrays.toString(a));
  return ret+1;
 }
}

■Challenge
は，今回やりませんでした．

■Result
○×× 0 -0
104.04p

■Rating
1339 -> 1372
やっとhighestを更新しました．今年中には1500まで上げたいと思います．