LoginSignup
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 382

Posted at

A - Daily Cookie

O(N)
Dを(食べるクッキーの数)として、

math
ans = 箱の数 - (クッキーの数 - D)
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, D;
    cin >> N >> D;
    string S;
    cin >> S;
    int cnt = 0;
    rep(i, N) if(S[i] == '@') cnt++;
    cnt -= D;
    cout << N - cnt << endl;
    return 0;
}

B - Daily Cookie 2

O(N)
ループを最後から最初へ行います。
Dを(食べるクッキーの数)として、

C++
if(S[i] == '@' && D > 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() {
    int N, D;
    cin >> N >> D;
    string S;
    cin >> S;

    for(int i=N-1; i>=0; i--){
        if(S[i] == '@' && D > 0){
            S[i] = '.';
            D--;
        }
    }
    cout << S << endl;

    return 0;
}

C - Kaiten Sushi

O(NlogN)
まず問題文の意味を理解しましょう。
サンプル１を例に、

1 2 3
美食度 3 8 2
美味しさ 5 2 1

美味しさ5, 2, 1の順に寿司が流れていきます。
美食度3, 8, 2の順に判定を行います。
問題文に、「美味しさが自分の美食度以上である寿司が自分の前に流れてきたときはその寿司を取って食べる」とあります。
美食度3の席より後には、美味しさ3以上の寿司は流れていきません。
よって判定するのは、

1 2 3
美食度 3 2
美味しさ 5 2 1

だけで良いです。
美食度の人は単調減少で並んでいます。
美味しさ2の寿司を判定する時、美食度2以上で最も美食度が低い人を探索します。
これは二分探索で探索できそうです。

私はコンテスト中、みんなで美味しい料理を分け合う優しい心があり、問題文の意味を理解できませんでした。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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, M;
    cin >> N >> M;
    vector<P> A;
    rep(i, N){
        int a;
        cin >> a;
        if(A.size()){
            if(A.back().first > a) A.push_back({a, i+1});
        }else{
            A.push_back({a, i+1});
        }
    }

    rep(i, M){
        int b;
        cin >> b;
        int ok = 0;
        int ng = A.size()-1;

        while(abs(ok - ng)>0){
            int mid = (ok + ng) / 2;
            if(A[mid].first <= b){
                ng = mid;
            }else{
                ok = mid+1;
            }
        }

        if(A[ok].first <= b ) cout << A[ok].second << endl;
        else cout << -1 << endl;
    }

    return 0;
}

これは自力ACのコードです。
実際はもっと良いコーディングがあります。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    rep(i, N) cin >> A[i];
    rep(i, M) cin >> B[i];
    rep(i, N-1) A[i+1] = min(A[i+1], A[i]);

    rep(i, M){
        int index = lower_bound(A.begin(), A.end(), B[i], greater<int>()) - A.begin();
        if(index == N) cout << -1 << endl;
        else cout << index+1 << endl;
    }

    return 0;
}

ここが良い発想ですね。
pairで美食度、indexを保持しなくて良くなります。

C++
rep(i, N-1) A[i+1] = min(A[i+1], A[i]);

またlower_boundによる二分探索も、実装時のバグを減らす技の一つです。

C++
int index = lower_bound(A.begin(), A.end(), B[i], greater<int>()) - A.begin();

D - Keep Distance

O(N)
全探索の問題です。
サンプル1の

3 23

について考えましょう。

1 11 21
1 11 22
1 11 23
1 12 22
1 12 23
1 13 23
2 12 22
2 12 23
2 13 23
3 13 23

上記のような配列の要素を作成するにはdfsを使用します。

  1. 配列に要素を追加
  2. 再起処理の呼び出し
  3. 追加した要素を削除
  4. 1を加算し、「1」の処理に戻る

これを再起処理の関数内で行います。

C++
void dfs(int m, int n, vector<int> &a){
    // 再起処理の終了条件
    if(a.size() == n){
        ans.push_back(a);
        return;
    }
    // 最初は1
    int b = 1;
    // ２つ目の要素は前の値に10を加算した数
    if(a.size() > 0) b = a.back() + 10;
    // m以下の時にループを行う
    while(b<=m){
        // 配列に要素を追加
        a.push_back(b);
        // 再起処理の呼び出し
        dfs(m, n, a);
        // 追加した要素を削除
        a.pop_back();
        // 1を加算
        b++;
    }
}

これだけだとTLEになります。
今回の問題は枝刈りと呼ばれる計算量の削減が必要です。
残りのn桁の数を'b'に加算します。

10*(n-a.size()-1)
C++
// m以下の時にループを行う
while(b + 10*(n-a.size()-1)<=m)

考察が終わりました。

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; }

vector<vector<int>> ans;

void dfs(int m, int n, vector<int> &a){
    if(a.size() == n){
        ans.push_back(a);
        return;
    }

    int b = 1;
    if(a.size() > 0) b = a.back() + 10;

    while(b + 10*(n-a.size()-1)<=m){
        a.push_back(b);
        dfs(m, n, a);
        a.pop_back();
        b++;
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<int> a;
    dfs(M, N, a);

    cout << ans.size() << endl;
    rep(i, ans.size()){
        for(auto a:ans[i]){
            cout << a << ' ';
        }
        cout << 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() {
    int N, M;
    cin >> N >> M;

    vector<vector<int>> ans;
    auto f = [&](auto f, vector<int> a){
        if(a.size() == N){
            ans.push_back(a);
            return;
        }

        int b = 1;
        if(a.size() > 0) b = a.back() + 10;
        a.push_back(b);
        while(a.back() + 10*(N-a.size())<=M){
            f(f, a);
            a.back()++;
        }
    };

    f(f, vector<int>());

    cout << ans.size() << endl;
    rep(i, ans.size()){
        for(auto a:ans[i]){
            cout << a << ' ';
        }
        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?