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 390

Last updated at Posted at 2025-01-29

A - 12435

O(N^2)
ソートの回数を探索しましょう。
ソートの回数が1の時、Yesです。

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 = 5;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    int cnt = 0;
    rep(i, n) for(int j=i+1; j<n; j++){
        if(a[i] > a[j]){
            swap(a[i], a[j]);
            cnt++;
        }
    }
    if(cnt==1) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

O(N)で回答することができます。
要素を一回だけ入れ替えた時、vector<int>({1, 2, 3, 4, 5})と等しいか判定します。

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 = 5;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    rep(i, n){
        swap(a[i], a[i+1]);
        if(a == vector<int>({1, 2, 3, 4, 5})){
            cout << "Yes"<< endl;
            return 0;
        }
        swap(a[i], a[i+1]);
    }
    cout << "No" << endl;
    return 0;
}

コンテスト中にこのようなコードが書けるようになりたいです。

B - Geometric Sequence

O(N)
配列Aが等比数列か判定します。
等比数列の条件は、

a_{i+1} / a_i = a_{i+2} / a_{i+1}

の条件を満たすことです。

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;
    cin >> n;
    vector<long double> a(n);
    rep(i, n) cin >> a[i];

    if(n==2){
        cout << "Yes" << endl;
        return 0;
    }

    long double r = a[1] / a[0];

    for(int i=0; i<n-1; i++){
        if(r != a[i+1] / a[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;
}

もう少し考察をしましょう。
判定を整数で行うことができます。

a_{i+1} / a_i = a_{i+2} / a_{i+1}

を

a_{i+1} * a_{i+1} = a_{i+2} * a_{i}

と式を変形します。

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;
    cin >> n;
    vector<long double> a(n);
    rep(i, n) cin >> a[i];
    for(int i=0; i<n-2; i++){
        if(a[i+1] * a[i+1] != a[i+2] * a[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

コンテスト中にこのようなコードが書けるようになりたいです。

C - Paint to make a rectangle

O(N)
#であるマスの最小のx, yを探索。
#であるマスの最大のx, yを探索。
範囲内のマスが#, ?なら、黒マス全体が長方形である条件を満たしています。

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 h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];

    int max_x = 0;
    int max_y = 0;
    int min_x = w;
    int min_y = h;

    rep(i, h) rep(j, w){
        if(s[i][j] == '#'){
            max_x = max(max_x, j);
            max_y = max(max_y, i);
            min_x = min(min_x, j);
            min_y = min(min_y, i);
        }
    }

    rep(i, h) rep(j, w){
        if(min_x <= j && j <= max_x && min_y <= i && i <= max_y){
            if(s[i][j] == '.'){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;

    return 0;
}

D - Stone XOR

O(N!)
dfsの全探索の問題です。
同じ袋に入れるA_iの要素を探索してグループ分けする問題です。
サンプル1を考察します。

3
2 5 7

は、

2 5 7
0 7 7
0 5 9
2 0 12
0 0 14

とパターン分けができます。
この処理を実装できるかが問題の鍵になります。

コンテスト中にTLEとなったコードを書きます。
グループ分けの手法が誤っています。
n=12の時、O(13^12)となっています。

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

set<ll> st;

void dfs(vector<ll> &A, int index){

    int n = A.size();

    if(index >= n){
        ll sum = 0;
        rep(i, n) sum ^= A[i];
        return;
    }

    dfs(A, index+1);

    ll t = A[index];
    A[index] = 0;
    for(int i=index+1; i<n; i++){
        A[i] += t;
        dfs(A, index+1);
        A[i] -= t;
    }
    A[index] = t;
}

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    dfs(A, 0);
    cout << st.size() << endl;
    return 0;
}

最初にn個の配列を用意して、各要素へb+=a, a=0と加算していく手法はダメだと分かります。
2次元配列groupを用意して、a[i]の要素をgroupに下記のように追加していきます。

  • すでにあるグループへ追加する
  • 新しいグループを作り追加する

O(N!)の処理になります。

[0] = {2, 5, 7}

[0] = {2, 5}
[1] = {7} 

[0] = {2, 7} 
[1] = {5}

[0] = {2} 
[1] = {5, 7}

[0] = {2}
[1] = {5}
[2] = {7}

のように処理を行います。

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;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    vector<ll> group;
    set<ll> st;
    auto dfs = [&](auto dfs, int v){
        if(v >= N){
            ll sum = 0;
            int n = group.size();
            rep(i, n){
                sum ^= group[i];
            } 
            st.insert(sum);
            return;
        }

        int n = group.size();
        rep(i, n){
            group[i] += A[v];
            dfs(dfs, v+1);
            group[i] -= A[v];
        }

        group.push_back(A[v]);
        dfs(dfs, v+1);
        group.pop_back();
    };
    dfs(dfs, 0);

    cout << st.size() << endl;
    return 0;
}

O(12!) = 479001600
処理速度は間に合うと思われますがTLEになりました。
setのデータ構造の問題です。

setは要素をソートして保持します。
O(logN)の為、TLEの原因になっています。
unordered_setを使用します。
unordered_setはハッシュ値に基づき、コンピュータにとって都合の良い任意の順序で要素を保持します。
O(1), O(N)で処理をできます。

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;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    vector<ll> group;
    unordered_set<ll> st;
    auto dfs = [&](auto dfs, int v){
        if(v >= N){
            ll sum = 0;
            int n = group.size();
            rep(i, n){
                sum ^= group[i];
            } 
            st.insert(sum);
            return;
        }

        int n = group.size();
        rep(i, n){
            group[i] += A[v];
            dfs(dfs, v+1);
            group[i] -= A[v];
        }

        group.push_back(A[v]);
        dfs(dfs, v+1);
        group.pop_back();
    };
    dfs(dfs, 0);

    cout << st.size() << endl;
    return 0;
}

ACできました。
全ての基本である全探索を学びました。
今回のABCは良問が揃っていたコンテストだと思います。

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?