2014年3月15日土曜日

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は「後端の」という意味です。

2014年3月12日水曜日

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点(=全部の条件に合う)になったものが答えになるように実装しました。

2014年3月3日月曜日

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でシステムテストクリア。配列で穴の数を管理するのが一番簡単そうな気がします。

2014年3月2日日曜日

2014年1月の学習記録

最近ブログから離れがちなのは、仕事の煮詰まり具合によるものです。あと半年ぐらい続きそうな感がありますが、どうぞお付き合いくださいませ。

SpringによるWebアプリケーションスーパーサンプル 第2版(第1~3章)
初めて触るフレームワークなのですが、「設定より規約」ということで、どのようなルールがあるかということを理解していないと、簡単な書き方ができずに苦労しそうです。ちなみにパイロットプロジェクトとして問い合わせフォームを作り始めたのですが、参考書からちょっと外れるだけでかなり嵌っています。たとえば「戻る」ボタンを押したときにデータを保持したまま移動するという機能を実装するとか。いきなりMVCやオブジェクト指向をやっており、ショック療法を受けている真只中であります。
独習 Javaサーバサイド編 第2版(pp.1~80)
Springでの開発はjspを利用しているので、Web開発の教養と思って併読。

その他センター試験の数学を解くなど。私見ですが、今年の数学の問題は簡単な方だったと思います。

フォロワー

ページビューの合計