SRM 511 div1 easy:Zoo
SRM練習会に参加しました。easyとmedを提出したんですがmedは落ちました。このころのtopcoderはサンプルが弱い気がする。
問題
ウサギとネコがいて,それぞれの動物に「自分と同じ種族で,自分より背の高い動物が何匹いるか」を質問する(すべての動物は背の高さが異なるとする)。
この質問の答え方をするような各動物の種類の構成の仕方は何通りあるか。
解法
各動物の質問に対する答え方は以下のようになるしかありません。
動物1 0, 1, 2, ..., k
動物2 0, 1, 2, ..., k, k+1, ..., l
このような構成にならなかったら0を返します。
このような構成になった場合は,0, 1, ..., kと答えた動物がそれぞれウサギかネコかで2通りの可能性があるのでまず通りはあります。
また,の場合,どちらの種族が多くいるか(どちらがl匹いる動物になるか)でさらに2通りの可能性があるので答えはさらに2倍になります。
以下ソースコード(かなり読みづらいと思います)
int kind[2][44]; class Zoo { public: long long theCount(vector <int> answers) { memset(kind, 0, sizeof(kind)); for (int el : answers) { if (kind[0][el] > 0) { if (kind[1][el] > 0) return 0; kind[1][el]++; } else { kind[0][el]++; } } int cur = -1; for (int i = 0; i <= 40; i++) { if (kind[0][i] && kind[1][i]) cur = i; else break; } cout << cur << endl; int last1 = cur; for (int i = cur+1; i <= 40; i++) { if (kind[0][i]) last1 = i; else break; } cout << last1 << endl; for (int i = last1+1; i <= 40; i++) { if (kind[0][i]) return 0; } for (int i = cur+1; i <= 40; i++) { if (kind[1][i]) return 0; } if (cur == -1) return 2; ll ans = 1; for (int i = 0; i <= cur; i++) ans *= 2; if (last1 != cur) ans *= 2; return ans; } };