CF 222A Shooshuns and Sequence
#137div2 A問題。
Problem - 222A - Codeforces
なんだかちょっとだけ苦戦した。
後で調べたらシミュレートでもできるらしい。
Codeforces Round #137 (Div. 2) A : Shooshuns and Sequence - komiyamの日記
Codeforces 222 A. Shooshuns and Sequence - simezi_tanの日記
でも、もうちょっと考えて書いてみた。
例えば、どんな入力なら大丈夫かというと、
3 2
3 1 1
みたいに、k番目以上先が全部同じなら、前のが全部消えていくから大丈夫。
逆に、そうでないならだめ。なぜなら、いくらやっても違うのが入っていくから。
次に何回繰り返せばいいかいうことを考える。
これは、前から何個消せばいいかということと同じこと。
後ろは同じのがぐるぐる回ってるだけだから。
1 2 3 3 3 3
で、k=4ならば、最初からふたつ、1と2を消せばいい。
だから出力は2.
という感じで実装してみた
#include <iostream> #include <iomanip> #include <vector> #include <map> #include <set> #include <queue> #include <numeric> #include <algorithm> #include <functional> #include <cctype> #include <complex> #include <string> #include <sstream> #define push_back pb #define all(c) c.begin(),c.end() #define rep(i,n) for(int i=0;i<(n);i++) #define tr(container, it) \ for(typeof(container.begin()) it = container.begin(); it != container.end(); ++it) #define present(container, element) (container.find(element) != container.end()) #define cpresent(container, element) (find(all(container),element) != container.end()) #define sz(a) ((int)a.size()) typedef long long ll; const int dx[] = {1,0,-1,0}; const int dy[] = {0,-1,0,1}; const double EPS = 1e-9; using namespace std; int main(){ int n,k; cin >> n >> k; vector<int> V(n); rep(i,n) cin >> V[i]; k--; int x = V[k]; for(int a=k;a<n;a++){ if(x==V[a]) continue; cout << "-1" << endl; return 0; } int r = 0; for(int a=k-1;a>=0;a--){ if(V[a] == x) r++; else break; } cout << k-r << endl; return 0; }