TopCoder SRM419 Div2 250Pts

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

柱状図(訳注：棒グラフと思って差し支え無いです)とは水平方向にn個の柱が配置されたものである。各柱は幅が1であり、各柱はx軸にくっついている。柱の高さはa[]という整数型の配列で与えられる。a[i]はi番目の柱の高さを表している(訳注：より詳しくはリンク先の画像をご確認ください。隣合う柱はくっついている図です)。与えられた柱状図の周囲の長さを返すメソッドを作成せよ。なお、a[i]は1以上50以下の整数になるものとする。例えば、aが{3, 2, 1}であれば、x軸に水平な方向の周囲の長さは柱の上側、下側を合わせて3*2=6、側面の長さは左から順に3+1+1+1で合計6なので、それらを合わせて12になる。

私の解答はこちら。

public class ColumnDiagramPerimeter {

 public int getPerimiter(int[] a) {
  int perimiter = 0;
  int prev = 0;
  for( int i=0 ; i<a.length ; i++ ){
   perimiter += Math.abs(a[i] - prev);
   prev = a[i];
  }
  perimiter += (a[a.length-1] + a.length * 2);
  return perimiter;
 }

}

得点は207.19、2回目のsubmitでシステムテストクリア。途中で提出のページに接続できなくなり、提出が遅れたのが残念。

TopCoder SRM418 Div2 250Pts

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

あなたは真剣に戦略ゲームをするプレーヤーなので、敵の防御塔を攻撃するという、もっとも一般的な問題を解くことにした。攻撃をする前にはmyUnitsという数の兵士を得る。各兵士は1回のラウンドにおいて、1つの塔に1のダメージを与えることができる。敵は兵士を持たない。しかしながら、体力がhpTの塔をnumT所持している。各塔は1回のラウンドにおいて、attackTだけの兵士を殺すことができる。1つのラウンドは次の順で行われる。

1. 自軍の各兵士は塔を1つ選び、塔に1のダメージを与える。塔がすべての体力を失うと、塔は破壊される。各兵士ごとに独立して攻撃する塔を選べるものとする。
2. 敵の攻撃になる。敵はk*attackTだけの自軍の兵士を殺すことになる。ここで、kは残っている塔の数である。

あなたの課題はすべての塔を破壊することである。もしそれが可能であれば、それを実行するのに必要な最小限のラウンド数を返せ。もし不可能ならば-1を返すようなメソッドを作成せよ。

私の解答はこちら。

public class Towers {

 public int attack(int myUnits, int hpT, int attackT, int numT) {
  int nTurn = 1; // 攻防を行った回数
  int totalHP = numT * hpT; // 塔の合計体力
  int remainT = numT; // 残っている塔の数
  int remainU = myUnits; // 残っている自軍の兵士数
  while( true ){
   totalHP -= remainU; // 塔の体力を減らす
   if( totalHP <= 0 ) return nTurn; // 塔の体力の合計が0以下なら全部破壊されたことになる
   remainT = (int)Math.ceil(totalHP*1.0/hpT); // 残っている塔の数を計算
   remainU -= remainT * attackT; // 自軍の兵士の数を減らす
   if( remainU <= 0 ) return -1; // もし自軍の兵士が全滅したら-1を返す
   nTurn++;
  }
 }

}

得点は196.74/250、1回のsubmitでシステムテストクリア。中央値は約135点。すべての塔を破壊するにはできるだけ塔を集中的に攻撃するというのが最善になることを利用します。タワーの残り体力を計算する際に、totalHPに1.0を掛けていなかったことに気付くのに少し時間がかかりました。

TopCoder SRM417 Div2 250Pts

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

与えられたXという整数に対し、Rev(X)というXの桁を反転させた整数を得ることができる。例えばRev(123)=321、Rev(100)=1である。xとyという二つの正の整数が与えられたとき、Rev(Rev(x) + Rev(y))を返すメソッドを作成せよ。

私の解答はこちら。

public class ReversedSum {

 public int getReversedSum(int x, int y) {
  StringBuffer xx = new StringBuffer("" + x);
  StringBuffer yy = new StringBuffer("" + y);
  int s = Integer.parseInt(xx.reverse().toString()) +
                        Integer.parseInt(yy.reverse().toString());
  StringBuffer ss = new StringBuffer("" + s);
  return Integer.parseInt(ss.reverse().toString());
 }

}

