AtCoder 生活 64日目

64日目

今回はC問題、D問題1問ずつ解き、とバーチャル参加を2回しました。

問題	難易度	自力で解けた	かかった時間
ABC167	C	✕	122分11秒
ABC167	D	✕	164分50秒

ABC153

A

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

int main(){
    int h,a;
    cin >> h >> a;
    cout << (h+a-1)/a << endl;
}

B

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pil = pair<pii,int>;


int main(){
    int h,m;
    cin >> h >> m;
    rep(i,n){
        int a;
        cin >> a;
        h -= a;
    }
    if(h <= 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

int main(){
    ll n,k;
    cin >> n >> k;
    if(n-k <= 0){
        cout << 0 << endl;
        return 0;
    }
    int ans = 0;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    sort(h.begin(),h.end());
    rep(i,n-k){
        ans += h[i];
    }
    cout << ans << endl;
}

ABC152

A

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

int main(){
    int n,m;
    cin >> n >> m;
    if(n == m) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pil = pair<pii,int>;


int main(){
    int a,b;
    cin >> a >> b;
    int x = min(a,b);
    int y = max(a,b);
    rep(i,y){
        cout << x;
    }
    cout << endl;
}

C

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

int INF = 1e9;

int main(){
    int n;
    cin >> n;
    int m = INF;
    int cnt = 0;
    rep(i,n){
        int a;
        cin >> a;
        if(m > a) m = a;
        else cnt++;
    }
    int ans = n - cnt;
    cout << ans << endl;
}

ABC167_C

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int INF = 2e9;

int main(){
    int n,m,x;
    cin >> n >> m >> x;
    vector<vector<int>> a(n,vector<int>(m));
    vector<int> c(n);
    rep(i,n){
        cin >> c[i];
        rep(j,m) cin >> a[i][j];
    }
    int ans = INF;
    rep(s,1<<n){
        int cost = 0;
        vector<int> d(m);
        rep(i,n){
            if(s>>i&1){
                cost += c[i];
                rep(j,m) d[j] += a[i][j];
            }
        }
        bool ok = true;
        rep(j,m) if(d[j] < x) ok = false;
        if(ok) ans = min(ans,cost);
    }
    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;
}

解くのにかかった時間：122分11秒
感想：bit全探索にまだ慣れてない…

ABC167_D

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;

int main(){
    ll n,k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vector<int> s;
    vector<int> ord(n+1,-1);
    int c = 1;
    int l = 0;
    int v = 1;
    while(ord[v] == -1){
        ord[v] = s.size();
        s.push_back(v);
        v = a[v-1];
    }
    c = s.size() - ord[v];
    l = ord[v];
    if(k < l) cout << s[k] << endl;
    else {
        k -= l;
        k %= c;
        cout << s[l+k] << endl;
    }
}

解くのにかかった時間：164分50秒
感想：ある程度の形はわかっていたが解ききれなかった

最後に

C,D問題をスムーズに解けるように緑diffの問題にも慣れていきたい