Codeforces です。先ほどシステムテストが終わりました。ということで、たまには記事にしてみようと思いました。

A と B はシステムテスト通過、 C はプレテスト落ち、 D と E は問題見てないです。問題見たところだけ。

まずは A 。何枚かのコインを、片方がもう片方より大きい金額になるように二つに分けるときに、金額が大きくなる方の最小の枚数を答える、みたいな問題です。

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<numeric>

using namespace std;

int main(void) {
	int n, tmp;
	vector<int> a;
	vector<int>::iterator it;
	int i;

	cin >> n;
	for(i = 0; i < n; i++) {
		cin >> tmp;
		a.push_back(tmp);
	}
	sort(a.begin(), a.end(), greater<int>());

	tmp = 1;
	it = a.begin();
	while(it != a.end()) {
		++it;
		if(accumulate(a.begin(), it, 0) > accumulate(it, a.end(), 0)) { break; }
		tmp++;
	}

	cout << tmp << endl;

	return 0;
}

vector に入れ降順ソートして、先頭からイテレータ（のひとつ前）までとイテレータから最後までの二つでそれぞれ合計して、前者が後者を超えた瞬間の、前者の要素数を出力するようにしました。

次は B 。チケットに書いてある番号が幸せか否かみたいなやつです。英文が全然読めなかったので、ほとんど雰囲気ですが、要は数字を半分に分けたうちの前半の数字と後半の数字を全て一対一で関連付けて、それらが全て「前半のある数字＜後半のある数字」または「前半のとある数字＞後半のある数字」になればよい、みたいな感じだと思います。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(void) {
	int n;
	string num;
	vector<int> first, second;
	bool flg1, flg2;
	int i;

	cin >> n;
	cin >> num;
	for(i = 0; i < n; i++) {
		first.push_back( num[i]-'0' );
		second.push_back( num[n+i]-'0' );
	}
	sort(first.begin(), first.end());
	sort(second.begin(), second.end());
	flg1 = true; flg2 = true;
	for(i = 0; i < n; i++) {
		if(first[i] >= second[i]) { flg1 = false; }
		if(first[i] <= second[i]) { flg2 = false; }
		
	}
	if(flg1 || flg2) { cout << "YES" << endl; }
	else { cout << "NO" << endl; }

	return 0;
}

まずは string で入力を受けて、それらを前半部、後半部で int な vector に突っ込んで、それぞれ昇順ソートします。そうして、 vector を前から比較していって、前半部が後半部以上だったら flg1 を false に、後半部が前半部以上だったら flg2 を false に、というように、要は全てが前半部のほうが大きい（後半部のほうが小さい）組み合わせになっているか、または後半部のほうが大きい（前半部のほうが小さい）組み合わせになっているかというのをチェックして、どちらかが true であれば（両方 true ってのはないですね） YES 、そうでなければ NO を出力します。

次は C 。これは時間内では解けなかったのですが、終了 9 分後に完成したので（汗）。 n 個数字を受けて、それらの数字を 2 つ組み合わせた組を全通り出して、辞書順ソートしたときに k 番目に来る組み合わせは何か、みたいな問題です。問題的には B より簡単だと思いました。先にやればよかった・・・。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(void) {
	long long n, k, tmp, p1, p2, same;
	vector<long long> a;
	long long i;

	cin >> n >> k;
	for(i = 0; i < n; i++) {
		cin >> tmp;
		a.push_back(tmp);
	}
	sort(a.begin(), a.end());
	p1 = (k-1)/n;
	same = 1;
	for(i = 1; a[p1+i] == a[p1]; i++);
	same += i - 1;
	for(i = 1; a[p1-i] == a[p1]; i++);
	same += i - 1;
	p2 = ((k-1)%n + (i-1)*n) / same;
	cout << a[p1] << " " << a[p2] << endl;

	return 0;
}

入力を受けて、 vector に突っ込んで、昇順ソートして、あとは計算ですね。一つ目の数字は単純に k / n 番目の vector の要素を出してやればおｋです。添え字的には -1 ですね。二つ目の数字が若干厄介で、基本的には k / n の余り、 k % n で良いのですが、同じ数字が入力された時の処理が多少面倒です。それで引っかかってました・・・。まあ、あれこれ考えた結果、ソースコードにあるような式になりました。僕に文章校正能力がないので説明は割愛しますが、どういう順番に並ぶか紙に書いてみればわかると思います。

今回は非常に、英語に苦労させられた感があります。英語の勉強が必要ですね・・・。ということで、以上、今回の Codeforces でした。

Tweet