2012年10月22日月曜日

TopCoder SRM438 Div2 250Pts

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

luckySetという整数の集合が与えられる。luckySetに属する2つの要素でAがBより大きく、AとBが共に正の整数である区間[A, B]は、もしAとBの間の整数がなければ不幸であると考えられる。luckySetという整数型配列と、nというluckySetの最大値を超えないような整数が与えられたとき、nを含む不幸な区間の数を返すメソッドを作成せよ。

例えば、luckySet={1, 7, 14, 10}、n=2である場合、1と7の間に2があり、2~6の整数を用いて、2を含むような区間を考えてみると、[2, 6]、[2, 5]、[2, 4]、[2, 3]の4つが該当する。

私の解答はこちら。

import java.util.Arrays;

public class UnluckyNumbers {

 public int getCount(int[] luckySet, int n) {
  for( int i=0 ; i<luckySet.length ; i++ ){
   if( luckySet[i] == n ) return 0; // Setの値があったら区間は作れないので0
  }
  Arrays.sort(luckySet); // ソートして、

  int[] between = new int[2]; // どこの間の区間にnがあるか検討する
  for( int i=1 ; i<luckySet.length ; i++ ){
   if( luckySet[i] > n ){
    between[0] = luckySet[i-1] + 1;
    between[1] = luckySet[i] - 1;
    break;
   }
  }
  if( n < luckySet[0] ){ // nがluckySetの最小値よりも小さい場合
   between[0] = 1;
   between[1] = luckySet[0] - 1;
  }
  int nInterval = 0; // 以下で区間の数を数える
  for( int i=between[0] ; i<=between[1] ; i++ ){
   if( i < n ){
    nInterval += between[1] - n + 1;
   }else if( i == n){
    nInterval += between[1] - n;
   }
  }
  return nInterval;
 }

}

得点は153.40/250、2回目のsubmitでシステムテストクリア。1回目の提出では、nがluckySetの最小値を下回る場合の処理を間違えていた。

2012年10月19日金曜日

TopCoder SRM437 Div2 250Pts

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

整数ほど美しいものは無い。整数の美しさは、10進数表記で書いたときに、含まれる異なった桁の数をいう。整数nが与えられたときに、その整数の美しさを返すメソッドを作成せよ。

私の解答はこちら。一旦文字列にして、各桁ごとに分解して集合を作成し、その集合のサイズを求めています。

import java.util.HashSet;

public class TheBeauty {

 public int find(int n) {
  String sn = "" + n;
  HashSet<Character> hs = new HashSet<Character>();
  for( int i=0 ; i<sn.length() ; i++ ){
   hs.add(sn.charAt(i));
  }
  return hs.size();
 }

}

得点は249.01/250、1回のsubmitでシステムテストクリア。問題文も実装も簡単な問題です。集合を作るときに、10で割った余りを集合に入れて、10で割ることを繰り返す方法もあります。

2012年10月18日木曜日

TopCoder SRM436 Div2 250Pts

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

あなたはソーシャルネットワークにおいて、もっとも人気のある人を決めたいと思っている。それをするために、"2-friends"というそれぞれの人が持っている数値を数えることにした。AがBという人と2-friendであるというのは、互いに友人である、あるいはAとBの間に共通の友人Cがいる状態をいう。もっとも人気のある人というのは、2-friendsの値が最大の人物のこととする (2-friendsを最大にする人が複数いることもある)。問題ではfriends[]という文字列型配列が与えられる。i番目の文字列のj番目の要素がYであれば、i番目の人とj番目の人は友人であり、Nでなければ直接の友人ではない。ソーシャルネットワークにおいて、もっとも人気のある人の2-friendsの値を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.HashSet;

public class FriendScore {

 public int highestScore(String[] friends) {
  int max = -1;
  HashSet<Integer> hs = new HashSet<Integer>();
  for( int i=0 ; i<friends.length ; i++ ){ // 各人について2-friendsを探索
   for( int j=0 ; j<friends[i].length() ; j++ ){
    if( friends[i].charAt(j) == 'Y' ){ // jはiの直接の友人か?
     hs.add(j);
     for( int k=0 ; k<friends[j].length() ; k++ ){ // iとjの共通の友人を探索
      if( k == i || k == j ) continue; // iとjは探索済(というか既に友人扱い)
      if( friends[j].charAt(k) == 'Y' ) hs.add(k);
     }
    }
   }
   max = Math.max(max, hs.size());
   hs.clear();
  }
  return max;
 }

}

得点は171.47/250、1回のsubmitでシステムテストクリア。この問題も実装より読解に時間がかかった。要は「友人」と「友人の友人」の数を探索しろと言っているのである。ああ、まぎらわしい。

2012年10月16日火曜日

TopCoder SRM435 Div2 250Pts

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

