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桁になれたので良かった.
蟻本も買ったので,今からアルゴリズムも勉強するし,もっと解けるようになるかな〜と思いました.
もっと頑張るぞ〜
AtCoder Beginner Contest 133
はい. AtCoder Beginner Contest 133 です
C問題沼りましたが,4完でした.
A - T or T
電車かタクシーかどちらが安いかという問題.
単純に と のどちらか小さい方を出力するだけ.
#include <iostream> #include <vector> #include <algorithm> #include <utility> #include <queue> using namespace std; int main() { int n,a,b; cin >> n >> a >> b; cout << min(n*a, b) << endl; }
B - Bite Eating
問題文の通りに計算しました.
整数の判定ぱっと思いついたものが,ceil()
と floor()
して,同じなら〜と思ったんだけど,
他の人のソース見てみたら, sum == (int)sum
みたいなことしていて,そっちの方が良いな〜と思いました.
#include <iostream> #include <vector> #include <algorithm> #include <utility> #include <queue> #include <cmath> using namespace std; int main() { int n,d; int count=0; cin >> n >> d; vector< vector<int> > x (n+10, vector<int>(d+10)); for(int i=0; i<n; i++) { for(int j=0; j<d; j++) { cin >> x[i][j]; } } for(int i=0; i<n; i++) { for(int j=i+1; j<n; j++) { double sum = 0.0; for(int k=0; k<d; k++) { sum += pow((abs(x[i][k] - x[j][k])), 2); } sum = sqrt(sum); if ( ceil(sum) == floor(sum) ) { count++; } } } cout << count << endl; }
C - Remainder Minimization 2019
割った余りなので,単純に l %= 2019; r %= 2019
して,[l,r] で探索したら良いかな〜と思ったんだけど,
それだと,1周(以上)している場合に判定できないな といろいろやっていたら沼りました.
#include <iostream> #include <vector> #include <algorithm> #include <utility> #include <queue> #include <cmath> using namespace std; const long mod = 2019; int main() { long l,r; cin >> l >> r; long ldiv = (l-1) / mod; long rdiv = r / mod; if ( rdiv - ldiv > 0 ) { puts("0"); return 0; } l%=mod; r%=mod; long ans = 3000; for (long i=l; i<=r; i++) { for(long j=i+1; j<=r; j++) { ans = min(ans, (i*j)%mod); } } cout << ans << endl; }
最初に
if ( r-l >= 2019 ) { puts("0"); return 0; }
とかやってたんだけど,そっちの方が良かった.
D - Rain Flows into Dams
「なんだこの問題…」と思っていました(Cが解けなくてD来てよく分からん…と何度か往復しました).
最初に考えたのは,連立方程式をたてて,行列で解く方法なんだけど,
なんとなくダメそうな気がして辞めました.
その連立方程式を足したり引いたりしたら,解けるのでは?と考えていたら解けました.
こんな感じの式がたてられるんだけど 分母の2が邪魔なので,全体に2をかけて.
のとき,全体としては以下の感じ.
1行目の式から,2行目の式を引いて,
さらにその式に3行目の式を足して,
という感じで, が求められる.が決まったら後は,
という感じ.
#include <iostream> #include <vector> #include <algorithm> #include <utility> #include <queue> #include <cmath> using namespace std; const long mod = 2019; int main() { long n; cin >> n; vector<long> a(n); vector<long> x(n); x[0] = 0; for(long i=0; i<n; i++) { cin >> a[i]; if (i%2==0){ x[0] += a[i]; } else { x[0] -= a[i]; } } cout << x[0] << " "; for(long i=1; i<n; i++) { x[i] = a[i-1]*2 - x[i-1]; cout << x[i] << " "; } cout << endl; }
E - Friendships
残り15分くらいで読んだけどよく分かりませんでした.
解説を聞きながら寝たんだけどなんか を使うらしい.
解けたら追記します.
まとめ
4完で,緑パフォーマンスだったので,最近の成績から言えば悪くなかったですね. C問題沼らなければ,もう少しパフォーマンス出たのかなぁ〜と思うので,もっと勉強しなくては!
AtCoder Beginner Contest 131
はい. AtCoder Beginner Contest 131 です
久しぶりに参加したので,ちゃんと解けるか不安だったけど, A,B,C,D は解けました.
E も解けそうだったけど,時間が足りませんでした( C に時間をかけ過ぎた).
A - Security
char で取って1つ前を保存しておきました.
#include <iostream> #include <vector> #include <algorithm> #include <iomanip> #include <string> using namespace std; int main(void) { char c1,c2; c2 = '-'; bool f = false; for(int i=0; i<4; i++) { cin >> c1; if ( f || c1 == c2 ) { f = true; } c2 = c1; } cout << (f? "Bad" : "Good") << endl; }
B - Bite Eating
愚直に計算しつつ,絶対値の小さいものを保存しておきました.
#include <iostream> #include <vector> #include <algorithm> #include <iomanip> #include <string> using namespace std; int main(void) { int n,l; int eat = 999; int sum = 0; cin >> n >> l; for(int i=1; i<=n; i++) { sum += l + i - 1; if( abs(eat) > abs(l+i-1) ) { eat = l+i-1; } } cout << sum - eat << endl; }
C - Anti-Division
a未満の c,dで割りきれる数と b以下の割り切れる数を求めて引き算したら解けました.
最初 (b-a) で range を取ってごにょごにょしていたんですが,それではダメでした
(本当にこの方法で良いのか疑問を持ちながら書いていたので,まぁ当たり前と言えば当たり前でした)
この手の問題は,問題集とかにも載っているらしく,時間かかってしまったのは,ちょっと残念ですね.
#include <iostream> #include <vector> #include <algorithm> #include <iomanip> #include <string> #include <cmath> using namespace std; long long gcd(long long a,long long b){ if (a%b==0){ return(b); } else{ return(gcd(b,a%b)); } } int main(void) { long long a,b,c,d; cin >> a >> b >> c >> d; long long ans1,ans2; long long GCD = gcd(c,d); a--; ans1 = a/c + a/d - a/((c*d)/GCD); ans2 = b/c + b/d - b/((c*d)/GCD); cout << (b-a) - (ans2 - ans1) << endl; }
D - Megalomania
期限の短い順に並べて,処理していけば 時間内に仕事が終わるかどうか分かります.
C より簡単なのでは…?
なんか compare の関数内側に書く方が良さそうなんだけど,書き方を覚えていなかったので外側に書くことになってしまった.
pair をほとんど調べずに進められたので,成長を感じました.
最初,期限の長いものから引き算していったので,変数名とかがそこに引きずられて残念な感じになっています…
#include <iostream> #include <vector> #include <algorithm> #include <iomanip> #include <string> #include <cmath> #include <utility> using namespace std; bool compare(pair<long long, long long> i1, pair<long long, long long> i2) { if ( i1.second == i2.second) return i1.first > i2.first; return (i1.second < i2.second); } int main(void) { long long n; cin >> n; vector< pair<long long, long long> > ab; for (long long i=0; i<n; i++) { long long tmp1,tmp2; cin >> tmp1 >> tmp2; ab.push_back( make_pair(tmp1,tmp2)); } sort(ab.begin(), ab.end(), compare); long long max = 0; for (long long i=0; i<n; i++) { if ( max+ab[i].first > ab[i].second ) { cout << "No" << endl; return 0; } max += ab[i].first; } cout << "Yes" << endl; }
E - Friendships
これもそんなに難しく無さそう…(希望的観測)
もう少し時間があったら解けた気もしますが,とりあえず解けませんでした.
勉強して書けたら追記します.
まとめ
今回は A,B,C,D 解けて,E もある程度解けそうだったので悪くないかもと思ったのですが,順位的には微妙でした.
次回はもっとレートを上げられるように頑張ります!
AtCoder Beginner Contest 128
はい. AtCoder Beginner Contest 128 です
今回は酷い.
AC になったのは, A と B だけでした(:3」∠)
とりあえず,この2つをまとめておきます.
C以降は勉強して解けたら追記していきます.
A - Apple Pie
問題文
リンゴが 3 つの欠片になるのだから,足して割るだけ.
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; int main(void) { int a,p; cin >> a >> p; cout << (a*3+p)/2 << endl; }
B - Guidebook
問題文
index 置いてソートするだけ.
#include <iostream> #include <vector> #include <utility> #include <string> #include <numeric> #include <algorithm> using namespace std; int main(void) { long n; vector< pair<string, int> > ass; cin >> n; for (long i=0; i<n; i++) { pair<string, int> tmp; cin >> tmp.first >> tmp.second; ass.push_back(tmp); } vector<int> index(ass.size()); iota(index.begin(), index.end(), 0); sort(index.begin(), index.end(), [&](long x, long y){if( ass[x].first != ass[y].first) return ass[x].first<ass[y].first; return ass[x].second>ass[y].second;} ); sort(ass.begin(), ass.end()); for(auto i: index){ cout << i+1 << endl; } }
C問題以上は,明日以降にちゃんと考えて解いたら追記します.
AtCoder Beginner Contest 127
はい. AtCoder Beginner Contest 127 です
今回は縛りプレイじゃないです(だからといって順位は高くないです).
A - Ferris Wheel
問題文
はい.問題文の通りに実装しました.
#include <iostream> using namespace std; int main() { int a,b; cin >> a >> b; if ( a <= 5 ) { b = 0; } else if ( a <= 12 ) { b /= 2; } cout << b << endl; }
B - Algae
問題文
for文ぶん回すだけ…?
#include <iostream> using namespace std; int main() { long long r,d,x; cin >> r >> d >> x; for(long long i=0; i<10; i++) { cout << (x=r*x-d) << endl; } }
C - Prison
問題文
Lの最大値と Rの最小値を求めれば良いだろ〜って感じで書いた.
これ,LとRすれ違うこともあるよなぁとか思いつつもそのまま出してしまって WA
即 if文を書き足して AC
#include <iostream> #include <algorithm> using namespace std; int main() { long long n,m; cin >> n >> m; long long nmax=-1; long long nmin=9999999999; for(long long i=0; i<m; i++) { long long l,r; cin >> l >> r; nmax = max(nmax, l); nmin = min(nmin, r); } long long ans = abs(nmin - nmax) + 1; if ( nmin < nmax ) { ans = 0; } cout << ans << endl; }
D - Integer Cards
問題文
ソートして小さい方から書き換えて行けば良いのでは?という感じ.
入れ子な vector のソート慣れてなくて時間がかかった.
#include <iostream> #include <algorithm> #include <numeric> #include <vector> using namespace std; bool compare(vector<long long> i1, vector<long long> i2) { return (i1[1] > i2[1]); } int main() { long long n,m; vector<long long> a; vector<vector<long long> > bc; cin >> n >> m; for(long long i=0; i<n; i++) { long long tmp; cin >> tmp; a.push_back(tmp); } for(long long i=0; i<m; i++) { long long tmp; vector<long long> vtmp; cin >> tmp; vtmp.push_back(tmp); cin >> tmp; vtmp.push_back(tmp); bc.push_back(vtmp); } sort(a.begin(), a.end()); sort(bc.begin(), bc.end(), compare); long long i,j; i = j = 0; while( a[i] < bc[j][1] ) { if( bc[j][0] > 0 ) { a[i] = bc[j][1]; i++; if( i > n-1 ) { break; } bc[j][0]--; } else { j++; if( j > m-1 ) { break; } } } long long ans = 0; for(long long i=0; i<n; i++) ans += a[i]; cout << ans << endl; }
E - Cell Distance
問題文
最初 4C2 とか組み合わせ使うのかな〜って考えてたけど,思いつかなくて一旦 F問題へ.
戻ってきて雑に総当たり書いてみたけど,よく分からず…
#include <iostream> #include <algorithm> #include <numeric> #include <vector> using namespace std; long long mod = 1000000007; long long calc(long, long, long, long, long, long ); int main() { long n,m,k; cin >> n >> m >> k; long sum = 0; for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++ ) { sum += calc(n,m,i,j,k,1); } } cout << sum << endl; } long long calc(long n, long m, long i, long j, long k, long l) { if ( l == k ) { return 0; } long sum = 0; for (int ii=i; ii<i; ii++) { for (int jj=j+1; jj<j; jj++) { sum = (sum + calc(n,m,ii,jj,k,l+1) + abs(ii-jj)) % mod; //cout << "sum " << sum << " "; } } //cout << endl; //cout << "(" << i << "," << j << ") " << "l : " << l << endl; //cout << "sum " << sum << endl; //cout << endl; return sum; }
F - Absolute Minima
問題文
何だこの問題は…
a の最小値と a を vector に溜めておいて, 2 が来たら全部絶対値取って足せば良いかな〜とか思ってた.
ダメみたいです.
#include <iostream> #include <algorithm> #include <numeric> #include <vector> using namespace std; int main() { vector<long long> a; long amin = 9999999999; long n; long b = 0; cin >> n; for (int i=0; i<n; i++) { long q; cin >> q; // cout << "q : " << q << endl; if( q == 2 ) { long sum = 0; for (auto it : a ) { sum += abs(amin - it); } cout << amin << " " << sum + b << endl; } else { long ta,tb; cin >> ta >> tb; // cout << "a b : " << ta << " " << tb << endl; a.push_back(ta); amin = min(amin, ta); b += tb; } } }
E問題と F問題は解けなかったので,次回までに(と言っても明日なんだけど…)勉強したい(:3」∠)
AtCoder Beginner Contest 126
はい. AtCoder Beginner Contest 126 です
22:00から始めるという縛りプレイでした.
タイムはそんなに悪くないかな…
A - Changing a Character
問題文
k番目の文字を小文字にするやつ.
char型に1文字ずつ読み込んでいって,k番目なら tolower するだけでできた.
#include <iostream> using namespace std; int main(void) { int n,k; char c; cin >> n >> k; for (int i=1; i<=n; i++) { cin >> c; if ( k == i ) { c = tolower(c); } cout << c; } cout << endl; }
B - YYMM or MMYY
問題文
日付の表記判断.
2桁ずつに別けて, 1 ≦ x ≦ 12 か判断するだけ.
#include <iostream> using namespace std; int main(void) { string str; int i,j; cin >> str; bool i_f, j_f; i_f = j_f = false; i = stoi( str.substr(0,2) ); j = stoi( str.substr(2,2) ); if ( 0<i && i<=12 ) { i_f = true; } if ( 0<j && j<=12 ) { j_f = true; } if (i_f && j_f) { cout << "AMBIGUOUS" << endl; } else if ( i_f ) { cout << "MMYY" << endl; } else if ( j_f ) { cout << "YYMM" << endl; } else { cout << "NA" << endl; } }
C - Dice and Coin
問題文
確率の計算していくだけ.テキトーでいけるかなと思って書いた.
#include <iostream> using namespace std; int main(void) { long long n,k; double ans = 0.0; cin >> n >> k; for (long long i=1; i<=n; i++) { double sum = i; double tmp = n; while( sum <= k-1 ) { sum *= 2.0; tmp *= 2.0; } ans += (1.0 / tmp); } printf("%.16f\n", ans); }
すると,サンプルの2と何故か微妙に違う…
時間も無かったので,とりあえずそのまま提出しました.
解説を見るとほぼ同じプログラム…
なんと確率の分母を全部取って割り算ではなく,逐次で /=2
していた.
うーん,そんなに差が出るんか…?
#include <iostream> using namespace std; int main(void) { long long n,k; double ans = 0.0; cin >> n >> k; for (long long i=1; i<=n; i++) { double sum = i; double tmp = 1.0 / n; while( sum <= k-1 ) { sum *= 2.0; tmp /= 2.0; } ans += tmp; } // cout << ans << endl; printf("%.16f\n", ans); }
2019-05-20 追記
double
→ long double
にしたら 誤差が 1*10^{-9} 以下になりました.
D - Even Relation
問題文
はい.時間が無くて超雑に書きました.
通るわけ無いですよね.
#include <iostream> using namespace std; int main(void) { int n; int ans[100010]; bool f[100010]; for (int i=0; i<10000; i++) { f[i] = false; ans[i] = 1; } int u[100010],v[100010],w[100010]; cin >> n; for (int i=0; i<n-1; i++) { cin >> u[i] >> v[i] >> w[i]; if (w[i]%2 == 0) { f[u[i]-1] = true; f[v[i]-1] = true; } else { if ( ans[u[i]-1] != -1 && ans[v[i]-1] != -1 ) { if ( ! f[u[i]-1] ) { ans[u[i]-1] = 0; } else if ( ! f[v[i]-1] ) { ans[v[i]-1] = 0; } } } } for (int i=0; i<n; i++) { cout << ans[i] << endl; } }
とりあえず2点間が偶数なら良いじゃん!っていうアレで書いたんだけど,
雑過ぎました.
しかも,未定義を -1 とした名残の if文が残っている…
圧倒的時間不足により問題文把握,プログラムが雑になってしまった感があります…
次はちゃんと時間作るぞ〜
あ, E問題 と F問題は解けたら上げます.
エンジニアを説明上手にする本を読んだ
エンジニアを説明上手にする本 を読んだ.
わかりやすく説明するために,
分類してラベルをつけて説明する.
使う用語や関心についてターゲットを分析することなどが説明されていた.
プレゼンテーションについても触れており,
ジェスチャーは3秒キープすることや間についての説明などもある.
情報を構造化するパターンについても説明があった.
言っていることはとても分かる.凄く説明が上手くいきそうだと思った.
悪くない.悪くないんだけど…
日本語が頭に入ってこない…
3度くらい読むの挫折しそうになった.