水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

No.411 昇順昇順ソート

c++初心者の自分が知らなかったことがあったので、メモ。

No.411 昇順昇順ソート - yukicoder


やること自体は解説に書いてある通りで、リストを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;
}

|