500点問題

• 文字列から?以外の数字の位置を探る。
• そこから左と右にそれぞれ数字を埋めていく

という流れで。

差分をとって10足して、そのあと10の余りをとって、さらに '0'を足せばキャストしなくていい。

  for(j=k-1;j>-1;j--) a[i][j]=(a[i+1][j]-a[i][j+1]+10)%10+'0';

こんな感じ

Mooseでデザパタとデザパタ本を読みながらメモっていく。

増補改訂版Java言語で学ぶデザインパターン入門
結城 浩
ソフトバンククリエイティブ / ￥ 3,990 ()
通常24時間以内に発送

• Adapter
  • handlesで委譲させるべし
• Template Method
  • Moose::Roleで抽象クラス
  • requiresでメソッドの実装を要求
• Factory Method
  • コンストラクタの実装を要求するとこはtemplate method
• Singleton
  • MooseX::Singletonを使う
• Bridge
  • 機能と実装を委譲で緩く結びつける
  • 実装側はMoose::Roleで抽象クラス
• Composite
  • Moose::Roleで抽象クラス
• Visitor
  • あとで
  • デザパタ本のjavaの実装だとacceptメソッドにオーバーロード使っている
• Chain of Responsibility
  • あとで

型による制約とMoose::Roleでインターフェースや抽象クラスが作れるのがよいのかな。

Moose CookBookを読んでいたら、Rubyも気になりだしたのでおもむろにプログラミングRuby を読み出した（以前買った初版のほうだけど）。

プログラミングRuby 第2版 言語編
Dave Thomas,Chad Fowler,Andy Hunt
オーム社 / ￥ 3,990 ()
通常24時間以内に発送

というわけで一通り読み終えた。

土曜日で集中力が続く日はよいなぁ。

ちょっと余裕が出てきたのでここらでMooseなど

.Netでpython実装とかjavaでpython実装とかそういうのに比べて、perlでperlを変えていくサマはまるで、今週号のハミィのようだと思った。

ピューと吹く!ジャガー1 「ふえとポエムと、時々、オトン」

Happinet(SB)(D) / ￥ 1,980 (2008-07-25)
近日発売　予約可

となるとironpython,jythonはハメ字郎の作る笛の如きものなのかね。

と娘と追いかけっこをしながら思った、週末の夜

灰色に落ちた。というか実力に見合った色かもしれん。

• 250: 問題をちゃんと理解してなくて撃沈
• 500: 素直にとけば良さげな問題だったが、なんかおかしな事になって終了
• 1000: unopened

500は後でちゃんと解く。

シャッフルしてたらひっかかったので、アルバム通して聴いたけど、 やっぱいいですのー。

HIGHVISION
スーパーカー
キューンレコード / ￥ 3,059 (2002-04-24)
通常24時間以内に発送

そういえば、エウレカの時は日曜ちゃんと朝起きてたなぁ。 それ以来テレビはほとんど見てなくて、最近「電脳コイル」と「精霊の守人」を立て続けにみた。

Catalyst::View::JSONとjQueryの組み合わせでJSONデータのやりとりは簡単にできるのでたまにグラフを書きたくなったらFlotを使うとよさげな感じ

あんま凝ったことはできないのでちょっとした折れ線グラフかヒストグラムな用途

tickに数字以外のものを表示させるメモ

data:  [[0,2],[1,4],[2,6]]
ticks: [[0, "red"], [1, "brue"], [2, "pink"]]

という感じで　xの値と対応させたい文字列を合わせてticksに指定する。

ベクタのベクタを作ったらなんだかpush_backが多くて見にくいなと思ってたら　stringの二次元配列を作ってる解答があったので見習う。

あと、ベクタのベクタを作る場合にダイヤモンドの間にスペースを入れないとコンパイルエラーになる理由がよくわからん。

