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 395

Last updated at Posted at 2025-03-03

A - Strictly Increasing?

O(N)
ループ、比較の問題です。

A[i] >= A[i+1]

が成立している時にNoになります。

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

    rep(i, N-1){
        if(A[i] >= A[i+1]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;
}

B - Make Target

O(N^2)
この問題を見たときに数学っぽく回答したかったです。
考察を書きます。

x+y<Nの時、

  • min(x, y) % 2 == 0なら#
  • min(x, y) % 2 == 1なら.

x+y>=Nの時、

  • N % 2 == 0
    • min(x, y) % 2 == 1なら#
    • min(x, y) % 2 == 0なら.
  • N % 2 == 1
    • min(x, y) % 2 == 0なら#
    • min(x, y) % 2 == 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;

    rep(i, N){
        rep(j, N){
            if(i+j<N){
                int k = min(i, j);
                if(k%2==0){
                    cout << '#';
                }else{
                    cout << '.';
                }
            }
            if(i+j>=N){
                int k = max(i, j);
                if(N%2==1){
                    if(k%2==0){
                        cout << '#';
                    }else{
                        cout << '.';
                    }   
                }else{
                    if(k%2==1){
                        cout << '#';
                    }else{
                        cout << '.';
                    }                       
                }
            }
        }
        cout << endl;
    }

    return 0;
}

もっと分かりやすくできます。
下記のように四角で全部塗りつぶします。

###########
###########
###########
###########
###########
###########
###########
###########
###########
###########
###########

###########
#.........#
#.........#
#.........#
#.........#
#.........#
#.........#
#.........#
#.........#
#.........#
###########

###########
#.........#
#.#######.#
#.#######.#
#.#######.#
#.#######.#
#.#######.#
#.#######.#
#.#######.#
#.........#
###########

###########
#.........#
#.#######.#
#.#.....#.#
#.#.....#.#
#.#.....#.#
#.#.....#.#
#.#.....#.#
#.#######.#
#.........#
###########

###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.###.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

すぬけさんのコードは綺麗だなぁ。

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<string> S(N, string(N, '.'));

    rep(i, N){
        int r = N - i - 1;
        if(i>r) continue;
        char c = '#';
        repx(x, i, r+1){
            repx(y, i, r+1){
                if(i % 2 == 0) S[y][x] = '#';
                else S[y][x] = '.';
            }
        }
    }
    rep(i, N) cout << S[i] << endl;

    return 0;
}

C - Shortest Duplicate Subarray

O(logN)
mapで数値と位置を保持。
前回位置との距離を取ります。

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

    map<int, vector<int>> mp;
    int ans = 1e9+7;
    rep(i, N){
        if(mp[A[i]].size()){
            ans = min(ans, i - mp[A[i]].back() + 1);
        }
        mp[A[i]].push_back(i);
    }
    
    if(ans == 1e9+7) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}

よく考察するとmap<int, vector<int>>である必要はなかったです。

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

    map<int, int> mp;
    int ans = 1e9+7;
    rep(i, N){
        if(mp.find(A[i]) != mp.end()){
            ans = min(ans, i - mp[A[i]] + 1);
        }
        mp[A[i]] = i;
    }

    if(ans == 1e9+7) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}

map<int, int>で十分ですね。

D - Pigeon Swap

O(N)
まず単純な全探索をコーディングしてみましょう。
問題文のままに実装します。
TLEになります。

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, Q;
    cin >> N >> Q;
    vector<int> bard(N);
    vector<set<int>> nest(N);
    rep(i, N){
        bard[i] = i;
        nest[i].insert(i);
    }

    rep(i, Q){
        int op;
        cin >> op;

        if(op == 1){
            int a, b;
            cin >> a >> b;   
            a--; b--;         
            nest[bard[a]].erase(a);
            nest[b].insert(a);
            bard[a] = b;
        }

        if(op == 2){
            int a, b;
            cin >> a >> b;
            a--; b--;      
            for(auto ne:nest[a]){
                bard[ne] = b;
            }  
            for(auto ne:nest[b]){
                bard[ne] = a;
            }
            set<int> t = nest[a];
            nest[a] = nest[b];
            nest[b] = t;
        }

        if(op == 3){
            int a;
            cin >> a;
            a--;
            cout << bard[a] + 1 << endl;
        }
    }
    
    return 0;
}

どこが重いかというと、

C++
        if(op == 2){
            int a, b;
            cin >> a >> b;
            a--; b--;  
            // ここから
            for(auto ne:nest[a]){
                bard[ne] = b;
            }  
            for(auto ne:nest[b]){
                bard[ne] = a;
            }
            // ここまで
            set<int> t = nest[a];
            nest[a] = nest[b];
            nest[b] = t;
        }

鳩がどこの巣にいるか更新する処理です。
O(N^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, Q;
    cin >> N >> Q;
    vector<int> bard(N);
    vector<int> nest(N);
    rep(i, N){
        bard[i] = i;
        nest[i] = i;
    }

    rep(i, Q){
        int op;
        cin >> op;

        if(op == 1){
            int a, b;
            cin >> a >> b;   
            a--; b--;         
            bard[a] = nest[b];
        }

        if(op == 2){
            int a, b;
            cin >> a >> b;
            a--; b--;
            swap(nest[a], nest[b]);
        }

        if(op == 3){
            int a;
            cin >> a;
            a--;
            cout << nest[bard[a]] + 1 << endl;
        }
    }
    
    return 0;
}
サンプル3 入力
30 15
3 3
2 8 30
2 12 15
2 2 17
1 19 1
2 7 30
3 12
3 8
2 25 26
1 13 10
1 16 10
2 16 29
2 1 21
2 6 11
1 21 8

この入力で複数回の入れ替えがある

2 8 30
2 7 30

に注目しましょう。

  • nest
7 8 30
0 7 8 30
1 7 30 8
2 8 30 7

と入れ替わります。

3
15
30

表示結果となり、WAになります。
鳩と巣の中間を補完する配列を用意しましょう。

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, Q;
    cin >> N >> Q;
    vector<int> bard(N);
    vector<int> nest(N), lavel(N);
    rep(i, N){
        bard[i] = i;
        nest[i] = i;
        lavel[i] = i;
    }

    rep(i, Q){
        int op;
        cin >> op;

        if(op == 1){
            int a, b;
            cin >> a >> b;   
            a--; b--;
            bard[a] = lavel[b];
        }

        if(op == 2){
            int a, b;
            cin >> a >> b;
            a--; b--;
            swap(lavel[a], lavel[b]);
            swap(nest[lavel[a]], nest[lavel[b]]);
        }

        if(op == 3){
            int a;
            cin >> a;
            a--;
            cout << nest[bard[a]] + 1 << endl;
        }
    }
    
    return 0;
}

配列内のデータの入れ替えに注意しましょう。

  • nest
7 8 30
0 7 8 30
1 7 30 8
2 30 7 8
  • lavel
7 8 30
0 7 8 30
1 7 30 8
2 8 30 7

中間の配列をlavelを用意したことにより巣の配列nestに変化が出ました。
lavelは前回の巣と同じ結果ですが、
nestは、｀2 7 30｀のopの時にswap(nest[7], nest[8])が処理されます。
複数回の入れ替えに対応ができるようになっています。
上記のコードでACになりました。

感想

本番中に考察して、このような問題をACしたいですね。

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?