TopCoder SRM487 Div2 250Pts

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

ウサギたちはプログラミングは好きだが、プログラミングの試験が好きではない。黒、グレー、白の3匹のウサギは最終試験を終えた。ウサギたちが問題について議論している間に、教授がやってきて、"黒いやつ、お前は0点だ、知識を確かなものにするために、グレーと白が取った点数の最大値の合計点を計算するプログラムを書け"といった。

試験はN問からなるものであった。ウサギたちは同じ問題を提示される。各問題に対し、その答えとしてA～Zのアルファベットの大文字を書かなければならなかった。問題に対し、1つの文字のみが正しいものとされ、他の25文字は正しくない回答となっている。正解は1点となり、ウサギの得た点数は問題に正解した数に一致する。

black、gray、whiteという黒、グレー、白のウサギが書いた回答を表す文字列が与えられる。それぞれの文字列はN文字からなり、文字列のi番目の文字はそれぞれのウサギのi番目の回答を表すものとする。黒ウサギの点数が0のときに、グレーと白のウサギが獲得しうる点数の合計の最大値を返せ。

私の回答は以下の通り。

public class BunnyExamAfter {

 public int getMaximum(String black, String gray, String white) {

  int points = 0;
  for( int i=0 ; i<black.length() ; i++ ){
   if( black.charAt(i) == gray.charAt(i) &&
    black.charAt(i) == white.charAt(i) ){
    // pass
   }else if( black.charAt(i) != gray.charAt(i) &&
     black.charAt(i) == white.charAt(i) ){
    points++;
   }else if( black.charAt(i) == gray.charAt(i) &&
     black.charAt(i) != white.charAt(i) ){
    points++;
   }else if( black.charAt(i) != gray.charAt(i) &&
     black.charAt(i) != white.charAt(i) &&
     gray.charAt(i) == white.charAt(i) ){
    points += 2;
   }else if( black.charAt(i) != gray.charAt(i) &&
     gray.charAt(i) != white.charAt(i) ){
    points++;
   }
  }
  return points;
 }

}

得点は220.72/250、1回のsubmitでシステムテストクリア。

TopCoder SRM486 Div2 250Pts

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

奇妙な省略形が扱いにくい携帯機器でテキストを書くのにしばしば用いられる。アルファベットと空白からなるテキストをエンコードする方法の1つに次のものがある。

• 空白はそのままで、各単語は単語ごとにエンコードされる。ここで単語とはアルファベットの続く連続した文字列をいう。
• もし単語が母音のみからなる場合、それはそのまま書かれる。
• もし単語が1つ以上の子音を含むのであれば、直前に別の子音がない子音のみ書く。母音を買い手はならない。
• 上記の規則において、母音は'a', 'e', 'i', 'o'と'u'である。他の文字は子音と考える。

例えば、"ps i love u"というのは、"p i lv u"と省略され、一方、"please please me"は"ps ps m"と略されるであろう。 originalという文字列が引数で与えられたとき、先述の方法で省略されたメッセージを返すメソッドを作成せよ。

私の解答は以下の通り。

public class TxMsg {

 public String getMessage(String original) {
  StringBuilder msg = new StringBuilder("");
  String[] strs = original.split(" ");
  for( int i=0 ; i<strs.length ; i++){
   if( isAllVowel(strs[i]) ){
    msg.append(strs[i] + " ");
   }else{
    msg.append(makeEncodedMessage(strs[i]) + " ");
   }
  }
  // if文の後者により、最後に空白ができる可能性があるので、trimを行う
  return msg.toString().trim();
 }

 private static boolean isAllVowel(String s){ // 入力がすべて母音か判断
  char[] vowels = {'a', 'e', 'i', 'o', 'u'};
  for( int i=0 ; i<s.length() ; i++ ){
   boolean isvowel = false;
   for( int j=0 ; j<vowels.length ; j++ ){
    if( s.charAt(i) == vowels[j] ){
     isvowel = true;
     break;
    }
   }
   if( ! isvowel ) return false;
  }
  return true;
 }