using namespace std;
class Matching {
public:
  vector <string> findMatch(vector <string> first, vector <string> second) {
    vector <string> cards, colors, shadings, numbers, ret;
    cards.push_back("CIRCLE");   cards.push_back("SQUIGGLE");   cards.push_back("DIAMOND");
    colors.push_back("RED");     colors.push_back("BLUE");      colors.push_back("GREEN");
    shadings.push_back("SOLID"); shadings.push_back("STRIPED"); shadings.push_back("EMPTY");
    numbers.push_back("ONE");    numbers.push_back("TWO");      numbers.push_back("THREE");
    vector < vector<string> > data;
    data.push_back(cards);
    data.push_back(colors);
    data.push_back(shadings);
    data.push_back(numbers);
    for(int i=0;i<first.size();i++){
       if(first[i] == second[i]){
    ret.push_back(first[i]);    
      }else {
     for(int j=0;j<data[i].size();j++){
      if(data[i][j] != first[i] && data[i][j] != second[i]) ret.push_back(data[i][j]);
    }
      }
    }
    return ret;
  }

PNEのバックナンバーが探せるってのが便利。早速自分の書いたやつを検索して「おーあるじゃん」とかやってみたり。

あと、OpenIDサーバーが立っていてなんじゃ?と思ってたら、研究開発創作日誌に書いてあった。

でも、IDの使い回し以外に他にもなんか考えているんだろうか？気になる。

AnnoCPANの論文版みたいなのできたらええかもしれんなぁといつも思うけど、OpenIDとか組み合わせるともっと面白いかもしれんなぁ。

YAPCのトーク聴いとけばよかったなぁ。

というわけでいまからニコニコで見る。

追記 08.06.03

AnnoCPANはCPANのPODにアノテーションつけられるサービスです。

論文もああいう風にパラグラフとかのもっと細かい単位でアノテーションつけたりできればよいんではなかろうかと思ってます。

IFは雑誌のおおざっぱな指標にしかならなくて、個々の記事の質はやっぱまちまちだからなーなんて思ったりしてるので、なんか適当にアイデンティティを保証さえできれば、どういう論文にどういうアノテーションをつけてるかとかで(アノテーター自体の)クオリティとか把握しやすいと思うんですよね。

あと、そういう場合にpagerank的なやり方でなんかファクター作れんのかなぁとかそういうことに興味があったりとか。

過半数とるまで、最下位の票を無効にしてもう一度投票し直しまっせっていう問題。

投票者は候補者をランク付けしておいて、一位の候補者が過半数を取っていればいいし、もしそうでなかったら、最下位に投票した投票者の票の次のランクの候補者に票を割り振っていくという。

シュワルツ変換でソートをかけていって、一位が過半数とってたらその候補者をreturnすればいいし、そうでなかったら、最下位候補者を投票の文字列から除いて再度やればいいのはわかったんだけど、　c++での書き方がわからん。

結局こんな感じになってしまった。一位と最下位調べるのにmapで組を作っておいて、イテレータで走査してminとmaxを記憶というやり方までは一緒。そのあと、最下位を消すのがわからなかったけど、この解答ではfindして見つかったindexをeraseしてた、なるほど。

perlだと

@votes = sort {$b->[1] <=> $a->[1]} map {[$_,$votes->{$_}]} split(//,$candidates);

っていうふうにつなげられるのがよいんだけどな。

$ballots = [map {s/$votes[-1]->[0]//;$_ } @$ballots];

あとCだと文字列の置換がまだしっくりこない。

perlの解答

sub outcome {
  my ($candidates, $ballots) = @_;
  my $total = @$ballots;
  return "" if  $total == 0;
  my($votes, @votes);
  while(1) {
    $votes = count_vote($ballots);
    @votes = sort {$b->[1] <=> $a->[1]} map {[$_,$votes->{$_}]} split(//,$candidates);
    return $votes[0]->[0] if($votes[0]->[1] * 2 >= $total);
    $ballots = [map {s/$votes[-1]->[0]//;$_ } @$ballots];
    $candidates =~ s/$votes[-1]->[0]//;
  }
}

sub count_vote {
  my $ballots = shift;
 my $counts = {};
  $counts->{substr($_,0,1)}++ for (@$ballots);
  return $counts;
}

print  outcome("ABC",["ACB", "BCA", "ACB", "BCA", "CBA"]);                       # B
print  outcome("DCBA",["ACBD", "ACBD", "ACBD", "BCAD", "BCAD", "DBCA", "CBDA"]); # B
print  outcome("ACB",["ACB", "BCA", "ACB", "BCA", "ACB", "BCA", "CBA", "CAB"]);  # ""
print  outcome("CAB",["ACB", "BCA", "ACB", "BCA", "ACB", "BCA", "CAB", "CAB"]);  # A
print  outcome("Z",["Z"]);                                                       # Z