LoginSignup
1
1

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 401

Posted at

A - Status Code

O(1)
下記を判定しましょう。

200 <= N < 300
C++
#include <bits/stdc++.h>

using namespace std;

int main() {
    int N;
    cin >> N;
    if(200 <= N && N < 300) cout << "Success" << endl;
    else cout << "Failure" << endl;
    return 0;
}

B - Unauthorized

O(N)
loginをしているか状態を管理しましょう。

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

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    for(int i=0; i<N; i++) cin >> S[i];

    bool isLogin = false;
    int ans = 0;
    for(int i=0; i<N; i++){
        if(S[i] == "login") isLogin = true;
        if(S[i] == "logout") isLogin = false;
        if(S[i] == "private" && isLogin == false) ans++;
    }
    cout << ans << endl;
    
    return 0;
}

C - K-bonacci

O(N)
フィボナッチ数列の問題の亜種です。
２つ前までの要素の合計ではなく、K個前までの合計を探索します。

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

using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N+1);

    if(N < K){
        cout << 1 << endl;
        return 0;
    }

    for(int i=0; i<K; i++) A[i] = 1;

    int inf = 1e9;
    int sum = K;
    for(int i=K; i<=N; i++){
        A[i] = sum;
        sum = (A[i] + sum) % inf;
        sum = (sum - A[i-K] + inf) % inf;
    }
    cout << A[N] << endl;

    return 0;
}

累積和を使用すると簡単にコーディングできます。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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, K;
    cin >> N >> K;
    vector<int> A(max(N+1, K));
    vector<int> S(A.size()+1);

    rep(i, K) A[i] = 1;
    rep(i, K) S[i+1] = S[i] + A[i];

    const int mod = 1e9;
    for(int i=K; i<=N; i++){
        A[i] = (S[i] - S[i-K] + mod) % mod;
        S[i+1] = (S[i] + A[i]) % mod;
    }
    cout << A[N] << endl;

    return 0;
}

すぬけさんのコードは綺麗ですね。
いつも参考になります。

D - Logical Filling

O(N)
奇数と偶数の関係を求める問題です。
下記のサンプルで考察しましょう。

10 4
.o.??.?.??

oは連続しないという条件があります。
?が連続せず一つだけのグループでは?を最大で１つoに置き換えることができます。
??が連続して二つのグループでは??をo?と?oに置き換えることができ、oの位置を固定できない為、??となります。

.o.??.o.??

6 3
.o.???

??が連続して三つのグループでは???をo.oと置き換えることができます。

6 3
.o.o.o

?が奇数個のグループの場合、(n+1)/2にてoの最大数を求めて置き換えることができます。
?が偶数個のグループの場合、(n+1)/2にてoの最大数を求めるのみになります。

  1. oの数を求める
  2. ?の連続する数と、そのグループの数を探索する
  3. Kとoの数、置き換えることができるoの最大数を判定する
  4. ?の奇数と偶数を判定して?をoと.に置き換える

考察ができました。
コーディングします。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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, K;
    cin >> N >> K;
    string S;
    cin >> S;

    int circle = 0;
    for(int i=0; i<N; i++) if(S[i] == 'o') circle++;

    if(circle == K){
        for(int i=0; i<N; i++) if(S[i] == '?') S[i] = '.';
        cout << S << endl;
        return 0;
    }

    for(int i=0; i<N-1; i++) if(S[i+1] == 'o' && S[i] == '?') S[i] = '.';
    for(int i=N-1; i>0; i--) if(S[i-1] == 'o' && S[i] == '?') S[i] = '.';

    int cnt = 0;
    vector<pair<int, int>> question;
    for(int i=0; i<N; i++){
        if(S[i] == '?'){
            cnt++;
        }else if(cnt>0) {
            question.emplace_back(i - cnt, cnt);
            cnt=0;
        }
    }
    if(cnt > 0) question.emplace_back(N - cnt, cnt);

    int sum = 0;
    for(auto [i, cnt]:question){
        sum += (cnt + 1) / 2;
    }

    if(sum == K - circle){
        for(auto [index, cnt]:question){
            if(cnt % 2 == 1){
                for(int i=index; i<index+cnt; i++){
                    if((i-index) % 2 == 0) S[i] = 'o';
                    else S[i] = '.';
                }
            }
        }
    }
    cout << S << endl;

    return 0;
}

もっと綺麗にコーディングできます。

C++
#include <bits/stdc++.h>
#include <atcoder/all>
 
#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, K;
    cin >> N >> K;
    string S;
    cin >> S;

    rep(i, N){
        if(S[i] == 'o'){
            if(i) S[i-1] = '.';
            if(i+1<N) S[i+1] = '.';
        }
    } 

    int x = K - count(S.begin(), S.end(), 'o');

    vector<pair<int, int>> question;
    rep(i, N){
        if(S[i] == '?'){
            int l = i;
            while(i<N && S[i] == '?') i++;
            question.push_back({l, i});
        }
    }

    int mx = 0;
    for(auto [l, r]:question) mx += (r-l+1) / 2;

    if(x == 0){
        for(auto [l, r]:question){
            for(int i=l; i<r; i++) S[i] = '.';
        }
    }else if(x == mx){
        for(auto [l, r]:question){
            if((r-l) % 2 == 0) continue;
            rep(i, r-l){
                S[l+i] = "o."[i%2];
            }
        }
    }
    cout << S << endl;

    return 0;
}

すぬけさんのコードは綺麗ですね。
このコードを本番のコンテストでコーディングするのは難しい。

1
1
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
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?