AOJ 0517 Longest Steps
前に一度解いた問題なのですがたまたま開いて解きたくなったのでもう一度解きました。
解法
連続で現れる個数をvectorで管理して白いカードがあったら2つの連続する区間どうしの間が1の区間の合計+1をvectorの中に投げ入れました。前解いた時のソースを見ると前のほうが簡潔でわかりやすいという残念なことになってました…(0を分けてvectorに突っ込んでいるので場合分けが不要になる)前のほうが頭良かったみたいです
この問題は本選2番なのでさらっとACしたい問題です。
前回のソースコード
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <complex> #include <string> #include <sstream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <functional> #include <iostream> #include <map> #include <set> using namespace std; typedef pair<int,int> P; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; #define pu push #define pb push_back #define mp make_pair #define eps 1e-9 #define INF 2000000000 #define sz(x) ((int)(x).size()) #define fi first #define sec second #define EQ(a,b) (abs((a)-(b))<EPS) vi sq; vi sqa; bool w[100100]; int main() { while(1) { int n,k; int ans=0; cin >> n >> k; sqa.clear(); sq.clear(); memset(w,false,sizeof(w)); if(n==0&&k==0)break; bool flag=false; for(int i=0;i<k;i++) { int c; cin >> c; if(c==0) { flag=true; continue; } w[c]=true; } int cnt=0; for(int i=1;i<=n;i++) { if(w[i]) { cnt++; } else { sq.pb(cnt); cnt=0; } } sq.pb(cnt); if(!(flag)) { for(int i=0;i<sz(sq);i++) { ans=max(ans,sq[i]); } cout << ans << endl; } else { for(int i=0;i<sz(sq)-1;i++) { sqa.pb(sq[i]+sq[i+1]); } sort(sqa.begin(),sqa.end(),greater<int>()); cout << sqa[0]+1 << endl; } } return 0; }
今回のソースコード
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <complex> #include <string> #include <sstream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <functional> #include <iostream> #include <map> #include <set> using namespace std; typedef pair<int,int> P; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; #define pu push #define pb push_back #define mp make_pair #define eps 1e-9 #define INF 2000000000 #define sz(x) ((int)(x).size()) #define fi first #define sec second #define SORT(x) sort((x).begin(),(x).end()) #define all(x) (x).begin(),(x).end() #define EQ(a,b) (abs((a)-(b))<EPS) bool white=false; bool cards[100010]; int main() { while(1) { int n,k; white=false; memset(cards,0,sizeof(cards)); cin >> n >> k; if(n==0&&k==0)break; for(int i=0;i<k;i++) { int a; cin >> a; if(a==0)white=true; else cards[a]=true; } int count1=0,count2=0; vector<int> vec; int start=0; int end=0; for(int i=1;i<=n;i++) { if(cards[i]) { if(count2==0)count1++; else { if(start==0)start=1; end=1; vec.pb(count2); count2=0; count1++; } } else { if(count1==0)count2++; else { if(start==0)start=2; end=2; vec.pb(count1); count1=0; count2++; } } } if(end==1) { vec.pb(count1); vec.pb(count2); } if(end==2) { vec.pb(count2); vec.pb(count1); } vector<int> ans; if(start==1) { for(int i=0;i<vec.size();i++) { if(white) { if(i%2==0) { if(i==0||i==vec.size()-1)continue; if(vec[i]==1)ans.pb(vec[i-1]+vec[i+1]+1); } } if(i%2==1) { ans.pb(vec[i]); } } } if(start==2) { for(int i=0;i<vec.size();i++) { if(white) { if(i%2==1) { if(i==vec.size()-1)continue; if(vec[i]==1)ans.pb(vec[i-1]+vec[i+1]+1); } } if(i%2==0) { ans.pb(vec[i]); } } } SORT(ans); cout << ans[ans.size()-1] << endl; } return 0; }