TopCoder SRM410 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について意訳で説明する。

最新のマイクロコントローラーをできるだけ安くするため、ACMEウィジェットカンパニーはとても単純なキャッシュのデザインを行った。プロセッサはnバイトからなる遅いメモリシステムにつながっており、そのnバイトは0～n-1と値をつけられている。速いアクセスが可能なキャッシュは一度にkバイト保持することができる。キャッシュはベースアドレス（後程説明する）を持っており、base～base+k-1まで値がついたバイトのコピーを保持する。プログラムが1バイトを読み込んだとき、キャッシュコントローラーは以下のアルゴリズムを実行する。

• 現在のベースアドレスと新しいベースアドレスが最小になるよう、要求されたバイトを含む新しいkバイトの範囲を見つける。もし、要求されたバイトがキャッシュの中にあれば、ベースアドレスの変更は必要ない。
• 新しい範囲にあるバイトの内容をメモリシステムから読み込み、キャッシュを新しい内容に更新する。古いメモリ範囲で、新しいメモリ範囲に含まれない範囲は捨てるものとする。
• プログラムに要求されたバイトを返す。

プログラムのパフォーマンスを分析するために、メモリシステムから何バイトが読まれたかを知りたい。プログラムが読むバイトはaddresses[]という整数型配列で与えられる。これはメモリから読みだされる順序で値が格納されている。また、プログラムが始まるとき、ベースアドレスは0にあるものとする。addresses[]で指定されたアドレスをすべてキャッシュに順に取り込んだとき、全部でメモリから何バイトを読み込んだかを返すメソッドを作成せよ(訳注：この文章は元の問題文にはありませんが、実行例に具体的に書いているので、こちらで補足しておきます)。

私の解答はこちら。

public class ContiguousCacheEasy {

 public int bytesRead(int n, int k, int[] addresses) {
  int[] range = new int[2];
  int nRead = 0;
  range[0] = 0;
  range[1] = k-1;

  for( int i=0 ; i<addresses.length ; i++ ){
   if( range[0] <= addresses[i] && addresses[i] <= range[1] ) continue;
   if( addresses[i] < range[0] ){
    int readBytes = range[0] - addresses[i] < k ? range[0] - addresses[i] : k;
    nRead += readBytes;
    range[0] = addresses[i];
    range[1] = addresses[i] + k - 1;
   }else if( addresses[i] > range[1] ){
    int readBytes = addresses[i] - range[1] < k ? addresses[i] - range[1] : k;
    nRead += readBytes;
    range[0] = addresses[i] - k + 1;
    range[1] = addresses[i];
   }
  }
  return nRead;
 }

}

得点は190.64/250、1回のsubmitでシステムテストクリア。中央値は約114点。難しいのは実装よりも文章でした。