c++初心者の自分が知らなかったことがあったので、メモ。
やること自体は解説に書いてある通りで、リストを2つに分けてソートして、条件をみたすものができているかどうかを判断する。条件をみたすかどうかは、リストAの最大値がリストBの最小値よりも大きく、かつリストAの最小値がKであること、である。
ここでリストの中にある最大値の要素、最小値の要素の求め方であるが、max_element, min_elementというメソッドがあることを知った。これを使うと容易にリストの中身を取ってこれそうである。以下のリンクを参考にしたが、配列の添字も取れるようだ。
参照:
忘れがちな C++ の標準ライブラリの使い方 - Qiita
ただ、どうも自分の手元でセグメンテーション違反が発生しているので、いろいろ試していたところこのメソッド、リストの中身が空だとセグメンテーション違反で落ちることが確認された。使うときは要注意だなあ…。。。
http://melpon.org/wandbox/permlink/szmS9fP8NpvGYYOX
というわけで回答したコードはこんな感じになりました。(ヘッダーやdefine部分はカットしているのでご了承ください)
#117012 No.411 昇順昇順ソート - yukicoder
int main(){ cin.tie(0); ios::sync_with_stdio(false); cout.precision(16); int n, k; cin >> n >> k; ll ans = 0; vector<int> list; REP(i, n) list.pb(i + 1); ll limit = 1; REP(i, n) limit *= 2; REP(i, limit) { vector<int> l1 = {}; vector<int> l2 = {}; int bitnum = i; REP(j, n) { ((bitnum & 1) == 1 ? l1 : l2).pb(list[j]); bitnum >>= 1; } sort(l1.begin(), l1.end()); sort(l2.begin(), l2.end()); if(l1.size() == 0 || l2.size() == 0) continue; int l1max = *max_element(l1.begin(), l1.end()); int l2min = *min_element(l2.begin(), l2.end()); if(l1max > l2min && l1[0] == k) ans++; } #if DEBUG cout << "** RESULT **" << endl; // debug #endif cout << ans << endl; }
|