ベクタのベクタを作ったらなんだか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は何もしないな。

三番目の引数に設定する

sort(vc.begin(), vc.end(), greater<int>());

または

sort(vc.rbegin(), vc.rend());

"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
}

perlだと

say "abc" x 3 # abcabcabc

と書けるところをc++だと

string ret = "";
for(int i=0;i<3;i++) ret += "abc";
cout << ret << endl;

と書かないといけないのか？

topcoder 154div2 300点で"320.56 450.44"みたいな入力をdouble,doubleの組にするという問題。

cinは空白を読み込まないので

double x, y;
cin >> x >> y;

と書ける。

あと

#define all(v)  (v).begin(),(v).end()

と定義しておけば、

sort(all(vec))

という風に楽ができる

topcoderのsrm151 DIV2の250点問題の他のヒトの解答をみていたらみつけた。

#include<iostream>

using namespace std;
int main(){
  int result = 5;
  result <?= 3; // 3
  cout << result << endl;
}

条件に合致する場合に代入する演算子。コンパイルしたら警告がでた。

warning: minimum/maximum operators are deprecated

他にはstringはfind,substrというメソッドがあってperlと似たような感じで文字列操作ができるということを知った。

というか、文字列操作の比較表: Ruby, Python, JavaScript, Perl, C++が便利。

topcoder SRM147DIV2の250点問題。tが文字列で、shiftが移動文字数。これを復号するが、

t[i] = (t[i] - 'A' - shift + 26) % 26 + 'A';

とやってA->Zの循環をifを使わずに済ませる。別にC++に限らずpythonでもperlでも一緒なので覚えておく。