TopCoder SRM269 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について、おおまかに説明する。ひさびさに練習できる環境になったので、問題をといてみました。

あなたは今、古いコードを新しいコンパイラ用に変換している。"->"を"."に書き換えるのであるが、コメント部では置き換えてはならない。コメントの部分は//で始まり、行末で終わりである。program[]というコードの文字列型配列が与えられたとき、そのコードを変換した結果を返せ。

public class AccessChanger {

 public String[] convert(String[] program) {
  for( int i=0 ; i<program.length ; i++ ){
   int posComment = program[i].indexOf("//");
   if( posComment < 0 ){ // コメントがない場合
    program[i] = program[i].replaceAll("->", ".");
   }else{
    // コメント前だけ取り出して置換
    String tmp = program[i].substring(0, posComment);
    tmp = tmp.replaceAll("->", ".");
    // コメント以降を結合
    program[i] = tmp + program[i].substring(posComment);
   }
  }
  return program;
 }

}

得点は218.66/250。正直、入力となるprogram[]を破壊する書き方はあまり好きではないですね。コピーしたものを返したくなります。どちらが便利かは状況に依るのでしょうが。

TopCoder SRM268 Div2 250Pts

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

あなたはクロスワードパズルを作成している。盤面は作成したのだが、パズルに単語をあてはめる必要がある。空のクロスワードパズルはXという黒マスと.という空のマスからなる。スロットの長さがNというのは、Nの空マスが連続した状態として定義され、黒マスあるいは盤面の端に挟まれたものである。Nは最低でも2とする。
board[]という空のクロスワードパズル(Xと.の文字のみからなる)と、スロットのサイズsizeが与えられたとき、水平方向のスロットで長さがちょうどsizeになるものの数を返せ。boardの各要素はパズルの各行を表しているものとする。

私の解答はこちら。1行取り出して.がちょうどsize個現れる回数をカウントするという、言われた通りのことを実装するだけで済む。

public class CrossWordPuzzle {

 public int countWords(String[] board, int size) {
  int n=0;
  for( int i=0 ; i<board.length ; i++ ){
   String[] aLine = board[i].split("X");
   for( int j=0 ; j<aLine.length ; j++ ){
    if( aLine[j].length() == size ) n++;
   }
  }
  return n;
 }

}

得点は247.08/250。行方向のみカウントすればよいので、特にインデックス操作もいらず、非常に簡単に解くことができた。列方向もカウントすると、charAtメソッドなどを使って解くのだろうなと考えながら解いていました。

2011年10月の学習記録

2011年10月に学習した主な本一覧。仕事が割と修羅場に近い状態が続いたので、あまり勉強していませんが。

なぜ、あなたはJavaでオブジェクト指向開発ができないのか(pp.86～150)

この本は読むだけでなく、手を動かして理解するということが重要そうだと思いました。実装に現れるモノを洗い出して、シーケンス図やクラス図を書くというのは割と普通だと理解しました。普段テストばかりで開発をすっかり忘れている感もありますが、開発のイメージをする/思い出すには悪くない本かなと考えています。

Eclipseで学ぶはじめてのサーブレット&JSP(pp.1～20)

Webそのものを知ること、Javaの実装能力を上げること、Web系の言語も触っておきたいなということからJSPに手を出してみました。

微分積分学(pp.26～30)

TopCoder SRM267 Div2 250Pts

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

最低10万ドル以上の課税可能な人の2004年の税金は以下のテーブルから計算される(表は問題文中を参照)。あなたの税金を計算するために、課税対象収入と税率と控除の適切なグループを見つけよ。

誰かがいくら税金を払うか分かった時、元の課税対象の収入はいくらだったのかということが知りたい。taxAmountという課税された額が引数として与えられたときに、もとの課税対象収入のもっとも近い額を返すTaxTableというメソッドを作成せよ。結果は最も近いドルの値で返せ(つまり小数点第1位で四捨五入)。もし、taxAmountが小さすぎて、テーブルになければ-1を返すようにせよ。

