水面下の夢

競プロやイラストに興味があります.メインブログがここ.同人サークル「かのらぶ」のページはこっち( https://yumechi0525.amebaownd.com ).ブログアイコンはYaQ(@8_9_00)さんから.

備忘録:C++のnext_permutationはかならずソートしてから使う

単純に競プロの本番でハマった話。Pythonだとはまらない問題だったので、余計に困った。 仕様をしっかり知っていなければいけない(戒め)

さっさとコードと実行結果を紹介する。こういうことをするとハマる。

#include <iostream>
#include <vector>

#include <algorithm>
#include <functional>
#include <iterator>

using namespace std;

/** FOR VECTOR DEBUG */
template <typename T>
ostream& operator<< (ostream& out, const vector<T>& v) {
  if ( !v.empty() ) {
    out << '[';
    copy (v.begin(), v.end(), ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.precision(16);

    vector<int> vec{10, 30, 20};
#if DEBUG
    cout << "** RESULT **" << endl; // debug
#endif
    do {
        cout << vec << endl;
    } while(next_permutation(vec.begin(), vec.end()));
    
    return 0;
}

実行結果(templateでvectorの中身表示した結果です)

wandbox.org

[10, 30, 20] 
[20, 10, 30] 
[20, 30, 10] 
[30, 10, 20] 
[30, 20, 10] 

見て分かる通り、[10, 20, 30] という組が無いです。どうやら昇順で最後のものになると組み合わせ作ってしまうのが終わってしまうみたい。。。。 このあと、[30, 20, 10] で試しましたが、予想通り、1つしか帰ってこなかったのでした。

ちなみに、Pythonの itertools.permutations は漏れなく出るので、制約に余裕がある場合はこっちを書こうなあと思ったPythonしか書けない系競プロ部でした…。

from itertools import permutations

for elem in permutations([10, 30, 20]):
    print(elem)

出力結果。 wandbox.org

(10, 30, 20)
(10, 20, 30)
(30, 10, 20)
(30, 20, 10)
(20, 10, 30)
(20, 30, 10)

組み合わせを使う問題はそれなりに頻出だと思うので、次回ははまらないようにして、確実に点数につなげていきたいですねえ。

追記

ハマった問題出てきた。チケット切ってたyumechiさん有能。

github.com

ABC073 の D問題の件だった。

CPP - WA : http://abc073.contest.atcoder.jp/submissions/1581943 - AC : http://abc073.contest.atcoder.jp/submissions/1583207

Python http://abc073.contest.atcoder.jp/submissions/1583653