TopCoder SRM173 Div2 250Pts

問題の詳細はこちらより確認できる(要TopCoder登録)。

問題の大まかな訳は以下の通り。

コンピュータのインストール作業のプログレスバーを実装する。進捗状況に応じて"######.............."のように、#が終了部分、.が終了していない部分として、それらを用いて20文字で表すクラスshowProgressを作成せよ。taskTimes[]が作業一つのタスクにかかる時間、taskCompletedは先頭から順にいくつタスクを終えたかという数を示している。タスクの進捗状況はインストールにかけた時間/インストール終了までにかかる時間である。また、進捗状況の#の数は小数点以下を切り捨てた整数にする。taskCompletedはtaskTimesの要素数を上回らない1以上の数とする。

例えば、taskTimes={20,35,15}、taskCompleted=1とすると、20/(20+35+15)*20=40/7=5.7なので、#は5個、.は15個になる。

Javaで実装すると以下のようになった。

public class ProgressBar {

 public String showProgress(int[] taskTimes, int tasksCompleted) {
  int taskSum=0;
  int taskCompSum=0;
  for( int i=0 ; i<taskTimes.length ; i++){
   taskSum += taskTimes[i];
  }
  for( int i=0 ; i<tasksCompleted ; i++){
   taskCompSum += taskTimes[i];
  }
  int igetaNum = 20*taskCompSum/taskSum;
  int dotNum = 20-igetaNum;
  String result = "";
  for( int i=0 ; i<igetaNum ; i++){
   result = result + "#";
  }
  for( int i=0 ; i<dotNum ; i++){
   result = result + ".";
  }
  return result;
 }

}

得点は235.80/250。素直な算数の実装なので、まずまずの速さ。上位者のコードでためになるものがあったので、メソッドだけ紹介。前回のArrays.sortに続いて、配列操作のメソッドを集めたクラスArraysが再度登場。

import java.util.*;

public String showProgress(){
 int done = 0, total = 0;
 for( int i=0; i<taskTimes.length ; i++ ){
  total += taskTimes[i];
  if( i<tasksCompleted ) done += taskTimes[i];
 }
 char[] r = new char[20];
 Arrays.fill(r, '.');
 Arrays.fill(r, 0, done * 20 / total , '#');
 return new String(r);
}

メモリの節約方法で参考になったものがあったのでこちらも紹介。Stringクラスは値が変更されると、別のメモリ領域に変更された値を割り当てるので、提出したコードのように、Stringクラスの変数に1文字ずつ追加するコードだとメモリを無駄に利用してしまうのである。以下のコードはそれに対策を施したものである。

StringBuffer buf = new StringBuffer("");
  for( int i=0 ; i<20 ; i++ ){
  if( i<igetaNum ){
   buf.append("#");
  }else{
   buf.append(".");
  }
 }
 return buf.toString();

上位の人の書き方にはArrays.fillを使っているものが多かった。行数も少ないし、可読性が高く参考になる。