私の解答はこちら。

public class TaxTable {

 public int income(int taxAmount) {
  int max = (1000000 + 25357)*20 / 7 + 1; // 入力の上限から分かる探索範囲の上限
  int ret = -1;
  int least = 25000 - 6525; // 入力の下限を計算
  if( taxAmount < least ){
   return -1;
  }
  double minDiff = Double.MAX_VALUE;
  // 入力の下限から上限までで誤差が最小になる収入額を計算
  for( int i=100000 ; i<=max ; i++ ){
   double mul = retMultiplier(i);
   double sub = retSubtraction(i);
   double diff = Math.abs((i*mul-sub)-taxAmount);
   if( diff < minDiff ){
    minDiff = diff;
    ret = i;
   }
  }
  return ret;
 }
 private double retMultiplier(int v){ // 課税対象額に応じた税率
  if( v>=100000 && v<117250 ){
   return 0.25;
  }else if( v<178650 ){
   return 0.28;
  }else if( v<319100 ){
   return 0.33;
  }else{
   return 0.35;
  }
 }
 private double retSubtraction(int v){ // 課税対象額に応じた控除額
  if( v>=100000 && v<117250 ){
   return 6525.0;
  }else if( v<178650 ){
   return 10042.50;
  }else if( v<319100 ){
   return 18975.0;
  }else{
   return 25357.0;
  }
 }
}

得点は126.90/250。毎回300万回程度のループが回っているので、あまり速い動作にはならないと思います。TopCoderでは2秒で結果が返ってこればOKで、目安としては1000万回のループ以下であればOKということになるそうです。入力の上限がない場合は工夫が必要とは思いますが、コンテストで簡単な部類の問題なのでそこまで考えなくても良いようにできているのだと思います。

JMRX勉強会【プレゼンストラテジー リサーチへの応用】のメモ

約二か月前のことですが、初めてマーケティング業界の勉強会に参加してきました。マーケティング業界の悲哀が伝わってきました。プレゼンについては働く業界が違えど、あまり変わらないのかなという思いになりました。

マーケティングのお仕事の辛そうな点@打ち合わせ中

• 意思決定者(=経営者)に、前提をひっくり返されること
  
• クライアントの理解度がばらついている中、バランスを取った説明をすること
  

マーケティングの個人における課題

• 話すのが苦手、あるいは得意すぎて話し過ぎる
  
• 緊張、話が飛ぶ
  
• 時間配分のコントロール
  
• 人の目が見れない
  
• 話し方、動きに癖がある
  

リサーチの目的とは?やりたいことの発案->やりたいことの実現

1. 対象・マーケットの価値観の汲み取り
   
2. イノベーションの導入
   
3. 競合との差別化
   
4. ニーズの反映
   
5. 生み手・作り手の情熱
   

辛いのは、クライアントの後押しばかりではないということ。時にはリサーチの結果、無理であることを伝えなければならないということもある。また、リサーチの中でクライアントが欲していることに応えられているかということは意識する必要がある。

プレゼンの基本～魅力を伝える3つの価値

1. 表層価値
   
2. 経験価値
   
3. 背景価値
   

3つの価値はお見合い相手の女性にも当てはまるようだ。表層価値は体裁であり、美しさである(短時間で分かる)。経験価値は将来を共有することで得られる価値、つまり気が利くということを表している。背景価値というのは、対象の背景に存在し、将来享受できると想像される価値、つまり育ちの良さということになる。プレゼンでは、表層価値に該当するのは身なり、経験価値(プレゼンではこれが一番大事!)は誠実感や時間配分、背景価値は会社のブランドやプレゼンターの知見ということになる。

プレゼンをより良いものにする改善策としては、見た目については次のようなものがある。

• 服装は無難に
  
• 自分らしさを出しすぎない
  

資料については、次のような方針がよい

• 見せる資料と配る資料は別の方が良い。また極力シンプルなものがよい
  
• 主文は言い切りで、最小限の文字数に
  