 private static String makeEncodedMessage(String s){
  char[] vowels = {'a', 'e', 'i', 'o', 'u'};
  StringBuilder sb = new StringBuilder();
  boolean prevConsonant = false;
  boolean currentConsonant = true;

  for( int i=0 ; i<s.length() ; i++ ){
   currentConsonant = true;
   for( int j=0 ; j<vowels.length ; j++ ){
    if( s.charAt(i) == vowels[j] ){
     currentConsonant = false;
     break;
    }
   }
   if( !prevConsonant && currentConsonant ){
    sb.append(s.charAt(i));
   }
   prevConsonant = currentConsonant;
  }
  return sb.toString();
 }

}

得点は158.01/250、1回のsubmitでシステムテストクリア。

TopCoder SRM485 Div2 250Pts

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

マナオはすべての商品が正の整数の価格を持つ国に住んでいる。彼は電子レンジを売る会社を立ち上げており、それらを売るのに最適な価格を決める必要がある。最近彼は新しい心理学的な発見を聞いた。それは価格の小さい方の桁に9が続くにつれて、消費者に魅力的になるというものである。たとえば9099は9が2つ、8909は1つ9が最後にあるので、前者が魅力的ということになる。

マナオはminPriceを下回らない価格でのみ売る余裕があり、消費者はmaxPriceを超えない価格でしか電子レンジを買わないということを把握している。minPriceとmaxPriceの間で9が最大限後ろに続く数のうち最大のものを見つけることでマナオを手助けせよ。

public class MicrowaveSelling {

 public int mostAttractivePrice(int minPrice, int maxPrice) {
  int nNine = 0;
  int price = minPrice;
  for( int i=minPrice ; i<=maxPrice ; i++ ) {
   int nCurrent = trailing(i, 9);
   if( nCurrent >= nNine ) {
    price = i;
    nNine = nCurrent;
   }
  }
  return price;
 }
 private int trailing(int num, int target){
  int n = 0;
  while( num >= 1 ){
   if( num % 10 == 9 ){
    n++;
   }else{
    return n;
   }
   num /= 10;
  }
  return n;
 }

}

得点は173.37/250、3回目のsubmitでシステムテストクリア。ちなみにtrailingは「後端の」という意味です。

TopCoder SRM484 Div2 250Pts

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

カード1には1～8の整数、カード2には1～4、9～12の整数、カード3には1、2、5、6、9、10、13、14、カード4には1～15の奇数が書かれている。太郎は花子に対して、1～16の整数を1つ思い浮かべ、それが各カードに含まれているか否かを尋ねた。その答えで整数は唯一に定まる。引数のanswerという文字列にはYないしNという文字が入り、カードiに数字が含まれているか否かの回答はi番目の文字に対応しているものとする(Yなら含まれる、Nなら含まれない)。このとき、花子が想像している数字を返すメソッドを作成せよ。

import java.util.ArrayList;

public class NumberMagicEasy {

 public int theNumber(String answer) {
  int[][] numbers = {{1, 2, 3, 4, 5, 6, 7, 8},
    {1, 2, 3, 4, 9, 10, 11, 12},
    {1, 2, 5, 6, 9, 10, 13, 14},
    {1, 3, 5, 7, 9, 11, 13, 15}
  };
  int[] pts = new int[16];
  if( answer.indexOf("Y") == -1 ) return 16; // 全部Nなら16
  for( int i=0 ; i<answer.length() ; i++ ){
   if( answer.charAt(i) == 'Y' ){
    for( int j=0 ; j<numbers[i].length ; j++ ){
     pts[numbers[i][j]-1] += 1;
    }
   }else{
    ArrayList<Integer> al = new ArrayList();
    for( int j=1 ; j<16 ; j++ ){
     al.add(j);
    }
    for( int j=0 ; j<numbers[i].length ; j++ ){
     if( al.contains(numbers[i][j]) ){
      int idx = al.indexOf(numbers[i][j]);
      al.remove(idx);
     }
    }
    for( int j=0 ; j<al.size() ; j++ ){
     pts[al.get(j)-1]++;
    }
    al.clear();
   }
  }
  for( int i=0 ; i<pts.length ; i++ ){ // 全部の条件にマッチする数字を返す
   if( pts[i] == numbers.length ) return i+1;
  }
  return 16;
 }

}