ケイトは一直線のコースの初めに、スキーの板をつけて立っている。コースはn個の同じ長さの部分からなる。pathFrictionという、コースの摩擦を表す文字列が与えられる。pathFrictionのi文字目は1から9の整数であり、コースのi番目の地域の摩擦を表している(以後、添字は0から始まるとする)。この問題では、ケイトのスキー板を1つの板として扱う。スキー板は同じ長さのm個の部分からなる。スキー板の摩擦はskiFrictionというi番目の文字が1から9という文字列でそれぞれ与えられる。これらはスキー板のi番目の位置を表している。最初に、ケイトはスキー板のi番目の部分がパスのi番目の部分に触れるように立っている。次に、ケイトはスキー板の(m-1)番目の部分がパスの(n-1)番目に触れるまで前に進む。1つの部分だけ前に進むときは、ケイトは一番遅い速度で前に移動する。1つの部分だけ前にすすむのにかかる時間というのは、スキー板の部分の数と現在いるコースの摩擦の合計で表される。ケイトがコースの最後にたどり着くまでにすべる時間の合計を返すメソッドを作成せよ。

例えば、skiFriction="45"、pathFriction="15196"であるとき、返す値は33になる。これは次のようにして計算される。スキー板は4、5という部分を持つ。板はコースは1、5という位置にある。ここで4+1、5+5というそれぞれの位置に対応させるようにして和をとる。すると、最大値は10なので、1つ前に進むのに10秒かかるということになる。次に進むと、コースは5、1になる。4+5、5+1と同様に対応する位置で和をとると最大値は9である。最後のステップでは、4+1と5+9を比較して14秒移動にかかるということになる。次のステップではpathFrictionの最後の文字を使うことになるので、移動は終了となる。以上より10+9+14=33が導出されることになる。

私の解答はこちら。

public class SkiFriction {

 public int bestPosition(String skiFriction, String pathFriction) {
  int n = 0;
  for( int i=0 ; i<pathFriction.length() - skiFriction.length() ; i++ ){
   int max = -1;
   for( int j=0 ; j<skiFriction.length() ; j++ ){
    int s = skiFriction.charAt(j) - '0';
    int p = pathFriction.charAt(i+j) - '0';
    max = Math.max(max, s+p);
   }
   n += max;
  }
  return n;
 }

}

得点は222.02/250、1回のsubmitでシステムテストクリア。私にとっては実装は楽でしたが、読解がしんどい一問でした。問題設定が現実的でなく、想像しづらいためかと思います。

2012年10月14日日曜日

TopCoder SRM434 Div2 250Pts

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

5つの正の整数が与えられたとき、least majority multipleというのは、5つの与えられた数のうち、3つ以上で割り切れる最小の正の整数を指す。a, b, c, d, eという5つの異なる値を取る正の整数が与えられたとき、least majority multipleを返すメソッドを作成せよ。

私の解答はこちら。

public class LeastMajorityMultiple {

 public int leastMajorityMultiple(int a, int b, int c, int d, int e) {
  int num = 1;
  while( true ){
   int divisible = 0;
   if( num % a == 0 ) divisible++;
   if( num % b == 0 ) divisible++;
   if( num % c == 0 ) divisible++;
   if( num % d == 0 ) divisible++;
   if( num % e == 0 ) divisible++;
   if( divisible >= 3) return num;
   num++;
  }
 }

}

1から順にカウントしていけばよいだけなので、工夫の余地はあまりないかな。しいて言うなら、5つの整数がすべて値が異なるという条件から、必ず返す値は3以上になるので、num = 3から探索を開始すればよいのではと思います。

2012年10月12日金曜日

TopCoder SRM433 Div2 250Pts

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

かつて数学がいつも大問題となっている王国があった。王家の会計のポストを充足しなければならいというときに、応募者には以下の問題が与えられた。「AとBという二つのN個の要素を持つ整数型の配列が与えられる。AとBに関する関数SをS = A0*B0 + … + AN-1*BN-1と定義する。Sをできるだけ小さくするようにAを並び替えよ。Bについては並び替えを認めないものとする。問題作成者は応募者の解答が正しいかチェックするようなプログラムを書くことに迫られた。A、Bという配列が与えられたとき、Sの取り得る最小値を返すようなメソッドを作成せよ。

私の解答はこちら。

import java.util.Arrays;

public class RoyalTreasurer {

 public int minimalArrangement(int[] A, int[] B) {
  Arrays.sort(A);
  Arrays.sort(B);
  for( int i=0 ; i<A.length/2 ; i++ ){
   int tmp = A[i];
   A[i] = A[A.length-i-1];
   A[A.length-i-1] = tmp;
  }
  int sum = 0;
  for( int i=0 ; i<A.length ; i++ ){
   sum += A[i]*B[i];
  }
  return sum;
 }

}

得点は246.01/250、1回のsubmitでシステムテストクリア。Sが最小値を取るのはAを降順、Bを昇順に並び替えて、添字が同じものを順に掛け算したときになります。Bを並べ替えるなと言っても、並べ替えた方が簡単というちょっと意地悪な問題。

2012年10月9日火曜日

TopCoder SRM432 Div2 250Pts

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

