250点問題は再帰でさらっとかけた。

500点問題はできたと思ったのにシステムテストで落とされてた。あれれと思ってみてみると、しょうもないミス。

1000点問題は開いてみたけど、ちょっと手が動かず。

結局さらに落ちて灰色。

forを0から回したい時にレンジの都合で負になってしまう場合maxで評価するとよい

for(int i=max(0,k);i<vectors.length();i+)

ふむふむ。

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';

こんな感じ

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

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

500は後でちゃんと解く。

ベクタのベクタを作ったらなんだか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;
  }

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

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

シュワルツ変換でソートをかけていって、一位が過半数とってたらその候補者を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

splitができなくて難儀した。

というわけでxでsplit。substrで前から切り刻んでいく。

#include <vector>
#include <string>
#include <iostream>

using namespace std;

int main(){
  string str = "..x..x.xxx.xxx.....x.x...x..x.x....x.x...";
  int cutAt;
  while( (cutAt = str.find_first_of('x')) != str.npos ){
    if(cutAt > 0)
      {
       cout << str.substr(0, cutAt).size() << endl;
      }
    str = str.substr(cutAt + 1);
  }
}

あーこれだと最後のstringは何もしないな。

"3d18"みたいな文字列を二つのintに分けるのにfindとsubstrを使ったが、

string dice = "3d18";
int j = dice.find("d");
int rolls = atoi(dice.substr(0,j).c_str());
int num = atoi(dice.substr(j+1,dice.length() - j - 1).c_str());

そういう場合にはsscanfでよいらしい。

string dice = "3d18";
int n,s;
sscanf( dice.c_str(), "%dd%d",&n,&s);

それにしてもsplitがないのが不便だな。

c++を学ぶのによさげなのでTopCoderのpracticeを解いていたんだけど、ちょうど深夜1時にSRM402があったので、ふと参戦してみようと思った。

で、参戦した。

250点と500点問題を解いた。250点問題は問題の意図を間違えていて、あわてて修正したのでかなりロスった。500はやけに簡単ダナァと思ったら、ダブルデータという落とし穴があった(僕を含め、何人かはこれで撃墜されてた)。

チャレンジタイムとかいう、バグリそうなテストデータを突っ込んでみようタイムがやたらと楽しい。見てただけだけど、ヒトのコードを見ながら色々考えるので、この時間は結構勉強になるな。

初参加の僕は真っ先に標的にされてあっさり500点問題を撃墜されたけど、いわゆる念の洗礼というやつか。

それから今回、同じ組には、初参加は僕の他に3人いたけど、そのうち2人は1問も解いてなかった。みんなそんな感じで参加しにくるのかと。

というわけで、緑色だ。

sortした時に最大値を得るのにnums[nums.size()-1]とやったけど、*--nums.end()でもいいのかね。最小値はnums[0]でも*nums.begin()でわかりやすいのに。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main () {
  vector <int> vec;
  vec.push_back(4);
  vec.push_back(7);
  vec.push_back(6);
  vec.push_back(3);
  sort(vec.begin(), vec.end());
  cout << *--vec.end() << endl; // 7
}