得点は117.24/250、1回のsubmitでシステムテストクリア。削除の仕様に対する設計がちょっと面倒でした。方針としては、各質問の回答で条件に合う数字に1点、合わない数字は0点をつけて、4回の質問で4点(=全部の条件に合う)になったものが答えになるように実装しました。

TopCoder SRM483 Div2 250Pts

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

エリーのやっかいな教育アシスタントのトーブはエリーに次のパズルを与えた。42->1、1337->0、669->3(もう少し続く)。このとき45678は何になるか？エリーは考えるのが早く、問題を解く直感のおかげで解法を思いついた。Googleである。答えは10進数で表記したときの数字の桁に含まれる穴の数の合計であるとわかった(桁の先頭に0埋めはしない)。1、2、3、5、7は穴が無く、0、4、6、9は穴が1つ、8は2つある。したがって45678は1+0+1+0+2=4となる。あなたはエリーに好印象を与えるために、ある整数から正しい答えを導くプログラムを書くことにした。整数numberが与えられたとき、その数に含まれる穴の数の合計を返せ。

public class DigitHoles {

 public int numHoles(int number) {
  int[] holes = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
  char[] cnumber = ("" + number).toCharArray();
  int nholes = 0;
  for( int i=0 ; i<cnumber.length ; i++ ){
   nholes += holes[cnumber[i] - '0'];
  }
  return nholes;
 }

}

得点は245.00/250、1回のsubmitでシステムテストクリア。配列で穴の数を管理するのが一番簡単そうな気がします。

TopCoder SRM482 Div2 275Pts

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

public class AverageAverage {

 public double average(int[] numList) {
  double val = 0.0;
  for( int i=0 ; i<numList.length ; i++ ){
   val += numList[i];
  }
  return val/numList.length;
 }

}

得点は273.16/250、1回のsubmitでシステムテストクリア。 (問題文の翻訳を誤って消してしまいました...numListから1つ以上の要素を取り出すパターンを列挙し、各パターンで平均を求め、その平均を求めよという問題だったと思います。)

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でシステムテストクリア。順番にチェックしていくだけ。

TopCoder SRM478 Div2 250Pts

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

タロウはおいしいキウイフルーツのジュースを用意した。彼はそれを0からN-1までの数字がつけられたN個のボトルに注いだ。i番目のボトルの容量はcapacities[i]リットルであり、bottees[i]リットルをそのボトルに注いでいる。そして、彼はボトルのジュースを再分配したいと思っている。このために0からM-1まで番号を付けられた操作を行う。i番目の捜査ではfromId[i]からtoId[i]にジュースを注ぐ。注ぐのをやめるのはfromId[i]の中が空になるか、toId[i]の容量が満杯になるかのどちらか早い方である。すべての操作が終わった時のキウイジュースの量を表したN個の要素からなる整数型の配列を返せ。

public class KiwiJuiceEasy {

 public int[] thePouring(int[] capacities, int[] bottles, int[] fromId, int[] toId) {
  for( int i=0 ; i<fromId.length ; i++ ){
   int from = bottles[fromId[i]]; // 注げる量
   int to = bottles[toId[i]];
   int toLeft = capacities[toId[i]] - to; // 注げる量
   int pourAmount = Math.min(from, toLeft); // 小さい方を調べて
   bottles[fromId[i]] -= pourAmount; // 移し替える操作
   bottles[toId[i]] += pourAmount;
  }
  return bottles;
 }

}

得点は242.44/250、1回のsubmitでシステムテストクリア。

TopCoder SRM477 Div2 250Pts

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