得点は243.24/250、1回のsubmitでシステムテストクリア。中央値は約233点。エレガントさを求めるのであればRev(X)という関数を定義するのが良さそうです。

TopCoder SRM416 Div2 250Pts

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

英語の典型的なテキストについて、いくつかの文字が他の文字よりも頻繁に現れるということが一般的に知られている。例えば、英語の長文においては、約12.31%の文字がeになる。言語学部の友人が、与えられたテキストの中で最も頻繁に現れる文字が知りたいということで、手伝ってくれるよう頼んできた。テキストはtext[]という文字列型の配列で与えられる。このとき、テキストでもっとも頻繁に現れる文字を返すメソッドを作成せよ。もし一番頻繁に現れる文字が複数ある場合、それらをアルファベット順で返すようにせよ。なお、文字列は小文字のアルファベットと空白しかないものとする。

私の解答はこちら。

public class MostCommonLetters {

 public String listMostCommon(String[] text) {
  int[] times = new int[26];
  for( int i=0 ; i<text.length ; i++ ){ // ここで文字の頻度集計
   for( int j=0 ; j<text[i].length() ; j++ ){
    char c = text[i].charAt(j);
    if( c != ' ' ){
     times[c-'a']++;
    }
   }
  }
  int maxTimes = -1;
  for( int i=0 ; i<times.length ; i++ ){ // 最大出現回数を調べる
   maxTimes = Math.max(maxTimes, times[i]);
  }
  String ret = "";
  for( int i=0 ; i<times.length ; i++ ){ // 出現回数が最大となる文字を集める
   if( times[i] == maxTimes ){
    char c = (char)('a'+i);
    ret += c;
   }
  }
  return ret;
 }

}

得点は241.25/250、1回のsubmitでシステムテストクリア。中央値は約186点。素直な集計の問題です。

TopCoder SRM415 Div2 250Pts

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

あなたの趣味は郵便消印を集めることである。N個の異なる消印があり、0からN-1まで番号が付けられている。それらの価値はprices[]という整数型の配列で与えられており、添字iが消印iの価値を表すものとする。あなたの目標はできるだけ異なる種類の消印を集めることである。既に持っている消印はhave[]という整数型配列で与えられている。また、初期状態では所持金0の状態とする。消印を売り、お金を得て異なる消印を買うということができる。集められる消印の種類数の最大値を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.Arrays;

public class CollectingUsualPostmarks {

 public int numberOfPostmarks(int[] prices, int[] have) {
  int value = 0;
  for( int i=0 ; i<have.length ; i++ ){
   value += prices[have[i]];
  }
  Arrays.sort(prices);
  int count = 0;
  int current = 0;
  for( int i=0 ; i<prices.length ; i++ ){
   current += prices[i];
   if( current > value ) break;
   count++;
  }
  return count;
 }

}

得点は191.82/250、問題文を読み替えて、全部売って安い方から買っていくと問題を置き換える発想の転換すると非常に見通しが良くなります。

一様分布から標準正規乱数を発生させる

標準正規分布に従う乱数を発生させる簡単な方法として、一様乱数をいくつか発生させてその和をとり、期待値で引き算するという方法がある。そこで、得られた値が本当に標準正規分布といって差し支えないか調べてみることにした。以下のコードでは、6つの一様乱数(取りうる値の範囲は[0,1])とし、それらの和の期待値3を引いたものを大量に発生させ、値の分布が一様乱数であるか検定したものである。6としているのは、とりうる値を[-3, 3]とするためである。標準正規分布であれば、多くの場合、そこから発生する乱数は[-3, 3]の範囲に収まるためである。

# 一様乱数から正規乱数を生成するプログラム

set.seed(1)
pts <- 6 # 一つの標準正規乱数を発生させるのに用いる一様乱数の数
N <- 5000 # 発生させる正規乱数
num.data <- N*pts
rn <- runif(num.data)
rnd.mat <- matrix(rn,nrow=N) # 一様乱数の行列
num <- rowSums(rnd.mat)-pts/2

