はじめに
- AtCoder Beginner Contestの過去問の解法及び提出したソースコードをまとめています。
- 基本的に自分が振り返ることを目的としておりますが、誤りや気になった点、その他質問等もお待ちしておりますので遠慮なくお願いします。
コンテストページ
A問題
HがMの倍数であるか判定したいので、HをWで割った余りが0かどうかを確認してあげればよいです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int m,h;
cin >> m >> h;
if(h%m==0) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
B問題
まず最初にWをグラムに直すことを忘れず。
Wを1からWまでの整数Xで割ったときの値をYとすると、「YグラムのみかんをX個選ぶ」と言い換えられます。
Yが[A,B]の範囲に含まれるかを判定し、含まれる場合のXの最大最小を求めてあげればよいです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
double a,b,w;
cin >> a >> b >> w;
w*=1000;
int mn = INT32_MAX;
int mx = 0;
for(int i = 1; i <= w; i++){
if(w/i >= a && w/i <= b){
mn = min(mn, i);
mx = max(mx, i);
}
}
if(mn == INT32_MAX) cout << "UNSATISFIABLE" << endl;
else cout << mn << " " << mx << endl;
return 0;
}
C問題
1000のi乗から1000のi+1乗引く1の各数に含まれるコンマの数はi個です。
上記を考慮しnの範囲で足していけばよいです。
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
ll powll(ll x, ll n){
ll ret = x;
for(ll i = 0; i < n; i++) ret *= x;
return ret;
}
int main()
{
ll n;
cin >> n;
ll ans = 0;
for(ll i = 0; i < 6; ++i){
ll p = powll(1000, i) - 1;
if(n > p) ans += n - p;
}
cout << ans << endl;
return 0;
}
D問題
荷物を価値の高いものから順にソート(同じ価値の場合は重さが軽い方が前方)して空いている箱のうちその荷物を入れられる最小の容量の箱に詰めていけばよいです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,m,q;
cin >> n >> m >> q;
vector<pair<int,int>> wv(n);
vector<int> x(m);
for(int i = 0; i < n; i++) cin >> wv[i].first >> wv[i].second;
for(int i = 0; i < m; i++) cin >> x[i];
sort(wv.begin(), wv.end(), [](auto l, auto r){
if(l.second > r.second) return true;
else if(l.second < r.second) return false;
else return (l.first < r.first);
});
for(int i = 0; i < q; i++){
int l,r;
cin >> l >> r;
l--;r--;
vector<int> tmp_x;
for(int i = 0; i < m;i++){
if(l <= i && i <= r) continue;
tmp_x.push_back(x[i]);
}
vector<bool> done((int)tmp_x.size(), false);
sort(tmp_x.begin(), tmp_x.end());
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < (int)tmp_x.size(); j++){
if(done[j]) continue;
if(tmp_x[j] >= wv[i].first){
ans += wv[i].second;
done[j] = true;
break;
}
}
}
cout << ans << endl;
}
return 0;
}
E問題(未AC)
まだ解いておりません。
F問題(未AC)
まだ解いておりません。