N日(1～Nという日とする)のうちK日(1<=K<=N)連続した休みがとりたいのだが、workingDaysにある日については会議がある（配列の要素は1以上N以下の整数で与えられる）。このとき会議がある日を最小でいくつずらせば、K日の連続した休みを取ることができるか。

import java.util.Arrays;

public class VacationTime {

 public int bestSchedule(int N, int K, int[] workingDays) {
  Arrays.sort(workingDays);
  int mindays = workingDays.length + 1;
  for( int i=1 ; i<=N-K+1 ; i++ ){
   int ndays = 0;
   for( int j=i ; j<i+K ; j++ ){
    for( int k=0 ; k<workingDays.length ; k++ ){
     if( workingDays[k] == j ) ndays++;
    }
   }
   if( ndays < mindays ) mindays = ndays;
  }
  return mindays;
 }

}

得点は190.81/250、1回のsubmitでシステムテストクリア。本文はもうちょっと前フリがあるのですが、面倒なので省略。

TopCoder SRM476 Div2 300Pts

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

N×Mの数字で埋められた行列がある。行列の要素は0～9である。この行列に対し、4つの操作が定義されている。それらは1行上にシフト(1番上の行は1番下に移動)、1行下にシフト(1番下の行は1番上に移動)、1列左にシフト（1番左の行は1番右に移動）、1列右にシフト(1番右の行は1番左に移動)というものである。1行しかなければ、1行上、下にシフトする操作は意味をもたないし、同様に、1列しかなければ1列左、右にシフトする操作は何も効果がないことに注意。matrix[]という、i番目の文字列のj番目の要素が行列の(i, j)要素を表す文字列型配列が与えられたとき、valueという値が一番左上に移動するのに必要な操作の回数の最小値を返せ。なお、valueに該当する値はmatrix中に複数存在することがある。左上に動かすべき要素がないときには-1を返せ。

public class MatrixShiftings {

 public int minimumShifts(String[] matrix, int value) {
  int nRow = matrix.length;
  int nCol = matrix[0].length();
  int minMove = nRow + nCol; // 最小移動回数のカウント
  int[][] array = new int[nRow][nCol]; // とりあえず数値として扱うことにする

  for( int i=0 ; i<nRow ; i++ ){
   char[] line = matrix[i].toCharArray();
   for( int j=0 ; j<nCol ; j++ ){
    array[i][j] = line[j] - '0';
   }
  }

  if( isExist(array, value) == false ) return -1; // 1個も検討すべき値がなければ-1で終了
  for( int i=0 ; i<nRow; i++ ){
   for( int j=0 ; j<nCol ; j++ ){
    if( array[i][j] == value ){
     int moveRow = Math.min(i, nRow-i); // 行方向に動かすべき最小回数
     int moveCol = Math.min(j, nCol-j); // 列方向に動かすべき最小回数
     minMove = Math.min(minMove, moveRow+moveCol); // valueが左上のセルに移動するまでの最小の移動回数を更新
    }
   }
  }

  return minMove;
 }

 private boolean isExist(int[][] a, int value){
  for( int i=0; i<a.length; i++ ){
   for( int j=0; j<a[0].length; j++ ){
    if( a[i][j] == value ) return true;
   }
  }
  return false;
 }
}

得点は254.13/300、1回のsubmitでシステムテストクリア。位置だけで左上のセルへの最小移動回数は決まるので、valueに合致するすべてのセルについてその回数を計算するだけ。コードは長いが、250点でも良さげ。

TopCoder SRM475 Div2 250Pts

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

ウサギたちはしばしばさびしさを感じるので、あるグループがまとまり、どれが一番美しい耳かを競うビューティーコンテストを開催した。1匹が1票を持つ。もし自身に投票した場合は無効となる。もっとも票数が多かったのが勝者となる。namesがウサギの名前、votesが投票先、それぞれのi番目の要素について取り出すと、ウサギnames[i]がvotes[i]に投票したということを意味する。勝者を文字列で返せ。もし複数の勝者がいるのであれば、空文字を返せ。