• 表は着眼点を明確に(見て欲しい所は強調)
  
• グラフは主張しすぎないように
  
• 明確な構図
  
  • 例:左ビジュアル、右文章
• 見出しコピーはキャッチーに
  
• 読ませる工夫が重要
  
• 集計データの報告ではない(結論が先)
  

プレゼンについては、次のような方針がよい。

• 時間配分は2/3型
  
  • つかみ、概要、総括、詳細、まとめまでが2/3、残りの1/3は質疑応答
    
• ちょっと勿体つけて、最後にドカン
  
  • 根拠や理屈はあとから熱く、細かく
    

プレゼンの作法は人によって違うので、参考になる箇所、認められないという箇所さまざまありました。コミュニケーション能力の向上を目指してうまいこと取り込んでいきたいです。

TopCoder SRM265 Div2 250Pts

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

GUIは、さまざまなGUIコンポーネントで単語を適切に表示するテキストの決まりごとに依存している。1行のテキストで幅を決められれば、ウィンドウ中のテキストを中央にするのに役立てられる。あなたには、文字と空白からなる文が与えられる。また、あるフォントに対する、アルファベットの小文字(lowercawse)と大文字(uppercase)の文字の幅が与えられる。このとき、文の幅を返すメソッドを作成せよ。

uppercase[]とlowercase[]は26の要素からなる。uppercaseの先頭はAという文字の幅を表し、最後はZという文字の幅を表す。小文字の場合も同様で先頭はaの幅、最後はzの幅を表す。空白はいつも3ピクセルに相当する。また、文字が描画されたとき、隣り合う文字は1ピクセルあけられているものとする。

私の解答はこちら。

public class FontSize {

 public int getPixelWidth(String sentence, int[] uppercase, int[] lowercase) {
  int totalWidth = 0;
  for( int i=0 ; i<sentence.length() ; i++ ){
   if( Character.isUpperCase(sentence.charAt(i)) ){
    int idx = sentence.charAt(i) - 'A';
    totalWidth += uppercase[idx];
   }else if( Character.isLowerCase(sentence.charAt(i)) ){
    int idx = sentence.charAt(i) - 'a';
    totalWidth += lowercase[idx];
   }else{
    totalWidth += 3;
   }
   if( i < sentence.length()-1 ) totalWidth++;
  }
  return totalWidth;
 }

}

制約上、文字はアルファベットと空白しかないので、上のような回答が許されていることに注意。ちょっとした場合分けで解けるので、難しくはないと思います。

TopCoder SRM231 Div2 450Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文のおおまかな和訳については、後日掲載するものとして、ひとまず解答だけ載せておく。

public class Stitch {
 public String[] stitch(String[] A, String[] B, int overlap) {
  String[] blended = new String[A.length];
  for( int i=0 ; i<A.length ; i++ ){
   blended[i] = A[i].substring(0, A[i].length()-overlap);
   for( int j=1 ; j<=overlap ; j++ ){
    double val = ((overlap+1.0-j)*A[i].charAt(A[i].length()-overlap+j-1)+
                 j*B[i].charAt(j-1))/(overlap+1);
    char cval = (char)Math.round(val);
    blended[i] += cval;
   }
   blended[i] += B[i].substring(overlap);
  }
  return blended;
 }
}

昔解いた問題を下書きに置きっぱなしにしておくのももったいないので、掲載することにした。

TopCoder SRM266 Div2 250Pts

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

2つの飛び乗れる石がある10フィートの川を渡りたいと思っている。何回かジャンプが必要になるが、興味があるのは、一番長い距離のものだけである。これは明らかに大事な問題で、できるだけ飛ぶ距離の最大値を小さくしたいと思っている。二つの石の距離はユークリッド距離で定義する。
さて、整数型のx[]とy[]という2つの要素を持つ配列が与えられる。(x[i]、y[i])はi番目の石の座標を表している。あなたははじめ、x座標が0で、y座標は任意の値を取り得る川岸にいる。反対側の岸はx座標が10でy座標は任意の値を取る川岸である(つまり、川はy軸に平行なものと考え、その中に石が二つ置かれているということになる)。
あなたが飛ばなければならない最大距離をもっとも近い整数値に丸めて返せ。なお、石はx座標の1～9の整数値、y座標の0～10の整数値の場所にあるものとする。また、二つの石は同じ場所にはないものとする。

