早く青コーダーになりたいので、ABCの中でラスト問題(ABC125までならD、それ以降ならF)が水色～青色のものを選んで解いて、解説したいと思います。
できれば1日1コンテストのペースで、半年後に全部潰せるペースで解いていきたいです。
A – Five Antennas
5つのアンテナのそれぞれの間隔が、k以下であるかを求める問題。
5つしかないので、5C2通りのパターン全てがk以下か調べることで解けそうです。
ただ、よくよく考えると左端にあるアンテナと右端にあるアンテナが一番離れているため、ここの2点間の距離がk以下か調べるだけで良さそうです。(その間にあるアンテナ間の距離は、それより小さいはず)
下記ソースではソートしていますが
西から順にアンテナ A,B,C,D,Eと名付けられており、それぞれの座標は a,b,c,d,eです。 a,b,c,d,e,k は 0 以上 123 以下の整数 a<b<c<d<e
なので、e-aがk以下かを見るだけでOKです。
#include<bits/stdc++.h>
using namespace std;
int main(){
int abcde[5];
int k;
cin>>abcde[0]>>abcde[1]>>abcde[2]>>abcde[3]>>abcde[4];
cin>>k;
sort(abcde,abcde+5);
if(abcde[4]-abcde[0]<=k) cout<<"Yay!"<<endl;
else cout<<":("<<endl;
}
出力がちょっと変ですが、こういったものは手打ちせずコピペしましょう。
B – Five Dishes
10の倍数の時刻で注文をする場合、5つの料理をどの順番でするのが最速になるのかを求めよ。
入力例1 A=29,B=20,C=7,D=35,E=120の場合を考えます。
A→B→C→D→Eの順番に頼む場合、
時刻0でAを注文→時刻29に届く→1待って時刻30でBを注文→時刻50に届く→時刻50にCを注文→時刻57に届く→3待って時刻60にDを注文→95に届く→5待って時刻100にEを注文→220に届く
となります。
料理を頼んだ後、端数がある場合10-届く時刻%10待つ必要があります。
ただ、ラストに注文した料理だけは待つ必要がありません(もう注文しなくて良いため)。
ここが最適化の部分です。
具体的には、待つ時間が一番長くなる料理を最後にした時の合計(A+B+C+D+E+A～Eの端数(一番大きいものは除く))を答えとします。
#include<bits/stdc++.h>
using namespace std;
int main(){
int A,B,C,D,E;
cin>>A>>B>>C>>D>>E;
int ten[5];
ten[0]=(10-A%10)%10;
ten[1]=(10-B%10)%10;
ten[2]=(10-C%10)%10;
ten[3]=(10-D%10)%10;
ten[4]=(10-E%10)%10;
sort(ten,ten+5);
cout<<A+B+C+D+E+ten[0]+ten[1]+ten[2]+ten[3]<<endl;
}
(10-A%10)%10は端数の計算です。30や40の時に(10-A%10)だけだと10になるので、最後の%10で0にするよう補正しています。
それらをソートし、一番大きいもの以外を足し合わせたものを答えとしています。
C – Five Transportations
N人が都市6に移動する際の最小時間を求めよ。
ただ、各都市間が1で移動できる人数の上限が決まっている。
この問題、所謂ボトルネックであるポイント(A～Eの最小)以外は関係ありません。
何故かというと、最小の以前で一杯運べても最小の地点で絞られ、その後は絞られた人数で進んでいくしかないからです。
ボトルネックの説明の絵である、蛇口と同じ考えですね。
#include<bits/stdc++.h>
using namespace std;
int main(){
long long N;
long long ABCDE[5];
cin>>N;
cin>>ABCDE[0]>>ABCDE[1]>>ABCDE[2]>>ABCDE[3]>>ABCDE[4];
sort(ABCDE,ABCDE+5);
cout<<4ll+N/ABCDE[0]+(N%ABCDE[0]!=0)<<endl;
}
N/ABCDE[0]+(N%ABCDE[0]!=0)でボトルネックの地点で運びきるのに必要な時間を求め、それにボトルネック以外の地点が運ぶのに必要な時間(1*4=4)を答えとしています。
D – Cake 123
ABC123を解いた理由の問題です。
AtCoder Problemsだと水色上位問題です。
X,Y,Zの値の組み合わせの中で、値が大きい順上位K番を出力せよ。
単純にループをすると最大1000^3でTLEです。
工夫する必要があります。
二つだけの場合
XとYしかない場合を考えます。
この問題、Kが最大3000しかないのがヒントです。
つまり、Xの上位3000個と、Yの上位3000個を組み合わせた9*10^6通りの中に上位3000以上が’あるはずです。(Xの上位3001個目は、Xの上位1～3000個と、Yの上位1個の組み合わせより小さくなるはずなので、大きくても3001番目にしかならない)
2つだけなら、X,Yの値が大きくても何とかなりそうです。
三つの場合
二つだけなら解けそうなことが分かりました。
こういった場合に使えるのが、半分全列挙の考えです。
AとBとCの組み合わせ=(AとBの組み合わせ)とCの組み合わせ
と同義になります。
AとBの組み合わせは1000^2で列挙できます。
(AとBの組み合わせ)とCの組み合わせは全列挙すると1000^3かかり同じになっちゃいますが、前項の考え方から上位3000だけ見ればいいため、3000^2で必要な分が列挙できます。
計算量を落とすことに成功しました！
#include<bits/stdc++.h>
using namespace std;
int main(){
long long X,Y,Z,K;
cin>>X>>Y>>Z>>K;
long long A[X],B[Y],C[Z];
for(int i=0;i<X;i++){
cin>>A[i];
}
for(int i=0;i<Y;i++){
cin>>B[i];
}
for(int i=0;i<Z;i++){
cin>>C[i];
}
vector<long long> sum;
for(int i=0;i<X;i++){
for(int j=0;j<Y;j++){
sum.push_back(A[i]+B[j]);
}
}
sort(sum.begin(),sum.end());
sort(C,C+Z);
vector<long long> ans;
for(int i=sum.size()-1;i>=max(0ll,(long long)sum.size()-K);i--){
for(int j=Z-1;j>=max(0ll,Z-K);j--){
ans.push_back(sum[i]+C[j]);
}
}
sort(ans.begin(),ans.end());
for(int i=ans.size()-1;i>=(int)ans.size()-K;i--){
cout<<ans[i]<<endl;
}
}
降順ソートのやり方が知らない(第三引数に何いればいいか忘れた)ため、forの添え字の方で頑張っていますが、ややこしいですしバグの元なのでやめたほうが良いです…。
雑談(マクロについて)
競プロはマクロ愛好家の方が多い(というか推奨されている雰囲気)ですが、どうなんでしょうか？
typedef long long ll;これはよく見かけます。long longをllとしてタイピング量を減らす作戦です。
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define all(x) x.begin(), x.end()タイピング量シリーズですが、たまに見かけます。
ここまでやらなくても…と思わなくもないです。
#define FOR(i, a, b) for (int i = a; i < (b); ++i)REPマクロです。これは好きな方が多いですよね。
私も、昔はマクロを使っていたのですが
#define int long longこのマクロ、さずがに競プロでも行儀が悪く(未定義動作っぽい?)、非難も多いみたいです。
私も愛用していましたが、そういった非難の中、使うか迷っていました。
結論として、使わないことと決めたのですが、決めた途端に他のマクロも行儀が悪く見えてしまい、現在全く使っていません。(using namespace stdが使っていますが、あれもちょっと…と思っています)
難しいところですね…。
(ごめんなさい、オチはないです＞ ＜)
コメント