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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4.   
5. public class LockersDivOne{  
6.  public int lastOpened(int N){  
7.   int[] a=new int[10000];  
8.   int[] b=new int[N];  
9.   for(int i=0;i<N;i++){  
10.    for(int k=2;k<a.length;k++){  
11.     if(a[k]==0){  
12.      a[k]++;  
13.      b[i]=k;  
14.      // System.out.println("i="+i+", k="+k);  
15.      break;  
16.     }else{  
17.      a[k]++;  
18.     }  
19.     if(a[k]==k)  
20.      a[k]=0;  
21.    }  
22.   }  
23.   int ret=0;  
24.   for(int i=0;i<N;i++){  
25.    if(b[i]>b[ret])  
26.     ret=i;  
27.    //if(b[i]<2)  
28.    // System.out.println("Error!");  
29.   }  
30.   //System.out.println(Arrays.toString(b));  
31.   //System.out.println(Arrays.toString(a));  
32.   return ret+1;  
33.  }  
34. }  

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まで上げたいと思います．