SRM511 Div1Easy Zoo
問題URL:Zoo
Markdownで書いてるから数式は手元では$…$
で書くけど、なぜかうまく反映されなくて、いちいち[tex:…]
に書き直してるっていう…
これはMarkdown関係ないけど、Tex使うとサムネ候補に数式が現れるのはやめてほしい。これのせいでサムネなしの記事も何かしらの画像(大体これ)を設定しないといけなくなる。サムネ削除ってできないのかね。
考察
はでかいな~~~~
とりあえずanswersをソートしてみる。ウサちゃんもネコちゃんも同じ身長の同種はいないとのことなので、回答に矛盾がないとき、answers={0,0,1,1,2,2,…,n,n,n+1,n+2,n+3,…,m}
になりそう。各数字へのウサギとネコの割り振り方は、
実装
answers={0,0,1,1,2,2,…,n,n,n+1,n+2,n+3,…,m}
でないものは全て弾かなければいけないので結構面倒。mapで数えたりuniqueとったりしたけど、効率のいい方法はわからない。
#include <bits/stdc++.h> using namespace std; class Zoo { public: long long theCount( vector <int> answers ){ sort(answers.begin(),answers.end()); map<int,int> mp; for(auto i:answers) mp[i]++; // 値が飛び飛び answers.erase(unique(answers.begin(),answers.end()),answers.end()); int a=answers.size(),b=answers.back(); if(a!=b+1) return 0; // 順番に並んでいるか bool flg=0; int n=b; for(auto m:mp){ int i=m.second; // 前半 if(!flg&&i!=2){ if(i==1){ flg=1; n=m.first; } else return 0; } // 後半 if(flg&&i!=1) return 0; } return pow(2,n+1); } };