AtCoder Beginner Contest 134
はい. AtCoder Beginner Contest 134 です
A,B,C,D,E の5完でした.
E で 5ペナルティー.つらい…
A - Dodecagon
入力の を して出力するだけですね.
#include <iostream> #include <vector> #include <utility> #include <map> #include <algorithm> #include <queue> #include <cmath> using namespace std; int main() { int r; cin >> r; cout << 3*r*r << endl; }
B - Golden Apple
監視員は前後 マス見えるんだから,1人の監視員でカバーできる範囲は .
だから,それで を割って,切り上げをしたら答えが出る.
#include <iostream> #include <vector> #include <utility> #include <map> #include <algorithm> #include <queue> #include <cmath> using namespace std; int main() { int n,d; cin >> n >> d; cout << ceil(n/(2*d+1.0)) << endl; }
C - Exception Handling
最初,最大値と次に小さい値を持っておけば解けるじゃん〜と思っていたんだけど,
次に小さい値っていうのがちょっとめんどくさかったので sort() しちゃえ!と実装しました.
なんか sort(b.rbegin(), b.rend())
という書き方もあるっぽい?次からそれで書こう!
#include <iostream> #include <vector> #include <utility> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <numeric> using namespace std; typedef pair<int,int> P; int main() { int n; cin >> n; vector<int> a(n); vector<int> b(n); for(int i=0; i<n; i++) { cin >> a[i]; b[i] = a[i]; } sort(b.begin(),b.end(), greater<int>()); for(int i=0; i<n; i++) { if (a[i] == b[0]) { cout << b[1] << endl; } else { cout << b[0] << endl; } } }
D - Preparing Boxes
の倍数の箱に入っているボールが奇数か偶数か,みたいな問題.
から決めていけば大丈夫な感じ.
(これよく見たら存在しない場合'-1'
を出力とか書いてるけど,そんな機能つけてないよ…?)
たまたま通してしまった()
解が存在しないということがないってことかな…? こういうのは証明して「ないから必要無い」とするのは良いけど,たまたま通すのはちょっと減らしていきたいね.
iの倍数を通って行って,もしボールが入っていたら,フラグを反転させて,
未確定(-1)なら,フラグを代入する形で決定していった.
よく考えたら for(j=i+i; j<=n; j+=i)
とかしたらかけ算とかしなくて良かったかな.
#include <iostream> #include <vector> #include <utility> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <numeric> using namespace std; typedef pair<int,int> P; int main() { int n,m; m=0; cin >> n; vector<int> a(n); vector<int> b(n,-1); for(int i=0; i<n; ++i) cin >> a[i]; for(int i=n; i>0; --i) { bool f = a[i-1]; int l = n/i; for(int j=l; j>0; --j) { if(b[i*j-1] == -1) { b[i*j-1] = f; if(f) m++; break; } else { if(b[i*j-1] == 1) f = !f; } } } cout << m << endl; for(int i=0; i<n; i++) { if(b[i] >= 1) cout << i+1 << endl; } }
E - Sequence Decomposing
なぜか時間内に解けてしまいました()
グラフではないけど,1つのレーンみたいなものを作って,その後ろに積み重ねていくイメージで書いた.
ニムトっていうボードゲームっぽいな〜と思いながら書いてました.
最初は, roots
っていう変数に頭の数保存して,その列の最大値にアクセスして〜みたいなこと書いてたけど,TLE になったので,考え直しました(最初のコード).
roots
を探すループを書いていたので,それが悪いと思って vector
で列の最大値だけ管理するようにしたら通りました(REとかたくさん出したけど).
#include <iostream> #include <vector> #include <utility> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <numeric> using namespace std; template< typename T > typename std::vector<T>::iterator insert_sorted( std::vector<T> & vec, T const& item ) { return vec.insert ( std::upper_bound( vec.begin(), vec.end(), item ), item ); } int main() { int n; cin >> n; vector<int> roots; for(int i=0; i<n; i++) { int v; cin >> v; v = -1*v; if(roots.size() <= 0) { roots.push_back(v); continue; } auto index = upper_bound(roots.begin(), roots.end(), v); if(index != roots.end()) { roots.erase(index); } insert_sorted(roots,v); } cout << roots.size() << endl; }
まとめ
初めて E問題まで解けました.
ABCで初めて900位と3桁になれたので良かった.
蟻本も買ったので,今からアルゴリズムも勉強するし,もっと解けるようになるかな〜と思いました.
もっと頑張るぞ〜