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 474

0
Posted at

A - Not X

問題文

O(3)
1~3の値でxと等しくない値を出力します。

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 x;
    cin >> x;

    rep(i, 3){
        if(i+1 != x){
            cout << i+1 << endl;
            return 0;
        }
    }

    return 0;
}

B - Exit Order

問題文

左から順に10番目までは10までの数値か、20番目までは20までの数値かを判定していきます。
コンテスト中は、変数で何番目のグループかカウントしてシミュレーションしました。

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<int> p(n);
    set<int> st;
    rep(i, n){
        cin >> p[i];
        st.insert(i+1);
    }

    int cnt = 0;
    rep(i, n){
        if(cnt / 10 >= (p[i] - 1) / 10){
            st.erase(p[i]);
            cnt++;
        }else{
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

明らかにコーディング方法が誤っているので、考察しましょう。
i / 10とp[i] / 10が等しいなら、同じ順番のグループと判定します。

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<int> p(n);
    rep(i, n) cin >> p[i];
    rep(i, n){
        if(i / 10 != (p[i]-1) / 10){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

これが想定された解法ですね。

C - Remove and Append

問題文

O(N)
シミュレーションを想定します。
クエリで渡された値を、配列から削除、末尾に追加を行うと配列の要素の移動に伴いTLEとなります。
そこで、クエリで渡された値を配列から削除せず、末尾に追加を行います。
表示するときに一度表示した値は表示しないようにしましょう。
下記はコンテスト中のコードです。

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, q;
    cin >> n >> q;
    vector<int> p(n);
    rep(i, n) cin >> p[i];
    rep(i, q){
        int a;
        cin >> a;
        p.push_back(a);
    }
    vector<bool> used(n+1);
    vector<int> ans;
    while(p.size()){
        int b = p.back();
        p.pop_back();
        if(used[b]) continue;
        used[b] = true;
        ans.push_back(b);
    }
    reverse(ans.begin(), ans.end());
    rep(i, ans.size()){
        cout << ans[i] << ' ';
    }
    cout << endl;
    return 0;
}

D - Outweigh

問題文

O(N)

  • a[i] > b[i]が一つもない場合はNo
  • a[i] <= b[i]の要素のwiは1とする
  • b[i] - a[i]の差分の合計をa[i] > b[i]の要素に加算して正整数列wiの値とする

下記はコンテスト中のコードです。

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<ll> a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    bool ok = false;
    ll cnt = 0;
    vector<ll> ans(n);
    rep(i, n){
        if(a[i] <= b[i]){
            cnt += b[i] - a[i];
            ans[i] = 1;
        }else{
            ok = true;
        }
    }
    if(ok == false){
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    rep(i, n){
        if(a[i] > b[i]){
            ans[i] = a[i] + cnt;
        }
        cout << ans[i] << ' ';
    }
    cout << 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?