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?

@RubyLrving(ruby lrving)

AtCoder Beginner Contest 471

0
Posted at

A - Nine or Nein

問題文

O(1)
式を変形の問題です。

a / b = 9

だと余りの判定ができずwaになります。

a = 9 * b

と式を変形しましょう。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int a, b;
    cin >> a >> b;

    if(a + b == 9 || a - b == 9 || a * b == 9 || a == 9 * b){
        cout << "Nine" << endl;
    }else{
        cout << "Nein" << endl;
    }

    return 0;
}

B - Survey Tabulation

問題文

O(n)
データ構造の問題です。
文字列の文字を全て小文字へ変換します。
その後、mapにて同じ文字列の数を探索します。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int n;
    cin >> n;
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    map<string, int> mp;
    rep(i, n){
        transform(s[i].begin(), s[i].end(), s[i].begin(), [](char c) {
            return tolower(c);
        });
        mp[s[i]]++;
    }
    int ans = 0;
    for(auto [key, value]:mp){
        ans = max(ans, value);
    }
    cout << ans << endl;
    return 0;
}

C - Cookies and Greedy Takahashi

問題文

O(N)
要素を正の数、負の数の２つのグループに分けて最適な手順で探索します。
コンテスト中は下記のコードで回答しました。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    deque<ll> left, right;
    rep(i, n){
        if(0 <= a[i]){
            right.push_back(a[i]);
        }else{
            left.push_back(a[i]);
        }
    }
    ll pos = 0;
    ll ans = 0;
    while(left.size() || right.size()){
        ll l = 0, r = 0;
        if(left.size()) l = abs(pos - left.back());
        if(right.size()) r = abs(right.front() - pos);
        if(left.size() && right.size() && l <= r){
            pos = left.back();
            left.pop_back();
            ans += l;
        }else if(left.size() && right.size() && l > r){
            pos = right.front();
            right.pop_front();
            ans += r;
        }else if(left.size()){
            pos = left.back();
            left.pop_back();
            ans += l;   
        }else{
            pos = right.front();
            right.pop_front();
            ans += r;
        }
    }
    cout << ans << endl;
    return 0;
}

少しコードを整理しましょう。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    deque<ll> left, right;
    rep(i, n){
        if(0 <= a[i]){
            right.push_back(a[i]);
        }else{
            left.push_back(a[i]);
        }
    }
    ll pos = 0;
    ll ans = 0;
    while(left.size() || right.size()){
        if(left.size() && right.size()){
            if(abs(pos - left.back()) <= abs(right.front() - pos)){
                ans += abs(pos - left.back());
                pos = left.back();
                left.pop_back();
            }else{
                ans += abs(right.front() - pos);
                pos = right.front();
                right.pop_front();
            }
        }else if(left.size()){
            ans += abs(pos - left.back());   
            pos = left.back();
            left.pop_back();
        }else{
            ans += abs(right.front() - pos);
            pos = right.front();
            right.pop_front();
        }
    }
    cout << ans << endl;
    return 0;
}

この問題はsetを使用して二分探索でも回答できます。
O(NlogN)

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll n;
    cin >> n;
    set<int> st;
    rep(i, n){
        int a;
        cin >> a;
        st.insert(a);
    }

    ll pos = 0;
    ll ans = 0;
    for(int i=0; i<n; i++){
        auto it = st.lower_bound(pos);
        int next = 0;
        if(it == st.begin()){
            next = *it;
        }else if(it == st.end()){
            next = *--it;
        }else{
            int x = *it;
            int y = *--it;

            if(abs(x - pos) < abs(y - pos)){
                next = x;
            }else{
                next = y;
            }
        }

        ans += abs(next - pos);
        st.erase(next);
        pos = next;
    }
    cout << ans << endl;
    return 0;
}

D - Chargers

問題文

O(NlogN)
データ構造の問題です。
問題文の通りにシミュレーションをすると、
充電しているバッテリーに、クエリ毎に渡される時刻 - コンセントへ繋いだ時刻の数値を加算していくことになります。
これはO(N^2)でTLEになります。

そこで0秒を基準にしてw-tの値をプライオリティキューに追加していきます。
出力する時はmin(最大容量, 0秒を基準した要素の中で最大のw + 現在の時刻)を出力します。

C++
#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll q, v;
    cin >> q >> v;

    priority_queue<ll> pque;
    rep(i, q){
        ll query, t, w;
        cin >> query;

        if(query == 1){
            cin >> t >> w;
            pque.push(w - t);
        }

        if(query == 2){
            cin >> t;
            if(pque.size()){
                ll ww = pque.top() + t;
                cout << min(v, ww) << endl;
                pque.pop();
            }else{
                cout << -1 << endl;
            }
        }
    }

    return 0;
}
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
Sign upLogin
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?