Codeforces Round #FF (Div. 2)
0xFF = 255
ooo-- 296th rating: 1639(+69)
AB早解きでCはアドホックでした.CがバグりやすかったようでDiv1Aとして解いた人も結構落としてた.
アルゴリズムの勝負はDからだったと思うのでその段階で勝負できるようになりたいな…
A
テストのためにwhile (cin >> p >> n)
と書いているのにcontinue
のところをbreak
にしていたせいで3回WAする.なかなかこのミスに気づけず諦めて最後に回した.結局ACできたのは開始110分後になってしまった.
国内予選のC問題といいくだらないミスで数十分潰す案件が続いてる.
int main(){ ll n, p; while (cin >> p >> n){ set<ll> s; int ans = -1; rep(i, n){ ll x; cin >> x; ll h = x%p; auto t = s.insert(h); if (t.second) continue; else if (ans == -1) ans = i+1; } cout << ans << endl; } }
B
最も価値が大きいアルファベットを求め,それをの後ろに個付け足したものが答えとなる.
int main(){ string s; cin >> s; int k; cin >> k; char c = 'a'; int score = 0; map<char, int> m; loop(i, 'a', 'z' + 1){ int t; cin >> t; m[i] = t; if (t > score){ score = t; c = i; } } s += string(k, c); int ans = 0; rep(i, s.size()){ ans += m[s[i]] * (i + 1); } cout << ans << endl; }
C
番目以降で連続して増加する列の長さと以前で連続して増加する列の長さを予め求め, 最後にの最大値を求める.数列の長さが2以下の場合,先頭か末尾を変更する場合,差が1しかない場合など 結構引っかかった.
int main(){ int n; while (cin >> n){ if (n == 1 || n == 2){ cout << n << endl; return 0; } vll a(n); vll before(n, 1); vll after(n, 1); rep(i, n){ cin >> a[i]; } for (int i = 1; i < n; i++){ if (a[i - 1] < a[i]){ before[i] = before[i - 1] + 1; } } for (int i = n - 2; i >= 0; i--){ if (a[i] < a[i + 1]){ after[i] = after[i + 1] + 1; } } ll ans = after[1] + 1; // change a[0] ans = max(ans, before[n - 2] + 1); // change a.back() for (int i = 1; i + 1 < n; i++){ if (a[i - 1] + 1 < a[i + 1]){ ans = max(ans, before[i - 1] + after[i + 1] + 1); } else { ans = max(ans, before[i - 1] + 1); ans = max(ans, after[i + 1] + 1); } } //cout << a << endl; //cout << before << endl; //cout << after << endl; cout << ans << endl; } }
D
今取れる最大の行or列を取る貪欲を書いていたけど,手で解いたのと合わないケースが出てきたので諦めた.