AtCoder Beginer Contest 082
久々にブログ書くけど、書いてない間に競プロやってなかったわけではないよ。・・・ほんとだよ?
きのうもABCは21時開始のとこ21:40にレジったけど、競プロやってなかったわけではないんだよ。・・・ほんとだってば。
A - Round Up the Mean
はい! 自然数 a, b がもらえるので、a と b の平均(mean)を小数点以下を切り上げ(round up)て整数で出力しなさい。っていう問題。
a+b=c とおいたとき、c が偶数なら、答えは c/2 ですが、c が奇数なら、答えは (c+1)/2 ですね。というのを使って解きました。
#include <iostream> int main(){ int a, b; std::cin >> a >> b; c = a+b; if(c%2) c = (c+1)/2; else c /= 2; std::cout << c << std::endl; return 0; }
ほかの解法として、切り上げ関数ceilを用いるものがあります。ceilはmath.hに入っていて、実数型を受け取って小数点以下を切り上げてくれます。double型で読み取って、double型の割り算をして、ceilを使って切り上げて、int型にキャストして、出力します。
#include<iostream> #include<cmath> int main(){ double a, b; std::cin >> a >> b; std::cout << (int)ceil((a+b)/2.0) << std::endl; return 0; }
でもね、もっと頭のいいやり方があってね、
#include <iostream> int main(){ int a, b; std::cin >> a >> b; std::cout << (a+b+1)/2 << std::endl; }
こっちの方が自然そうなのに何で思いつかなかったんでしょうね。
B - Two Anagrams
英小文字からなる2つの文字列 s, t が与えられるので、s と t をそれぞれ並べ替えて、辞書順で s
よりも t が大きくなるかどうかを判定しなさい。という問題。
つまり、s を辞書順最小に並べ替えて(qwerty->eqrtwy)、t を辞書順最大に並べ替えて(qwerty->ywtrqe)、このときに辞書順で s < t かどうかを判定すればよい。注意するのは、s = t のときである。このときは s < t でないから、"No\n" を出力する。また、s が "aaa" で t が "aa" とかのときは s > t である。注意。
辞書順に並べ替えるのには、sort関数を使うとよい。この関数大好き。
#include<iostream> #include<string> #include<algorithm> using namespace std; int main(){ string s, t; getline(cin, s); getline(cin, t); sort(s.begin(), s.end()); sort(t.rbegin(), t.rend()); bool ans=false; if(s.length()>=t.length()){ for(int i=0; i<t.length(); i++){ if(s[i] > t[i])break; if(s[i] < t[i]){ ans = true; break; } } }else{ ans = true; for(int i=0; i<t.length(); i++){ if(s[i] > t[i]){ ans = false; break; } if(s[i]<t[i]) break; } } if(ans)cout << "Yes\n"; else cout << "No\n"; return 0; }
これ頑張って書いたんですよ。でもね、
#include <algorithm> #include <iostream> #include <string> using namespace std; int main() { string s, t; cin >> s >> t; sort(s.begin(), s.end()); sort(t.rbegin(), t.rend()); if (s < t) cout << "Yes\n"; else cout << "No\n"; }
これでコンパイル通るらしくてね。虚無。入力のgetlineも辞書順比較のためのfor文も必要なかった...orz
んで、t.rbegin()とかt.rend()とかなんなんだというお話ですが、begin()は先頭のイテレータ、end()は末尾のイテレータでしたが、rbegin()は先頭の逆(reverse)イテレータで、同じくrend()は末尾の逆イテレータですね。つまり、sort(t.begin(), t.end())したあとにreverse(t.begin(),t.end())してるのと一緒ですね。ただし、これは、sort(t.begin(), t.end(), greater
C - Good Sequence
長さNの数列 a が与えられるので、a から要素をいくつか取り除いて、a をよい数列(good sequence)にします。a がよい数列であるとは、a の任意の要素 x が、a 全体で x個存在することを言います。取り除く最小の個数を出力しなさい。という問題。
たとえば、3が2個(2<3)のときは、2個とも取り除き、3が4個(4>3)のときは、1個(4-3)取り除き、3が3個(3=3)のときは、0個(3-3)取り除きます。
#include<iostream> #include<algorithm> using namespace std; int ans, count, num; int main(){ int N; cin >> N; int a[N]; for(int i=0; i<N; i++)cin >> a[i]; sort(a, a+N); for(int i=0; i<N; i++){ if(num!=a[i]){ ans += count<num ? count : count-num; num = a[i]; count = 0; } count++; if(i==N-1) ans += count<num ? count : count-num; } cout << ans << endl; return 0; }
んでね、解説見たらね、、、
#include <algorithm> #include <iostream> #include <map> using namespace std; int main() { map<int, int> mp; int a, N; cin >> N; for(int i=0; i<N; i++){ cin >> a; mp[a]++; } int ans = 0; for(auto p: mp){ int x = p.first; int n = p.second; ans += n<x ? n : n-x; } cout << ans << endl; }
数え方が上手! んで、for(auto p:mp)とはなんぞやという話なんだけど、こいつは範囲for文というやつで、任意なコンテナのサイズいっぱい回してくれるんですね。便利かもよ。
D - FT Robot
解法思いついたよ。でもその解法TLEなると思ったよ。想定解だったよ。おしまい。
おしまい。
ABC078 (AtCoder Beginner Contest 078)
きょうはシャドバを10時間くらいしてBPを1000くらい上げたような気がします。ネクロの勝率が高かったです。特にサタン出されてから昏き底やディースの裁きに耐えきり、アスタロトを打てない盤面に仕上げて逆転勝ちできたので(互いに山札2,3枚しか残ってない)確率はしょせん確率なのだと実感できました。諦めてはいけません。(だんだん導入が雑に・・・)
A - HEX
HEX(16進数)の10~15(A~F)2つの組(X,Y)をあげるから、X<Yのときは '<' を、X=Yのときは '=' を、X>Yのときは '>' を出力しなさいよとのこと。
#include <iostream> using namespace std; int main(){ char X, Y; cin >> X >> Y; if(X<Y) cout << "<\n"; else if(X>Y) cout << ">\n"; else cout << "=\n"; return 0; }
char型の変数を不等号(比較演算子)で比べようとすると、int型の文字コードに直して比べてくれる(注:16進数に直すわけではない)ので、簡単でした。charの比較はA
B - ISU
ISU(椅子)の長さはX、人が座る幅はY、人と人、人とISUの間の幅はZ、さあISUには何人座れるでしょう。ってな問題。
n人座れるとすると、Y*n+Z*(n+1) < X < Y*(n+1)+Z*(n+2) すなわち (Y+Z)*n+Z < X < (Y+Z)*(n+1)+Z であるから、n < (X-Z)/(Y+Z) < n+1 つまり、(X-Z)/(Y+Z) を切り捨てて(int型にして)出力すればOK。
#include <iostream> using namespace std; int main(){ int x, y, z; cin >> x >> y >> z; x -= z; int ans = x/(y+z); cout << ans << endl; return 0; }
コンテスト中はそんな不等式解いてなくて、1人あたりY+Z必要で、端っこの人だけさらにZ必要だから、XをZ縮めて、Y+Zで割ればいいやみたいに考えてました。上のコードはそういうわけ。
C - HSI
たぶんHSIって高速インターネットだと思うんだけど・・・(定かでない)
今回初登場のNくんとMくんです。わー\(^^)/ ある競プロ問題にはN個のテストケース(正誤判定入力)があって、そのうちM個は1問あたり1900msかけると50%(1/2)の確率で解け、残りのN-M問は1問あたり100msで確実に解けるプログラムを高橋君(AtCoderの社長さん)が書いたので、この問題でACをもらえるまで高橋君はコードを何回でも提出するとき、実行時間の総和の期待値を出力しなさい。ってさ。(高橋さん自分で求めて←)
#include <iostream> #include <cmath> using namespace std; int main(){ int n, m; cin >> n >> m; int ans = ( (n-m)*100 + m*1900 ) * pow(2,m); cout << ans << endl; return 0; }
答えは ( (N-M)*100 + M*1900 ) * 2^M になるんだけど、なんでこれになるのかはよく分からずに出した。これが解けたのはシャドバのおかげ(違う)。まあ x=(N-M)*100 + M*1900 として、ans=x+(1-1/(2^M))*ans ってなるらしい。ようわからん。なぜわかってないのに答えだけ書けたのかもわからん。つまりわからん。
D - ABS
ABS(絶対値)は実装力がなくてRE出しまくってる間にコンテスト終わってた。ので上げるコードがない。
おしまい
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; }
おしまい。またね。
yukicoder contest 176
久々にyukicoderに参加したよ。yukicoderの前に晩ごはん食べに中華料理屋さんのとこ行ったよ。食べ終わって帰ってきたらポケットの中にスマホがなかったよ。中華屋さんに置き忘れたと思ったよ。取りに戻ったよ。なかったよ。道を探したよ。なかったよ。暗いから夜が明けてから探すことにしたよ。yukicoderがはじまってから20分が経っていたよ。
A問題 No.586 ダブルブッキング
Yukiホテルの予約システムがぶっ壊れてて、同じ部屋に何組も予約が入ってしまったから、Yukiホテルが2組目以降のお客さんに別のホテルの新しい部屋を用意してあげることに・・・ Yukiホテルの宿泊料がP1、振替先のホテルの宿泊料がP2のとき、Yukiホテルは全部でいくらの損失? ってな問題。
#include <iostream> #include <set> using namespace std; int main(void){ int P1, P2, N, R; set<int> reserves; cin >> P1 >> P2 >> N; int oneLoss = P1 + P2; int ans = 0; for(int i=0; i<N; i++){ cin >> R; auto c = reserves.insert(R); if(!c.second) ans+=oneLoss; } cout << ans << endl; return 0; }
今回のコードでは、setですね。リスト(配列)の一種ですたぶん。setヘッダをincludeしてあげて、set<型名> 変数名; って感じで宣言します。要素を二分木(バイナリツリー)で持ってるので、要素の探索がO(log2_n)で速いです。
今回は、このsetの特徴である「同じ要素を持たない」ってことを使いました。変数名.insert(値)で値を挿入できるんですが、このときに返り値として、pair
では、なぜ pair
pair型は 変数名.first で1個目(左側)の値を、変数名.second で2個目(右側)の値を取得できます。これでコードの説明は終わりですね。あ、!c.second は c.second の否定です。
B問題 No.587 七対子
なんか説明疲れた。(だいたいスマホのせい←)
#include <iostream> #include <algorithm> using namespace std; int main(){ char S[14]; for(int i=0; i<13; i++) cin >> S[i]; S[13]='\n'; sort(S, S+13); bool odd=0; char ans='\n'; for(int i=0; i<13; i++){ if(!odd){ if(S[i]==S[i+1] && S[i]!=S[i+2]){ i++; }else if(S[i]==S[i+1]){ ans = 'I'; break; }else{ ans = S[i]; odd = 1; } }else{ if(S[i]==S[i+1] && S[i]!=S[i+2]){ i++; }else{ ans = 'I'; break; } } } if(ans=='I' || ans=='\0' || ans=='\n')cout<<"Impossible\n"; else cout<<ans<<endl; return 0; }
もっといい書き方があるとは思います。かなり冗長なコード。苦悩のあとが見て取れる。とりあえずソートして2個(S[even],S[odd])ずつ見ていって3個のやつ出てきたらbreakして "Impossible\n" を出力。1個のやつ出てきたらansにもって、また2個(S[odd], S[even])ずつ見ていって1個か3個のやつが出てきたらbreakして "Impossible\n" 出力。ansになんかの値が入ってるとansを出力。そんなかんじ。
C問題 No.588 空白と回文
この問題のポイントは実際に空白に置き換えなくてもいいってことと、与えられる文字列には空白が含まれないってこと。全部の部分文字列について、真ん中から対称に比較してって同じか違うかだけ見ればいいじゃん。
#include <iostream> #include <string> using namespace std; int main(){ string S; getline(cin, S); int ans=0, cnt; if(S.length()==1){ ans=1; }else{ for(int i=1; i<S.length(); i++){ cnt=0; for(int j=0; i+j<S.length() && i-j-1>=0; j++){ if(S[i-j-1]==S[i+j]){ cnt+=2; } } ans = max(ans, cnt); cnt=1; for(int j=1; i+j<S.length() && i-j>=0; j++){ if(S[i-j]==S[i+j]){ cnt+=2; } } ans = max(ans, cnt); } } cout<<ans<<endl; return 0; }
文字列の最初っから見ていって、どこを中心にしたら一番長くなるかな~って全部試してます。いじょう。
スマホみつかるといいなあ。
AtCoder Regular Contest 076
みなさんこんにちは。放送大学の文系講義が面白くて自分の大学の講義をさぼり中なu_shoです。
一昨日あったABC076のやつやるよ。u_shoはABしか解けなくてごみごみのごみだったよ(T^T)
まずA問題だよ。問題名は「Rating Goal」、今のレートRとなりたいレートGがもらえるから、RをGにするために必要なパフォーマンスPを求めるよ。問題文から、
(P+R)/2 = G
∴ P = 2G-R
だよ。方程式の解き方が分からない人はこのページ方程式の解き方 等式の性質を見てね。
∴は「したがって」みたいな意味だよ。
んじゃコード↓
#include <iostream> int main(){ int r, g; std::cin >> r >> g; std::cout << 2*g-r << '\n'; return 0; }
いままで using namespace std; で書いたことにしていた std:: を直に書いてます。std::endl を書くのがめんどくさいので、直に改行文字 \n を出力するようにしています。コーディングが速く終わりました。ついでに言っとくと、std::endl とするよりも実行時間が速いです。namespace(名前空間)については私がよくわかってないので、自分で調べてください←
次はB問題、「Addition and Multiplication」。最初の数1に、2をかけたり(do multiplication)、Kをたしたり(add)して、N回の計算でなるべく小さな数にしようね! って言ってます。2をかけても、Kをたしても、数は絶対に正です(∵Kは正の数(∵は∴の逆の意味。「なぜなら」とか))。なので、2をかけるときもKをたすときも、もとの数が小さい方が小さくなります。
つまり、一回の計算ごとに、小さくなるほうを選んでいけばOKってことですね。はい。
#include <iostream> using namespace std; int main(void){ int n, k; cin >> n >> k; int ans=1; for(int i=1; i<=n; i++){ if(ans*2 < ans+k){ ans *= 2; }else{ ans += k; } } cout << ans << endl; return 0; }
では、u_shoがゴミになった元凶のC問題ですね。「Dubious Document 2」(意訳:うさんくさい文章その2)です。?t?o??? みたいな謎の文字列S'にcoderみたな普通の文字列Tが入るかなーってやって、S'を辞書順最小になるように(この場合atcoder)どうにかしてね。
私奴の嘘解法(コンテスト時間外にAC)はこうですね。
#include <iostream> #include <string> using namespace std; int main(){ string S, T; cin >> S; cin >> T; bool check=false; int ct,cs; for(int j=S.length()-T.length(); j>=0; j--){ for(int i=0; i<T.length(); i++){ for(int k=0; k<T.length(); k++){ if(S[j+k-i]!='?' && S[j+k-i]!=T[k]){ break; }else if(k==T.length()-1){ check=true; cs=j; ct=i; goto LABEL; } } } } LABEL: string ans=S; if(check){ for(int i=0; i<T.length(); i++){ ans[cs+i-ct]=T[i]; //<-私はここで-ctを忘れてWAくらいまくりましたorz } for(int i=0; i<S.length(); i++){ if(ans[i]=='?')ans[i]='a'; } cout << ans <<endl; }else{ cout << "UNRESTORABLE\n"; } return 0; }
これACしちゃうんですけど(私はまずこれが通せなかったんですが)、S'が?b??で、Tがbaとかだと、ほんとはabaaって出力しなきゃいけないのに、このコードだとabbaって出力しちゃうんですよね。本番はこれに該当するテストケースがなくて大丈夫だった(通せた)みたいですが、、、
このテストケースを通すには、全探索ですね。上のコードみたいに、入るかなーってやって、入ったやつを全部記憶して、それが辞書順で小さいかどうかを順に比較していけばいいんですよね。大変そうなのでやりません。
えーっと、goto文っていうのはそこから、goto ?; の ?: って書いてあるところまで一気に処理をとばすヤバイ文ですね。?; を書くところを間違えては絶対にいけません。特にgoto文より上の行に書いてはいけませんし、ループの代わりに使うのもだめです。無限ループのもとです。注意して使いましょう。今回の場合だと、ラベル付きbreak文というのがあるので、そっちを使ってもいいでしょう。
ではでは。
AtCoder Regular Contest 075 C - Bugged
AtCoderのC埋め3問目。ABC063 / ARC075 のC問題「Bugged」(蠅ではない)。
N個の自然数s[i]がもらえるので、それを全部足したやつが答えなんですが、ここでBugが起きます。なんと答えが10の倍数だと0扱いされてしまうのです。なので、答えが10の倍数にならないためにはどのs[i]を「答えに足さない」かということを考えましょう。
#include <iostream> #include <algorithm> using namespace std; int main(void){ int N, ans = 0; cin >> N; int s[N]; for(int i=0; i<N; i++){ cin >> s[i]; ans += s[i]; } if(ans%10==0){ sort(s, s+N); for(int i=0; i<N; i++){ if(s[i]%10){ ans -= s[i]; break; } } } if(ans%10==0) ans = 0; cout << ans << endl; return 0; }
とりあえずansに全部足して、それが10の倍数だと、s[i]が10の倍数かどうかを小さいやつから順にみていって、10の倍数でなければ、そいつをansから引いてあげればOK。と思ったんですが、sの全部が10の倍数のときはどうやっても0なので、その場合をしっかり考えて、if(ans%10==0) ans = 0; の一文を付け加えてあげるとACです。(こういう問題を一発で通せるようにならなければ・・・)
という問題でした。ちゃお~。
と思ったけど、sort(s, s+N); が初出でした。これはalgorithmライブラリをincludeしてあげてから使います。sortはvoid(値を返さない)型の関数で、sort(ポインタA, ポインタB) とやると、ポインタAからポインタBが(確保されていれば)入っている数値の小さい順に並べかえられます(ポインタよくわかんない人は「ポインタ 配列」とかでググってください)。
そんぐらいの関数は自分で書けよと思ったでしょ。いやまあそうなんだけどね。実はソートには色々あって、それぞれ計算量が違うので、常に適切なソートを書くのは大変なのよ。その点、計算量が多くともO(NlogN) (Nは要素数)に最適化されるsort関数は便利なのね。もっと便利に使えるんだけど、それはまたの機会に。
今度こそちゃお~。