私の解答はこちら。

// 石1 -> 石2 -> 対岸
// 石1 -> 対岸
// 石2 -> 石1 -> 対岸
// 石2 -> 対岸
// 以上の4パターンを飛ぶ順番として列挙しておけばよい。以下のコードでは上から順に0～3という
// 添字を割り当てて、各ケースにおける飛ばなければならない距離の最大値を計算している。
public class SwimmersDelight {
 public int longestJump(int[] x, int[] y) {
  double[] maxDist = new double[4];
  double distBetweenStones = Math.sqrt(Math.pow(x[0]-x[1],2)+Math.pow(y[0]-y[1],2));
  maxDist[0] = Math.max(x[0], distBetweenStones);
  maxDist[0] = Math.max(maxDist[0], 10-x[1]);
  maxDist[1] = Math.max(x[0], 10-x[0]);
  maxDist[2] = Math.max(x[1], distBetweenStones);
  maxDist[2] = Math.max(maxDist[2], 10-x[0]);
  maxDist[3] = Math.max(x[1], 10-x[1]);
  double max = 10;
  for( int i=0 ; i<4 ; i++ ){
   if( maxDist[i] < max ){
    max = maxDist[i];
   }
  }
  return (int)Math.round(max);
 }

}

得点は108.13/250。結局、全パターンを列挙して求めるのが一番早いようだ。提出者の正解率が3割程度ということから、結構難しい問題だったようだ。

TopCoder SRM264 Div2 250Pts

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

ある先生が二つの成績をつける手法を思いついた。学生は点数を0～100の間で受ける。全学生の成績はscores[]という整数型配列で表され、昇順にソートされている。学生は最終的に0から8のグレードで評価される。先生は知的に各生徒に必要な成績を割り当てている。scoreのi番目の要素はi番目の要素のグレードに対応する。同じ点数の場合、グレードは高い方から低い方にソートされる。
最初の成績をつける方法では、ある学生にXという成績をつけたいと思った場合、それ以上の成績を持つ学生は少なくともX以上の成績になる。この制約はさておき、学生はとりうる中で最も低いグレードを付けられる。例えば、3人の学生の成績が{60,80,80}であり、先生が彼らに{3,8,6}というグレードを割り当てたいと思った場合、学生は{3,8,8}というグレードを受け取ることになる。3番目の学生は同じ点数の人で6より高い8という評価を受けている人がいるため、少なくとも8の成績を受け取ることになるからである。
2番目の方法では、ある学生にXという成績をつけたいと思った場合、その学生の点数以下の学生は最大でもXという評価しかしないというものである。先ほどの例では、3人の学生は{3,6,6}というグレードを受け取ることになる。というのも、2番目の学生は3番目の学生の評価に引きずられるからである。
二つの手法を適用し、各学生に対しグレードの差の絶対値を求め、その総和を返すようなメソッドを作成せよ。

私の解答はこちら。

public class GradingSystem {
 public int fairness(int[] scores, int[] grades) {
  int min = 8;
  int max = 0;
  int sMax = 0;
  int sMin = 0;
  for( int i=0 ; i<scores.length ; i++ ){
   max = Math.max(max, grades[i]);
   sMax += max;
  }
  for( int i=scores.length-1 ; i >= 0 ; i-- ){
   min = Math.min(min, grades[i]);
   sMin += min;
  }
  return Math.abs(sMax - sMin);
 }
}

この問題のポイントになるのは、同じ成績であれば、グレードは降順にソート済みであるということである。この条件により実装の量は少なくて済むようになっている。これに気付くのが遅かったため、コーディングにはかなり時間がかかりました。