私の解答はこちら。

import java.util.HashMap;

public class RabbitVoting {

 public String getWinner(String[] names, String[] votes) {
  HashMap<String, Integer> hm = new HashMap<String, Integer>();
  for( int i=0 ; i<names.length ; i++ ){
   if( names[i].equals(votes[i]) ) continue; // 自分に投票したら票として扱わない
   if( hm.containsKey(votes[i]) ){ // 票としてカウント
    hm.put(votes[i], hm.get(votes[i])+1 );
   }else{
    hm.put(votes[i], 1);
   }
  }
  int maxvotes = -1;
  String winner = "";
  for( String key: hm.keySet() ){ // こういうループもある
   if( maxvotes < hm.get(key) ){ // 最多得票数を更新した場合
    winner = key;
    maxvotes = hm.get(key);
   }else if( maxvotes == hm.get(key) ){ // 最多得票数が複数でた場合
    winner = "";
   }
  }
  return winner;
 }

}

得点は189.29/250、2回目のsubmitでシステムテストクリア。最初にputするときに0で初期化して間違えるというオチ(1で初期化する必要がある)。

TopCoder SRM474 Div2 250Pts

今回解いた問題は、文字列Aの途中(Aの先頭と最後尾も含む)のすべての位置に文字列Bを挟んだとき、できた文字列が回文になっている数を返すメソッドを作成せよという問題。

私の解答はこちら。

public class PalindromesCount {

 public int count(String A, String B) {
  int n = 0;
  for( int i=0 ; i<=A.length() ; i++ ){ // 最後尾に付け足すので、A.lengthまで調べる必要がある
   String cur = A.substring(0, i) + B + A.substring(i); // Aの途中にBを挟んだ文字列を生成
   if( isPalindrome(cur) ) n++;
  }
  return n;
 }

 private boolean isPalindrome(String s){ // 文字列をひっくり返して一致しているか調べる
  StringBuffer sb = new StringBuffer(s);
  String rev = sb.reverse().toString();
  return s.equals(rev);
 }
}

得点は240.30/250、1回のsubmitでシステムテストクリア。割ときれいにかけました。

TopCoder SRM473 Div2 250Pts

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

頭の数をhead、脚の数をlegsとするとき、鶴亀算を行い、鶴の数と亀の数を表す要素2の整数型の配列を返せ。もし適切な解がない場合は要素数0の整数型の配列を返せ。

私の解答はこちら。

public class OnTheFarmDivTwo {

 public int[] animals(int heads, int legs) {
  if( 4*heads - legs < 0 || legs - 2*heads < 0 ){
   int[] x= new int[0];
   return x;
  }
  if( (4*heads - legs) % 2 != 0 || (legs - 2*heads) % 2 != 0 ){
   int[] x= new int[0];
   return x;
  }
  int[] x = {(4*heads - legs)/2, (legs - 2*heads)/2};
  return x;
 }

}

得点は233.91/250、1回のsubmitでシステムテストクリア。連立方程式を立てて解が非負の整数になるような条件を求める方針で解きました。日本語訳なので鶴亀算と紹介しましたが、英文では鶴を鶏と亀を牛で表現していました。そこは興味深いところかもしれません。

TopCoder SRM472 Div2 250Pts

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

タロウはカラフルなもの、特にカラフルなタイルが好きである。タロウの部屋は連続したL個のタイルで区切られている。各タイルは以下の4つの色の1つである：赤、緑、青、黄。roomという文字列が与えられ、各部屋のi番目の文字はR、G、BまたはYで現され、それぞれ赤、緑、青、黄を表している。タロウは隣り合う部屋の色が同じにならないように部屋の色を変えることにした。変えなければならないタイルの数の最小値を返せ。

私の解答はこちら。

public class ColorfulTilesEasy {