hist(num,breaks=20,xlim=c(-4,4),xlab="",ylab="freq",main="")
oldpar <- par(new=T)
curve(dnorm,-4,4,xlab="",ylab="",axes=FALSE)
par <- oldpar

# コルモゴロフ・スミルノフ(KS)検定
# 標準正規分布 N(0, 1)とデータを比較している
ks.test(num, "pnorm", mean=0, sd=1)

コルモゴロフ・スミルノフ検定は、データがある分布に従っているかを検定するというものである。上のコードは1標本KS検定に相当する。帰無仮説はデータは分布から発生したものではない、対立仮説はデータは分布から発生したものとなる。統計量は従うと想定される分布の累積分布関数と、データのそれを比較した結果から得られる差の値に基づく。統計量が小さくなると、帰無仮説が棄却されるということになる。結論は、KS検定ではp値はほぼ0となり、帰無仮説は標準正規分布ではないということになった。ただし、中心極限定理からデータ数を6から増やせば、標準正規分布に従うことが想定される。そこで、pts<-12としてみると標準正規乱数といえるようなp値となった（有意水準5%で帰無仮説を棄却できる）。必要なptsのサイズは標準化する分布(今回は一様分布)の対称の程度に依存していることに注意。今回利用した一様分布U(0,1)は0.5で対称なので、比較的少ないデータ数で標準正規分布が生成できるのである。

TopCoder SRM414 Div2 250Pts

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

あなたはレストランのサービス部門のマネージャである。夕方のコースでは、顧客のグループがやってきて、その人たちをテーブルに配置しなければならない。レストランのテーブルは異なった人数の客に対応するために、さまざまなサイズのテーブルを用意している。テーブルへの客の配置は次のような手順で行う。客が現れたとき、まだ客で埋まっていないテーブルの内、そのグループ以上の人数を収められる最小のテーブルを客のために確保する。もし適切なテーブルが複数あれば、その中から任意に一つ割り当てる。もし適切なテーブルが一つもない場合は、顧客は即座に踵を返してその日の夕方は二度と現れない。グループが食事を終え、離れるとき、テーブルは利用できるようになり、新しい顧客を配置することができるようになる。

あなたはこの方法でテーブルに客を割り当てたとき、何人の顧客に逃げられるか知りたい。テーブルのサイズはtable[]という整数型配列で、各要素は収容可能な人数を表す。グループの人数、グループの到着時刻、出発時刻はそれぞれgroupSizes[i]、arrivals[i]、departures[i]である。i番目の要素はすべてグループiに関する情報である。グループは到着時刻順に並べられており、どのグループも同時に来ることはないものとする。もし、あるグループの出発時刻と別のグループの到着時刻が一致した場合は、出発するグループのテーブルは利用可能になっているものとする。逃げられた顧客の総数を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.Arrays;

public class RestaurantManager {

 public int allocateTables(int[] tables, int[] groupSizes, int[] arrivals, int[] departures) {
  Arrays.sort(tables);
  boolean[] isOccupied = new boolean[tables.length];
  // テーブルにいるグループの出発時刻。
  // i番目の要素がテーブルiを表す。値0はそのテーブルに誰も座ってないことを意味する
  int[] depTime = new int[tables.length];
  int nTurnedAway = 0;
  for( int i=0 ; i<arrivals.length ; i++ ){
   for( int j=0 ; j<tables.length ; j++ ){ // 来た人の時刻により、埋まっていたテーブルを解放
    if( arrivals[i] >= depTime[j] && depTime[j] > 0 ){
     isOccupied[j] = false;
     depTime[j] = 0;
    }
   }
   boolean caught = false;
   for( int j=0 ; j<tables.length ; j++ ){ // 空いているテーブルの探索
    // 最初に見つかったところに顧客を割り当てる(事前にテーブルサイズでソートしておくのがキモ)
    if( isOccupied[j] == false && tables[j] >= groupSizes[i] ){
     isOccupied[j] = true;
     depTime[j] = departures[i];
     caught = true;
     break;
    }
   }
   if( caught == false ){
    nTurnedAway += groupSizes[i];
   }
  }
  return nTurnedAway;
 }

}

得点は201.97/250、1回のsubmitでシステムテストクリア。中央値は約125点。テーブルを小さい順に並び替えておくことで、空いている必要最上限のテーブルサイズを探索するのが容易になります。