Codeforces Round #171 (Div. 2)
期末が出来なさすぎて冷えきっています。
Div1復帰。Div1に残れる実力をつけなければ....
A. 初め問題文間違っていてimfだった 適当に実装. なんでAでこんな書いたんだ...
const int dx[] = {1,0,-1,0}; const int dy[] = {0,1,0,-1}; int x, y, k = 1, dir; int ans; int main(){ cin >> x >> y; int a = 0, b = 0; while(a != x || b != y){ rep(i, 2){ if(a == x && b == y){ cout << ans << endl; return 0; } rep(j, k){ if(a == x && b == y){ cout << ans << endl; return 0; } a += dx[dir]; b += dy[dir]; } dir = (dir + 1) % 4; if(a == x && b == y){ cout << ans << endl; return 0; } ans++; } k++; rep(i, 2){ if(a == x && b == y){ cout << ans << endl; return 0; } rep(j, k){ if(a == x && b == y){ cout << ans << endl; return 0; } a += dx[dir]; b += dy[dir]; } dir = (dir + 1) % 4; if(a == x && b == y){ cout << ans << endl; return 0; } ans++; } k++; } cout << ans << endl; return 0; }
B. しゃくとりやるだけ
int n, t; int a[100010]; int ans; int main(){ cin >> n >> t; rep(i, n) cin >> a[i]; int s = 0, e = 0; int sum = 0; while(true){ while(sum <= t - a[e] && e < n){ sum += a[e]; e++; } ans = max(ans, e - s); sum -= a[s]; s++; if(e == n) break; } cout << ans << endl; return 0; }
C. 区間の増減性を持つsegtreeを建てて適当に2分探索.
#define SZ (1 << 20) int n, m; int a[100010]; struct segtree{ bool dat[SZ * 2]; void init(){ memset(dat, false, sizeof(dat)); } inline void update(int k, bool fl){ k += SZ - 1; dat[k] = fl; while(k > 0){ k = (k - 1) / 2; dat[k] = dat[k * 2 + 1] && dat[k * 2 + 2]; } } bool query(int a, int b, int k = 0, int l = 0, int r = SZ){ if(r <= a || b <= l) return true; if(a <= l && r <= b) return dat[k]; bool lc = query(a, b, k * 2 + 1, l, (l + r) / 2); bool rc = query(a, b, k * 2 + 2, (l + r) / 2, r); return lc && rc; } }; segtree inc, de; int main(){ cin >> n >> m; rep(i, n) cin >> a[i]; inc.init(); de.init(); rep(i, n - 1){ if(a[i] <= a[i + 1]) inc.update(i, true); if(a[i] >= a[i + 1]) de.update(i, true); } rep(i, m){ int p, q; cin >> p >> q; --p; --q; int lb = p - 1, ub = q + 1; while(ub - lb > 1){ int mid = (ub + lb) / 2; if(inc.query(p, mid)) lb = mid; else ub = mid; } if(de.query(lb, q)) cout << "Yes" << endl; else cout << "No" << endl; } /* rep(i, n){ for(int j = i; j < n; ++j){ int p = i; int q = j; cout << i + 1 << " " << j + 1 << " "; int lb = p - 1, ub = q + 1; while(ub - lb > 1){ int mid = (ub + lb) / 2; if(inc.query(p, mid)) lb = mid; else ub = mid; } cout << lb << " "; if(de.query(lb, q)) cout << "Yes" << endl; else cout << "No" << endl; } } */ return 0; }
D. 見てない。bitDPらしい。こわい
Eは既出らしいけど知らない。greedy