AtCoder Beginner Contest 103 (ABC103)
ABC103に参加しました。遅刻しなかった上に全完したのでレートが96上がりました。やったぜ。
A - Task Scheduling Problem
6通り全部試してもいいですが、A_i → A_j → A_k とタスクを行う場合、直感的に A_i ≦ A_j ≦ A_k がもっともコストが低そうですね。
なので、A_k = max(A), A_i = min(A), として答えはabs(A_k - A_j)+abs(A_j - A_i) = abs(A_k - A_i) = max(A)-min(A)となります。
B - String Rotation
(問題文で言われたとおりに)やるだけ。
str.substr(index)でstr[index]から末尾までの部分文字列を示します。
また、str.substr(index,length)でstr[index]からstr[index+length-1]までの部分文字列を示します。
最初に、s=s+sとしておくとより簡単な実装になるかも。
C - Modulo Summation
思考過程
aのそれぞれに対して m=(aの倍数-1)のとき嬉しいことは明らか。
つまりm=(全てのaの最小公倍数)-1とするとよい。
このときm%a=a-1となるので、∑(a-1)でよい。
D - Islands War
思考過程
(Aの最大値)<(Bの最小値)なら答え1だねってのは分かる。
じゃあそうじゃないときは1番大きいaを脇によけてans++して、もう1回判定するってのを繰り返すとよくって、
脇によけたやつどうしで、それと同様の操作をする((Aの最大値)<(Bの最小値)なら答え+1,そうじゃないときは1番大きいaを脇によけてans++して、もう1回判定するってのを繰り返す)と良さげ。
わきによけるときはaとセットのbも一緒によけて、Aの最大値、Bの最小値を更新する。
ただ、それすると実装が重い。つか毎回最大値判定にO(m)使うからともするとO(m^2)で通らない。
のでaの昇順にソートする。→たぶん解説と一緒でO(n logn)。
でもこれって、別に脇によけるのは一番大きなaでなくてもよくって、
つまりすべての(a,b)についてa<(Bの最小値) && b>(Aの最大値)なら答え+1,そうじゃないときは(a,b)を脇によけてans++して、もう1回判定するってのを繰り返すをやればよい。
このときソートがいらないのでO(n)。
僕のコードはこのときにソートつけてても通るので提出時間意識してつけっぱ。
ま・た・ね
AtCoder Beginner Contest 094 (ABC094)
ABCの過去問。ショートコーディングしてみた。Cは配列2つ持つよりもlower_bound()使いたかったけど、実装力ぅ(イテレータを理解していないため)。難しそうだし眠いから諦め。kotatsugameさんはやっぱりショートコーディング強い。
A問題：Submission #2819377 - AtCoder Beginner Contest 094
B問題：Submission #2819431 - AtCoder Beginner Contest 094
Atomエディタの入力補完機能をいじくってみた
おはこんばんにちは、u_shoです(=^･ω･^=)
私はエディタとして、入力補完の優秀さなどの点からAtomを使っているのですが、
main関数やnamespaceの補完では、「競プロ向け」*1でない補完をしやがるので少しばかり不満に思っていました。
そこで今回、Atomの入力補完機能(スニペットというらしい)を「競プロ向け」に魔改造することにしました。
参考はこのブログ↓
rfs.jp
まずは「ファイル(もしくはEdit)」から「スニペット(Snippets)」を開きます。*2
そしたらこのファイル(snippets.cson)が開きます(たぶん)。Atomのバージョンとかによっては違うかも
んでこのファイルの末尾にこんな感じで書いてあげます。最初っから書いてあるやつはコメント(トリセツ)なので消しても消さなくてもいいです。
'.source.cpp':ってのが、このスニペットはcppファイルの中で使いますよ～ってことです。
次にはインデントをしっかり*3とってスニペットの名前(補完時に表示される)を書きます。
そこからインデントをしっかりとって'prefix:'以下に、この文字打ち込んだらスニペットを呼び出しますよ～ってのを書きます。私はsettingとしました。
次に、インデントをしっかり(しつこい)とったら'body:'以降にこーゆー補完して！ ってのを書きます。$1で最初のカーソル位置、$2でタブキーで移動した後のカーソル位置を指定できます。私はいわゆる競プロテンプレートにしました。
これで完成！！
試しにやってみる。
setと打ってエンターキーを押すと・・・
できた～(*´▽｀*)
ICPC過去問
先週金曜日(7/6)にICPC国内予選がありまして、私も出場しまして、まあ去年と同じく３完だったのですが、大会の熱に中てられまして、やる気が爆上がりしたので久々に精進をすることにしました。前のように解説とかは無理なので、解いた問題のリンク張るだけにしようかなと思います。
ICPC国内予選2015 A問題(すなおに解いた)http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3009207
ICPC国内予選2017 C問題(ごり押し全探索o(10^6))http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3009198
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
英小文字からなる２つの文字列 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; }