単語の各文字について、出現形式が1つの列からなる場合に限り、単語はまとめられているという。言い換えれば、1つ以上の文字が2ヶ所に分かれて出現しないということである。例えば、"code"はまとめられているといえるが、"aabbbccb"はbが2ヶ所に現れているので、まとめられているとは言わない。さて、words[]という文字列型配列が与えられたとき、そのなかでまとめられている文字列の数を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.ArrayList;

public class GroupedWordChecker {

 public int howMany(String[] words) {
  int nGrouped = 0;
  ArrayList<Character> al = new ArrayList<Character>();
  for( int i=0 ; i<words.length ; i++ ){
   char lastChar = words[i].charAt(0); // 直前の文字
   boolean isGrouped = true;
   al.add(lastChar);
   for( int j=0 ; j<words[i].length() ; j++ ){
    char c = words[i].charAt(j); // 現在の文字
    if( lastChar == c ) continue;
    lastChar = c; // 新しい文字が出てきたと判定
    if( al.contains(c) ){ // もし既に登場した文字だったなら「まとめられているとは言えない」
     isGrouped = false;
     break;
    }else{ // 未登場の文字なら出現済み文字として登録
     al.add(c);
    }

   }
   if( isGrouped ) nGrouped++;
   al.clear(); // 次の単語を判定するためにリストの中身を空にする
  }
  return nGrouped;
 }

}

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

2012年10月6日土曜日

POST送信とGET送信の違い

Webページからテキストボックスなどに入力したデータを別のプログラムに渡す方法は、POST送信とGET送信がある。これらの違いは次のようになっている。

POST送信

  • データはURLには付けない
  • 送信できるデータはテキスト、バイナリのどちらでもよい

GET送信

  • URLにデータを付けて送る
    • つまり、https://www.google.co.jp/search?q=googleのように、?に続けてデータをくっつけているということである。POST送信では?以降がURLに現れることはない。
  • テキストのみ送信可能
  • FORM宣言時に指定しなければGETが使われる
    • セキュリティのことを考えるとGET送信よりもPOST送信の方が安心できる。FORMタグで作成したフォームで、何も指定しないとGET送信になるので、POST送信にする場合はMETHOD="POST"のように属性を指定する必要がある。

2012年10月5日金曜日

2012年9月の学習記録

2012年9月に学習した主な本一覧。

入門・演習 数理統計(pp.161~222、演習問題74問)
収束の性質や順序統計量、十分統計量、指数型分布族について。復習を兼ねてスライドでまとめて紹介したいところ。この調子だと読み終えるのは11月上旬ぐらいになってしまうかなと予想。UMVUEの節で苦戦中。
基礎からのMySQL(pp.1~231)
ウェブシステムを作ろうとしているので、その一環として読書開始。PHPをテキスト後半で学ぶことになる。新しい構文が出てくるたびに、SQLのコードを考えながら打ち込むことになるので、よい訓練になっている。これは読みやすい。年度末までに、Webアプリを作って公開しよう!と考えている。PHP+Pythonぐらいでアイディアを実装できないかなと(何をするかはまだ内緒)。
これなら分かる最適化数学(pp.97~200)
EMアルゴリズムの導出をはじめて見ました。この辺りに演習があると言う事無しなんですけれどね。
SciPy lecture note(pp.1~130)
Pythonで数値計算の練習を兼ねて日本語版を読んでみた。英語版は定期的にアップデートされているようなので、英語が読めるなら、そちらを読んだ方がよいでしょう。
Webアプリケーション構築入門(pp.1~84)
うーん、ちょっと進み方が唐突すぎるかな。テキストとしては基礎からのMySQLぐらいの進み方の方が楽で読みやすいです。Web開発というと、Apacheやセキュアなプログラミング、データベースなど、覚えることが大量にあって結構キツイです。

その他、NHK実践ビジネス英語、情報セキュリティスペシャリスト試験の過去問題、TopCoderの過去問を解くなど。そろそろサーバのいじり方を学ばないといけないかな...?

2012年10月4日木曜日

TopCoder SRM431 Div2 250Pts

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

ある正の整数がmega cool numberであるというのは、その桁が等差数列を形成しているときにそう呼ばれる。Nを与えたとき、1以上N以下の間の整数でmega cool numberとなる整数の数を返せ。

例えば123は初項1、公差1の等差数列なのでmega cool numberになることを意味している。

私の解答はこちら。

public class MegaCoolNumbersEasy {

 public int count(int N) {
  if( N<=99 ) return N;
  int n = 99;
  for( int i=100 ; i<=N ; i++ ){
   String nstr = "" + i;
   int diff = nstr.charAt(0) - nstr.charAt(1);
   boolean isCool = true;
   for( int j=1 ; j<nstr.length()-1 ; j++ ){
    if( nstr.charAt(j) - nstr.charAt(j+1) != diff ){
     isCool = false;
     break;
    }
   }
   if( isCool ) n++;
  }
  return n;
 }

}

得点は216.90/250、1回のsubmitでシステムテストクリア。問題文を理解する方が実装よりも時間がかかっています。

フォロワー

ページビューの合計