はじめに
競プロに興味を持ち，少しづつ参加しているのですが，モチベ維持のためにQiitaに少しづつ載せていけたらなと思います．過去に参加したものに遡って少しづつ書いていく予定です．
今回のコンテストのurlはこちら
A問題
問題概要
数値$a, b, c, d, e, k$が与えられたときの，$a, b, c, d, e$それぞれの差が$k$より小さいかを判定し，そうであればYay!と，そうでなければ:(を出力する．ここで，各値は$a<b<c<d<e$であるものとする．
自分の解答
ここでは，単純に総当たりで判定するコードを作成した．解説を見るともっと良い方法があった．
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int> con(5);
int i,j;
for(i=0; i<con.size(); i++){
cin >> con[i];
}
int k;
cin >> k;
int cantComm = 0;
for(i=0; i<con.size(); i++){
for(j=i+1; j<con.size(); j++){
if(con[j]-con[i] > k){
cantComm++;
}
}
}
if(cantComm == 0){
cout << "Yay!" << endl;
}else{
cout << ":(" << endl;
}
return 0;
}
解説を見た後
ここでは，$a<b<c<d<e$と決まっているのは，差が最大になるのは$e-a$と決まっており，そこだけを判定すると良い．
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, e, temp;
int k;
int i,j;
cin >> a >> temp >> temp >> temp >> e >> k;
cout << (e-a>k? ":(" : "Yay!") << endl;
return 0;
}
B問題
問題概要
$A, B, C, D, E$分かかる料理を全て入手するまでの時間を計算する．ここで，同時に待つことができる料理は１つまでとする．
自分の解答
非常に苦戦した．結局，
-
%10を保存しておき，それが一番遅いものを最後に注文する - 時間算出時には
%10を利用して各料理の待ち時間が10の倍数になるようにする
という２つの条件を考えてソースコードを作成した．
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int> chumon(5);
for(int i=0; i<chumon.size(); i++){
cin >> chumon[i];
}
int minTemp = chumon[0]%10;
for(int i=1; i<chumon.size(); i++){
if(minTemp > chumon[i]%10 && chumon[i]%10 != 0){
minTemp = chumon[i]%10;
}
}
int sumTime = 0;
for(int i=0; i<chumon.size(); i++){
sumTime += chumon[i];
if(sumTime%10 != 0){
sumTime += (10 - sumTime%10);
}
}
if(minTemp == 0){
cout << sumTime << endl;
}else{
sumTime -= (10 - minTemp);
cout << sumTime << endl;
}
return 0;
}
解説を見た後
解説だけでは特に変わったことは記述されていなかったため，解答一覧から数人のコードを見た結果，非常に綺麗な書き方があることがわかった．以下が，自分で理解して書いたものである．
#include <bits/stdc++.h>
using namespace std;
int main(){
int waitingTime;
int sumTime = 0;
int maxTemp = 0;
for(int i=0; i<5; i++){
cin >> waitingTime;
sumTime += (waitingTime+9)/10*10;
if(waitingTime%10 != 0)
maxTemp = max(maxTemp, 10-waitingTime%10);
}
cout << sumTime - maxTemp << endl;
return 0;
}
C問題
問題概要
６つの都市を最初から最後まで人が移動してその所要時間を求める問題．それぞれの移動時間は１分で，その人数は$A, B, C, D, E$人となっている．移動する人は$N$人全員最初の都市にいる．
自分の解答
解けなかった．
動作をそのままシミュレーションした結果TLEとなった．
解説を見た後
ここでは，一番足を引っ張る（人数の少ない交通機関）が＄N$人を運び終える時間を計算すると良い．
また，値の範囲が $$1<=A, B, C, D, E, N<=10^{15}$$ なので，intではなくlongを用いる必要がある．
#include <bits/stdc++.h>
using namespace std;
int main(){
long n;
cin >> n;
vector<long> capasity(5);
cin >> capasity[0];
long minTemp = capasity[0];
for(int i=1; i<capasity.size(); i++){
cin >> capasity[i];
minTemp = min(minTemp, capasity[i]);
}
cout << (n-1)/minTemp + 5 << endl;
return 0;
}
D問題
問題概要
$A,B,C$という形のケーキがそれぞれ$X,Y,Z$種類あるとする．それらに対して美味しさという数値が
A_1,A_2,...,A_X \\
B_1,B_2,...,B_Y \\
C_1,C_2,...,C_Z
と表される．ケーキを買うパターン$X\times Y\times Z$通りのうち，美味しさが$1,2,...,K$番目になる選び方をした時の美味しさを出力する．
自分の解答
解けなかった．
C問題までで力尽きていた．
取り敢えず全パターンソートは試したが，案の定TLEとなった．
解説を見た後
どうやら，$A,B,C$それぞれを降順ソートしてから可能性のある組み合わせを配列に格納して，それをさらにソートして0~Kまで出力すると良いようだ．
#include <bits/stdc++.h>
using namespace std;
int main() {
long X, Y, Z, K;
vector<long>vec;
cin >> X >> Y >> Z >> K;
vector<long> A (X);
vector<long> B (Y);
vector<long> C (Z);
for (int i=0; i<X; i++) cin >> A[i];
sort(A.begin(), A.end(), greater<long>());
for (int i=0; i<Y; i++) cin >> B[i];
sort(B.begin(), B.end(), greater<long>());
for (int i=0; i<Z; i++) cin >> C[i];
sort(C.begin(), C.end(), greater<long>());
for (int i=0; i<X && i+1<=K; i++)
for (int j=0; j<Y && (i+1)*(j+1)<=K; j++)
for (int k=0; k<Z && (i+1)*(j+1)*(k+1)<=K; k++)
vec.push_back(A[i] + B[j] + C[k]);
sort(vec.begin(), vec.end(), greater<long>());
for (int i = 0; i < K; i++) cout << vec[i] << endl;
return 0;
}
おわりに
- 切り上げを簡単に表現する書き方を学んだ
n = (m+9)/10*10;
- coutの分岐を学んだ
cout << (条件? 処理１:処理２) << endl;
- maxを更新していく書き方を学んだ
maxNum = max(maxNum, newNum);