2015-03-02

日記

 昼起きて午後から出かけて10年前の人々とリユニオンしてきた。楽しかったけど、うーんあんまりうまく喋れなかったなぁと思った。夜遅く帰ってきてちょっとプログラム書いたりして終わり。

雑記 [programming, C++]

・降順のソート(vector)

sort(v.begin(), v.end(), greater<int>());
か
sort(v.begin(), v.end()); reverse(v.begin(), v.end());

でよろしい。

・ビット演算を使って全ての組み合わせを出力する
ABC018Dのコードを漁っていたら知った。たとえば__builtin_popcount(n)で、nの二進表記で1が立ってる数を得ることができて、__builtin_popcount(11)なら1011なので3を返してくれる。これを使ってcombinationのすべてのパターンを出力ができる。というのは、便利に組み合わせが出力できるコードというのがなかなか見つからなくて(あんまり詳しく調べてないけど)困っていて、うーんどうやるんだろうなぁと見ていたらほとんど全ての人がこれに類するビット演算を使っていた(常識らしい、ショックだ)。2のn乗までビットをぐるぐる増やしていけばnビット分の01の配置の全てのパターンが出てくるから、そのうち任意のpビットだけ1のものを選ぶと、最下位ビットからの桁数が組み合わせのパターンとして出てくるよねという感じ。

//hoge.cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,p; cin >> n >> p;
  for (int i = 0; i < (1 << n); i++) { //(1 << n)は1をnビット左シフトしたもの。
    if (__builtin_popcount(i) == p) {
      for (int j = 0; j < n; j++) 
	if (i >> j & 1) cout << j + 1 << " "; //最下位バイトからj+1桁目が1
      cout << endl;
    }
  }
  return 0;
}

こんな感じ。出力は

$ echo 5 3 | ./hoge.out
1 2 3 
1 2 4 
1 3 4 
2 3 4 
1 2 5 
1 3 5 
2 3 5 
1 4 5 
2 4 5 
3 4 5

のようになる。
__builtin_popcountの部分は、

int count = 0;
for (int j = 0; j < n; j++) count += i >> j & 1;

(int)bitset<18>(i).count(); //18はビット列の長さの指定、こういう宣言にも慣れたい

bitset<18> bs(i);
if (bs.count() != p) continue;

でもいい。ここでnは桁数かつ組み合わせで選ばれる候補の個数。pは選ぶ数。とにかくこれですべてのパターンを検証できる。
if (i >> j & 1) の部分は、...xxxと...001のandを取るので、...xxxの最下位1ビットが1のときだけ値1を返すようなif文になる。&の両辺は整数値の比較なので、右辺の1は2進数表記の1じゃなくて10進数表記の1であることに留意。
やっぱりソートしたいので、次のように変える。

//hogehoge.cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,p; cin >> n >> p;
  vector<vector<int> > res; //vector<string>でもいいかも
  for (int i = 0; i < (1 << n); i++) {
    if (__builtin_popcount(i) == p) {
      vector<int> r;
      for (int j = 0; j < n; j++) 
	if (i >> j & 1) r.push_back(j+1);
      res.push_back(r);
    }
  }
  sort(res.begin(), res.end()); //よくわからないけどふつうにソートできた
  for (int i = 0; i < res.size(); i++) {
    for (int j = 0; j < p; j++)
      cout << res[i][j] << " ";
    cout << endl;
  }
  return 0;
}

とすると、(<int>のあとにスペースひとつ入れないとcinの>>と勘違いされるらしい?)

$ echo 5 3 | ./hogehoge.out
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

と良い感じに出力されてくれる。といってもこんな感じの出力がしたいのではなく、配列のインデックスが欲しい場合が多いだろうから、r.push_back(j+1);の部分をあれこれして使えばよろしい。
もう一度言うけど提出している人のほとんど(コンテスト時間内に提出しているC++の人しか見てないけど)がビット使って組み合わせを回してた。あまりにも統一的に使われているので常識なんだと思う。他にも常識的なコツがたくさんあるんだろうなぁ。

広告を非表示にする