AtCoder Beginner Contest 077
きのうABC077があったみたい。きのうは大学の囲碁将棋部の同級生とお食事会してたから参加できなかったので、きょうの昼に時間測りながら解いてみた。A,B,Cを 28分+1WA で解けたので、出ていたらパフォーマンス1600くらい(自己ベストは1119)だったのかあ・・・ 前回レートが下がった茶色コーダーとしては、出れていればなあ、という感じ。。。
A - Rotation
なにはともあれA問題(?)。「Rotation(回転)」です。縦2、横3の6文字Cij(1≦i≦2,1≦j≦3)がもらえるので、これを180度rotateさせても同じかな？ って問題。
#include <iostream> using namespace std; int main(){ char C[2][3]; for(int i=0; i<2; i++) for(int j=0; j<3; j++) cin >> C[i][j]; for(int j=0; j<3; j++){ if(C[0][j]!=C[1][2-j]){ cout<<"NO\n"; return 0; } } cout<<"YES\n"; return 0; }
C[0][j]と点対称の位置にあるのがC[1][2-j]なので、これを3つ比較して、もし違うのがあれば "NO\n" を出力してプログラムを終了させて、全部一緒だったら(⇔プログラムが終わっていなければ) "YES\n" を出力してプログラムを終了させました。簡単でした。
B - Around Square
そいでB問題。いつものあいつがもらえるので、それ以下の数のうちで最大の Square number(平方数：ある整数の2乗である数。1,4,9,16,...) を出力してあげればOK。
#include <iostream> #include <cmath> using namespace std; int main(){ int N; cin >> N; int ans = sqrt(N); cout << ans*ans << endl; return 0; }
cmath / math.h ヘッダのなかにある、sqrt() っていう平方根(ルート(√)：2乗したらそれになるような数)を返す関数を使いました。sqrt()はdouble型の値を返すので、int ans = sqrt(N); とやって、小数点以下を切り捨て(double型をint型にキャストし)ます。その2乗を出力するとACもらえます。
ここで間違って、平方数じゃなくて平方数の平方根を出力してしまった(cout<
C - Sunuke Festival
長さNの数列A, B, Cについて、A[i]
#include <iostream> #include <algorithm> using namespace std; int main(){ int N; cin>>N; int A[N]; for(int i=0; i<N; i++)cin>>A[i]; int B[N]; for(int i=0; i<N; i++)cin>>B[i]; int C[N]; for(int i=0; i<N; i++)cin>>C[i]; sort(A, A+N); sort(B, B+N); sort(C, C+N); long long ans=0; for(int i=0; i<N; i++){ ans += ( lower_bound(A,A+N, B[i]) - A ) * ( C+N - upper_bound(C,C+N, B[i]) ); } cout << ans << endl; return 0; }
sort() は確か以前紹介したと思います。ソートして(順番に並べて)くれる関数です。algorithmヘッダに入ってます。
問題は lower_bound(), upper_bound() ですね。こいつらは、(先頭のポインタ(イテレータ), 終端のポインタ(イテレータ), ある値) と引数を渡してあげると、lower_bound()は、その値以上の要素を先頭から終端まで探して、その中で一番(イテレータが)前の要素のイテレータ(ポインタ)を返します。upper_bound()は、その値以下の要素を先頭から終端まで探して、その中で一番(イテレータが)後ろの要素の一つ次のイテレータ(ポインタ)を返します。配列の長さがnのとき、計算量はO(log2(n))です。要は二分探索。こいつらvectorとかでも(確か文字列でも)使えます。便利。これとnext_permutation()があるからC++は強いと言ってもいい。
ともかく、Aの要素のうちB[i]より小さいものの数をlower_bound()で、Cの要素のうちB[i]より大きいものの数をupper_bound()で出してあげられるので、こいつらをかけてあげると、B[i]を使った組み合わせの数が分かります。これをB[0]~B[N-1]でやって全部足したやつを出力してやればOKですね。
D - Small Multiple
むつかしくてよくわからなかった。ゴリゴリしてみた。むりだった。
#include <iostream> #include <cstdio> long long sum, K, k, ans=50; void sumDigi(long long _K){ k = _K; if(k<=1)sum=50; else{ sum=0; for(long long i=0; k; i++){ sum += k%10; k /= 10; } } } int main(){ scanf("%lld", &K); for(long long i=2; i<68000000; i++){ sumDigi(K*i); if(sum < ans) ans = sum; } printf("%lld\n", ans); return 0; }
