AtCoder Beginner Contest 141
はい. AtCoder Beginner Contest 141 です
既にもう覚えていません. 過去の僕の気持ちになって書きます.
ABCDの4完でした.
A - Weather Prediction
書きやすさ重視で実装しました.
#include <iostream> #include <vector> #include <utility> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <string> using namespace std; int main() { string s; string ans; cin >> s; if (s == "Sunny") ans = "Cloudy"; if (s == "Cloudy") ans = "Rainy"; if (s == "Rainy") ans = "Sunny"; cout << ans << endl; }
B - Tap Dance
奇数のときに 'L',偶数のときに 'R'が来るとダメという感じ.
0-indexdなので偶奇が入れ替わりますが,そのまま実装しました.
#include <iostream> #include <vector> #include <utility> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <string> using namespace std; int main() { string s; cin >> s; int n = s.size(); bool ans = true; for (int i=0; i<n; i++) { if (i%2 && s[i]=='R') ans = false; if (!(i%2) && s[i]=='L') ans = false; } cout << (ans? "Yes" : "No") << endl; }
C - Attack Survival
基本的に 回問題が出されるので, 点の失点です.
ただし,答えた回数分は点数がもらえるのでその分を引いて, を超えれば勝ち抜けです.
#include <iostream> #include <vector> #include <utility> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <string> using namespace std; int main() { long n,k,q; cin >> n >> k >> q; vector<long> a(n+1,0); for (int i=0; i<q; i++) { int ai; cin >> ai; a[ai]++; } for (int i=1; i<=n; i++) { bool ans = (q-a[i] < k); cout << (ans? "Yes" : "No") << endl; } }
D - Powerful Discount Tickets
できるだけ高いものに割引券を使いたいので, priority_queue に突っ込んで大きい奴に割引券を使って priority_queue に戻します.
これを 回繰り返して,総和を取ると最小の合計金額が求まります.
#include <iostream> #include <vector> #include <utility> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <string> using namespace std; int main() { int n,m; cin >> n >> m; priority_queue<long> q; for (int i=0; i<n; i++) { int a; cin >> a; q.push(a); } for (int i=0; i<m; i++) { int a = q.top(); q.pop(); // cerr << a << " " << (int)((double)a/2.0) << endl; q.push((int)((double)a/2.0)); } long ans = 0; while(! q.empty()) { ans += q.top(); q.pop(); } cout << ans << endl; }
E - Who Says a Pun?
コンテスト中に「文字列アルゴリズムだ!」と Suffix-Array を検索して使ってみたんですが,ダメでした. コンテスト後に Z-algorithm をコピペでやってみたら解けました.
Suffix-Array でも解けたようなので, Suffix-Array も勉強したいと思います.
#include <iostream> #include <vector> #include <utility> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <string> #include <numeric> using namespace std; vector<long> z_algorithm(const std::string& s, const long n){ std::vector<long> z(n, 0); long L=0, R=0; for (long i=1; i<n; i++){ if(i>R) { L = R = i; while(R<n && s[R-L]==s[R]) R++; z[i] = R-L; R--; } else { long k = i-L; if(z[k] < R-i+1){ z[i] = z[k]; } else { L = i; while(R<n && s[R-L]==s[R]) R++; z[i] = R-L; R--; } } } return z; } int main() { int n; long ans = 0; string s; cin >> n >> s; vector<long> z; for (int i=0; i<n-1; i++) { z = z_algorithm( s.substr(i, n-i), n-i); for (long j=1; j<n-i; j++) { ans = max(ans, min(z[j],j)); } } cout << ans << endl; }
まとめ
パフォーマンスが1200代だったのでまぁまぁ良いですね.
この調子で頑張ります。