 public int theMin(String room) {
  int nChange = 0;
  char[] roomchars = room.toCharArray();
  char prevColor = 'X';
  for( int i=0 ; i<room.length() ; i++ ){
   char curColor = room.charAt(i);
   if( curColor == prevColor ){
    nChange++;
    roomchars[i] = 'X';
   }
   prevColor = roomchars[i];
  }
  return nChange;
 }

}

得点は243.22/250、1回のsubmitでシステムテストクリア。1文字ごとに分解してしまえばしめたものです。

TopCoder SRM471 Div2 250Pts

このTopCoderの問題は検索にかけても現れないのですが、簡単に説明してみます。

エリーは"2で割る"問題が大好きである。これにより彼女は2で割らなければならない問題を意味している。エリーはそれ自身が素数を含む数があることに気づいた。数XがYという数字を持つというのは、Y=X/2^k(非負の整数kで割って、切り捨てられたもの)を満たしているときをいう。エリーはすべての正の整数を"prime container"と呼び、その数が含む素数の数をprime containerの大きさと定義した。例えば、7の大きさは2である。これは7/1=7、7/2=3がともに素数だからである(訳注：これを続けると7/2^2=1なので素数にならない)。同様に47は5、959は6が得られる。正の整数Nが与えられたとき、その数のprime containerの大きさを求めることでエレノラを手伝え。

私の解答はこちら。

public class PrimeContainers {

 public int containerSize(int N) {
  int ans = 0;
  for( int i=1 ; i<=N ; i=i*2 ){
   int target = N / i;
   if( isPrime(target) && target >= 2 ){
    ans++;
   }
  }
  return ans;
 }

 boolean isPrime(int n){ // 素数か判定するプログラム
  int end = (int)Math.sqrt(n);
  for( int i=2 ; i<=end ; i++ ){
   if( n % i == 0 ) return false;
  }
  return true;
 }
}

得点は218.65/250、1回のsubmitでシステムテストクリア。後半の英文の意味が拾いにくかったので、意訳してしまいました。

TopCoder SRM470 Div2 250Pts

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

巡回しているセールスマンはLinear王国で製品を売ろうとしている。Linear王国は座標系にNの街がある。各街は点であり、i番目の街は(x[i], y[i])にある。Linear王国のすべての街は共線性がある、すなわちすべての街を通るまっすぐの線が存在することを意味する。巡回セールスマンはすべての街を訪問しようとしている。2つの街を移動するのに必要な距離はマンハッタン距離に等しい。任意の街から移動し、任意の街で移動を終えるとしたとき、セールスマンが移動しなければならない距離の最小値を返せ。

私の解答はこちら。

public class LinearTravellingSalesman {

 public int findMinimumDistance(int[] x, int[] y) {
  int[] minDist = {0, 0};
  boolean isStart = true;
  int[] prev = {0, 0};
  boolean[] isUsed = new boolean[x.length];
  for( int i=0 ; i<x.length ; i++ ){
   int target = -1;
   int minx = 10001;
   for( int j=0 ; j<x.length ; j++ ){
    if( isUsed[j] == false && x[j] < minx ){
     target = j;
     minx = x[j];
    }
   }
   if( !isStart ){
    minDist[0] += ( Math.abs(x[target] - prev[0]) +  Math.abs(y[target] - prev[1]));
   }
   prev[0] = x[target];
   prev[1] = y[target];
   isStart = false;
   isUsed[target] = true;
  }

  for( int i=0 ; i<x.length ; i++ ){
   isUsed[i] = false;
   isStart = true;
  }
  prev[0] = 0; prev[1] = 0;
  
  for( int i=0 ; i<x.length ; i++ ){
   int target = -1;
   int minx = 10001;
   for( int j=0 ; j<x.length ; j++ ){
    if( isUsed[j] == false && y[j] < minx ){
     target = j;
     minx = y[j];
    }
   }
   if( !isStart ){
    minDist[1] += ( Math.abs(x[target] - prev[0]) +  Math.abs(y[target] - prev[1]));
   }
   prev[0] = x[target];
   prev[1] = y[target];
   isStart = false;
   isUsed[target] = true;
  }
  
  return minDist[0] < minDist[1] ? minDist[0] : minDist[1];
 }

}

