TopCoder SRM481 Div2 250Pts

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

あなたは円の形に配置された多くの店からなるマーケットを訪れている。店は0からn-1という番号が時計回りにつけられている。各お店からちょうど一つずつの品物を買いたいと思っている。そこでお店0を時刻0秒で出て、時計回りにお店を回る。もしお店iにopenTime[i]より前、もしくはcloseTime[i]より後に到着したら、それはお店は閉まっており、購入を行えないことを意味する。もしopenTime[i]とcloseTime[i]の間に到着し、かつまだそのお店でほしいものを購入していないのであれば、即座にそれを買わなければならない(購入に時間はかからないものとする)。どちらの場合においても、すぐに次の店に向かわなければならない。2つのお店の間を移動するのにはtravelTime秒かかる。もし何も購入できなくなったらマーケットを離れるものとする。購入可能なものの合計数を返せ。

public class CircleMarket {

 public int makePurchases(int[] openTime, int[] closeTime, int travelTime) {
  boolean[] passedClosedTime = new boolean [openTime.length];
  boolean[] alreadyPurchase = new boolean [openTime.length];
  int currentTime = 0;
  int nPurchase = 0;
  int i = 0;

  while( true ){
   if( isAllClosed(passedClosedTime) ) break;
   if( openTime[i] <= currentTime && currentTime <= closeTime[i] ){
    if( alreadyPurchase[i] == false ){ // お店は開店中でまだ購入済みでない
     nPurchase++; // 購入数をカウントアップ
     alreadyPurchase[i] = true; // 購入済みフラグを立てる
    }
   }else if( currentTime > closeTime[i] ){ // 閉店時刻を過ぎていた
    passedClosedTime[i] = true; // 閉店済みフラグを立てる
   }
   i++;
   i %= openTime.length; // 次のお店への移動
   currentTime += travelTime; // 次のお店に進んだ時へ時刻をすすめる
  }
  return nPurchase;
 }

 private boolean isAllClosed(boolean[] state){ // すべてのお店が閉まっているかを判断するメソッド
  for( int i=0 ; i<.length ; i++ ){
   if( state[i] == false ) return false;
  }
  return true;
 }
}

得点は217.27/250、1回のsubmitでシステムテストクリア。時間と既に買ったかを管理する論理値型配列、現在時刻、購入したものの数、訪問しているお店の番号を組み合わせて実装。

TopCoder SRM480 Div2 250Pts

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

TopCoder Security Agency（TSA、本日設立された）は今新しい暗号化システムを開発した。この暗号化システムは暗号化する数字の列を入力として受け取る。あなたはTSAで働いており、仕事は暗号化プロセスの重要な部分を実装することである。入力のなかから1つの数字を取り出し、その値を1増やすことが認められている。これはリスト中のすべての数字の積ができるだけ大きくなるように行われなければならない。numbers[]という数字の列が与えられたとき、得られる積の最大値を返せ。ただし、返される値は2^62を超えないことは保証されているものとする。

import java.util.Arrays;

public class Cryptography {

 public long encrypt(int[] numbers) {
  Arrays.sort(numbers);
  long n = numbers[0] + 1;
  for( int i=1 ; i<numbers.length ; i++ ){
   n *= numbers[i];
  }
  return n;
 }

}

得点は247.04/250、1回のsubmitでシステムテストクリア。積を最大化するということは、最小値を見つけてそれに1を加えればよいということに気づけばOK。

TopCoder SRM479 Div2 250Pts

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

ジョンとブラスは飛行機を所有している。彼らはいくつかの連続したフライトをしようとしている、flightsのi番目の要素はi番目のフライトに必要な燃料を表している。フライトはflightsにある順序で行われる。最初にfuelリットルの燃料が飛行機にある。フライトを行うためには、飛行機の燃料が少なくともそのフライトに必要な量がなければならない。燃料を再度入れることなくフライトをこなせる回数の最大値を返せ。

public class TheAirTripDivTwo {

 public int find(int[] flights, int fuel) {
  int total = 0;
  for( int i=0 ; i<flights.length ; i++ ){
   total += flights[i];
   if( total > fuel ) return i;
  }
  return flights.length;
 }

}

得点は247.96/250、1回のsubmitでシステムテストクリア。順番にチェックしていくだけ。