ABC 111 C - /\/\/\/ - sky’s 雑記

cpp力の無さで解けず、解法わかってるのにコードに起こせないのは凹む。

初手の方針

inputを偶奇で分けてそれぞれ頻度の高いものを比較して差分を出力すればいけそうかなと思った。が、それをどう書いていいかがわからなかった。

vector<ll> v;

REP(i, n) {
  ll a;
  cin >> a;
  v[a]++;
}

vector<pair<ll, ll>> v;

REP(i, n) {
  ll a;
  cin >> a;
  v.push_back(make_pair(a, 1));
}

のようなことをやっていたんだが前者についてはa基準でvectorをsortする方法がわからず、後者についてはpairのaをfindしてincrementする方法がわからず頓挫した。

苦し紛れでvectorの各要素についてcountをしたがcountの計算量がlast-firstなので10^ 5*10^ 5でLTE

Submission #9346212 - AtCoder Beginner Contest 111

正答

vectorにkeyを配列の値,valueに値の出現数のpairをpushしてsortする。

Submission #9429873 - AtCoder Regular Contest 103

シンタックスを知っているとどうということはないんだが初出の記法は以下の2つ

逆イテレータ

降順ソートする際に使った。sort(epv.rbegin(), epv.rend()) の部分。sort(epv.begin(), epv.end(), greater<pair<ll, ll>>()) と同義。

範囲for文

コンテナクラスに対してfor文を回すシンタックス。C++11から追加された記法らしい。 kotlinでコレクションに対してforEachを回すのと同じ感覚でかけて便利そう。

C++ コンテナクラス入門