0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

[AtCoder]AtCoder Beginner Contest 195

Posted at

はじめに

  • 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)

まだ解いておりません。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?