ABC 032 C - 列
問題概要
省略
解法
しゃくとり法をやるだけなんだけど、すぐにうまくできない。
ミス
尺取り法バグらしまくってうまくできない。
コード
尺取り法
#include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) const int INF = 1e9; ll s[100010]; int main(void){ int n, k; cin >> n >> k; bool f = false; rep(i, n){ ll t; cin >> t; s[i] = t; if(t == 0)f = true; } if(f){//1つでも0が含まれていれば、長さ n にできる printf("%d\n", n); return 0; } int ans = 0; int l = 0, r = 0; ll acc = 1; while(r < n){ while(r < n && acc * s[r] <= k){ acc *= s[r]; r++; } ans = max(ans, r - l); if(l != r){ acc /= s[l]; l++; }else{ l++; r++; } } printf("%d\n", ans); return 0; }
segtree + 尺取り法
#include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) const int INF = 1e9; const int MAX_N = 1 << 18; int size; ll seg[MAX_N * 2];//segは欲しい情報 struct segtree{ segtree(int n){ size = 1; while(size < n) size *= 2;//要素数を2のべき乗に } void update(int k, ll v){//k番目の値をvに変更 k += size - 1; seg[k] = v; //上りながら更新 while(k > 0){ k = (k - 1) / 2; seg[k] = seg[k * 2 + 1] * seg[k * 2 + 2]; } } //[a, b)の積を求める ll query(int a, int b, int k = 0, int l = 0, int r = size){ if(r <= a || b <= l) return 1;//積に影響を与えない 1 if(a <= l && r <= b) return seg[k]; ll x = query(a, b, k * 2 + 1, l, (l + r) / 2);//左の子の積 ll y = query(a, b, k * 2 + 2, (l + r) / 2, r);//右の子の積 return x * y; } }; int main(void){ int n, k; cin >> n >> k; segtree st(n); bool f = false; rep(i, n){ ll t; cin >> t; if(t == 0)f = true; st.update(i, t); } if(f){//1つでも0が含まれていれば、長さ n にできる printf("%d\n", n); return 0; } int ans = 0; //[l, r)の長さが最大となるところを求める。 int r = 1; rep(l, n){//左を1つ縮める while(!(l < r))r++;//lがrを超えないように while(r <= n && st.query(l, r) <= k) r++;//左を固定して、右を伸ばせるだけのばす ans = max(ans, r - l - 1);//[l, r - 1]が条件を満たしている } printf("%d\n", ans); return 0; }
この実装がわかりやすいかも
#include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) const int INF = 1e9; ll s[100010]; int main(void){ int n, k; cin >> n >> k; bool f = false; rep(i, n){ ll t; cin >> t; s[i] = t; if(t == 0)f = true; } if(f){//1つでも0が含まれていれば、長さ n にできる printf("%d\n", n); return 0; } if(k == 0){ printf("0\n"); return 0; } int ans = 0; int l = 0, r = 0; ll acc = 1; //[l, r] while(1){ if(acc <= k){//右を進める ans 答えを更新 ans = max(ans, r - l); if(r == n) break; acc *= s[r++]; }else{ acc /= s[l++]; } } printf("%d\n", ans); return 0; }