得点は183.36/250、1回のsubmitでシステムテストクリア。PCが壊れる前に解き、コメントがないので解き方の方針は忘れてしまいました(苦笑)

TopCoder SRM469 Div2 250Pts

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

ジョンとブラスはとても面白い映画を見に行こうとしている。彼らは同じ並びの隣り合った席に座りたいと思っている。映画館はn行m列のシートからなる。行方向は先頭から最後尾へ向けて1からnと番号づけられ、左から右に1からmと順に番号づけられている。いくつかのシートは既に埋まっており、ジョンとブラスは任意の空いている席を予約することができる。row、seatという整数型の配列が与えられ、そのi番目の要素row[i]、seat[i]は予約された席の位置を示している。すべての残りの席は空いている。ジョンとブラスが同じ並びで隣り合って座ることができる場合の数を返せ。なお、ジョンとブラスの位置までは考慮しないものとする。つまりジョンとブラスが逆に座っても同じ席の予約なので1通りとしてカウントするということである。

私の解答はこちら。

public class TheMoviesLevelOneDivTwo {

 public int find(int n, int m, int[] row, int[] seat) {
  boolean[][] isReserved = new boolean[n][m];
  for( int i=0 ; i<row.length ; i++ ){
   isReserved[row[i]-1][seat[i]-1] = true;
  }
  int nSeat = 0;
  boolean isPrevReserved = true;
  int nFree = 0;
  for( int i=0 ; i<n ; i++ ){
   nFree = 0;
   isPrevReserved = true;
   for( int j=0 ; j<m ; j++ ){
    if( isReserved[i][j] ) {
     isPrevReserved = true;
     nFree = 0;
    }else{
     isPrevReserved = false;
     nFree++;
    }
    if( nFree >= 2 ) nSeat++;
   }
  }
  return nSeat;
 }

}

得点は220.85/250、1回のsubmitでシステムテストクリア。「並び」、「行」と訳したのですが、まとめた方がよかったですかねぇ。

TopCoder SRM468 Div2 250Pts

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

王は長いこと外におり、妃の元へできるだけ早く戻りたいと思っている。王は街0におり、妃は街Nにいる。0からN-1の間の値をとる各iにおいて、街iと街i+1を結ぶ道と空路が存在する。i番目の要素がiからi+1へ向かうのに陸路でかかる時間を表すroadTime[]と、空路でかかる時間flightTime[]が与えられる。しかし、空路を選ぶことは王国における技術的な制限により王の命に危険がある。したがって、妃は王に最大でK回のフライトにするように頼んでいる。王が妃のもとにたどり着くまでにかかる最小の時刻を計算して返せ。

私の解答はこちら。

import java.util.Arrays;

public class RoadOrFlightEasy {

 public int minTime(int N, int[] roadTime, int[] flightTime, int K) {
  int[] diff = new int[N];
  int time = 0;
  for( int i=0 ; i<N ; i++ ){
   diff[i] = roadTime[i] - flightTime[i];
  }
  for( int i=0 ; i<N ; i++ ){
   time += roadTime[i];
  }
  Arrays.sort(diff);
  if( diff[N-1] <= 0 ) return time;
  int k = 0;
  for( int i=N-1 ; i>=0 ; i-- ){
   if( k >= K || diff[i] <= 0 ) break;
   time -= diff[i];
   k++;
  }
  
  return time;
 }

}

得点は201.00/250、2回目のsubmitでシステムテストクリア。最後に「|| diff[i] <= 0」を付け忘れての失敗。方針としては、iからi+1へ陸路と空路で向かった時にかかる時間の差をとり、空路の方が速いものから、最大K個とるというものである(実際の計算では陸路で全部向かったと仮定して、差分だけ引き算するようにしている)。ただし、速い方からK個とるうちに、陸路の方が速く到着するようであれば、それ以上は空路を選択せずに終了とする。