LoginSignup
2
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 411

Last updated at Posted at 2025-06-22

A - Required Length

問題文

O(1)
データ構造の問題です。
stringの長さを取得して比較しましょう。

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;
    string s;
    cin >> s >> n;

    if(s.length() >= n){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

B - Distance Table

問題文

O(N^2)
全探索の問題です。
制約が小さいので2重ループで処理ができます。

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> d(n-1);
    rep(i, n-1) cin >> d[i];

    rep(i, n){
        int sum = 0;
        repx(j, i, n-1){
            sum += d[j];
            cout << sum;
            if(j < n-1) cout << ' ';
        }
        cout << endl;
    }

    return 0;
}

C - Black Intervals

問題文

制約は、
1≤N,Q≤5×10^5
なので2重ループで全探索を行うとTLEを起こします。

別の手法を考察しましょう。
黒く塗られたマスが連続している区間の数をansとします。
a_iのマスを黒にした時、

  • 左右に黒があるならans--
  • 左右に黒がないならans++
  • 左右の片方のみ黒なら増減なし

a_iのマスを白にした時、

  • 左右に黒があるならans++
  • 左右に黒がないならans--
  • 左右の片方のみ黒なら増減なし

これでO(q)で処理をできます。
下記がコンテスト中のACのコードです。

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> a(q);
    rep(i, q) cin >> a[i];

    vector<bool> graph(n);

    if(n==1){
        rep(i, q){
            graph[a[i]-1] = !graph[a[i]-1];
            if(graph[a[i]-1]) cout << 1 << endl;
            else cout << 0 << endl;
        }
        return 0;
    }

    int cnt = 0;
    rep(i, q){
        graph[a[i]-1] = !graph[a[i]-1];

        if(graph[a[i]-1]){
            if(a[i]-2 >= 0 && graph[a[i]-2] && a[i] < n && graph[a[i]]){
                cnt--;
            }
            if(a[i]-2 >= 0 && graph[a[i]-2] == false && a[i] < n && graph[a[i]] == false){
                cnt++;
            }
            if(a[i]-2 < 0 && a[i] < n && graph[a[i]] == false){
                cnt++;
            }
            if(a[i]-2 >= 0 && graph[a[i]-2] == false && a[i] >= n){
                cnt++;
            }         
        }else{
            if(a[i]-2 >= 0 && graph[a[i]-2] && a[i] < n && graph[a[i]]){
                cnt++;
            }
            if(a[i]-2 >= 0 && graph[a[i]-2] == false && a[i] < n && graph[a[i]] == false){
                cnt--;
            }
            if(a[i]-2 < 0 && a[i] < n && graph[a[i]] == false){
                cnt--;
            }
            if(a[i]-2 >= 0 && graph[a[i]-2] == false && a[i] >= n){
                cnt--;
            } 
        }
        cout << cnt << endl;
    }

    return 0;
}

もっと綺麗にできないか考察しましょう。
if文の分岐パターンが多くなっているのは、vector<bool> graph(n);で記載しているのが問題です。
vector<bool> graph(n+2);ならa[i]-2、a[i] < nの判定がいらなくなりますね。

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> a(q);
    rep(i, q) cin >> a[i];

    vector<bool> graph(n+2);
    int ans = 0;
    rep(i, q){
        graph[a[i]] = 1 - graph[a[i]];

        if(graph[a[i]]){
            if(graph[a[i]-1] && graph[a[i]+1]){
                ans--;
            }else if(graph[a[i]-1] == false && graph[a[i]+1] == false){
                ans++;
            }      
        }else{
            if(graph[a[i]-1] && graph[a[i]+1]){
                ans++;
            }else if(graph[a[i]-1] == false && graph[a[i]+1] == false){
                ans--;
            }   
        }
        cout << ans << endl;
    }

    return 0;
}

コードはかなり整理されました。

D - Conflict 2

問題文

考察が必要な問題です。
まず全探索のコードを書いてみました。

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;
    string server = "";
    vector<string> pc(n);
    rep(i, q){
        int query;
        cin >> query;

        if(query == 1){
            int p;
            cin >> p;
            p--;
            pc[p] = server;
        }
        if(query == 2){
            int p;
            string s;
            cin >> p >> s;
            p--;
            pc[p] += s;            
        }
        if(query == 3){
            int p;
            cin >> p;  
            p--;
            server = pc[p];     
        }
    }
    cout << server << endl;

    return 0;
}

時間は2528msでTLE。
メモリは3627196KiBでMLE。
10^6の長さのstring型の連結がこの状態を発生させていると気づくことができます。
サーバーと関連ある文字列のみを処理しましょう。
逆順で処理をしてサーバーと関連ある文字列のみ保持をします。

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> op(q), p(q);
    vector<string> s(q);
    rep(i, q){
        cin >> op[i] >> p[i];
        if(op[i] == 2){
            cin >> s[i];
            reverse(s[i].begin(), s[i].end());
        }
    }

    int server = 0;
    string ans = "";
    for(int t = q-1; t>=0; t--){
        if(op[t] == 1){
            if(server == p[t]){
                server = 0;
            }
        }else if(op[t] == 2){
            if(server == p[t]){
                ans += s[t];
            }      
        }else {
            if(server == 0){
                server = p[t];
            }
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;

    return 0;
}

pのPCの文字をサーバーの文字で上書きするので、

C++
            if(server == p[t]){
                server = 0;
            }

サーバーの文字をpのPCの文字で上書きするので、

C++
            if(server == 0){
                server = p[t];
            }

ここが実装で難しい所です。
何度も復習したいですね。
クエリを逆順する以外の回答も記載します。
追加する文字列をindexで管理ます。
その時に親ID+追加する文字列をpairで管理します。
最後に逆順で文字列を復元していきます。
結局何かを逆順で処理をしないといけないですね。

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> pc(n+1);
    for(int i=0; i<=n; i++){
        pc[i] = i;
    }
    map<int, pair<int, string>> mp;
    int cnt = 0;
    rep(i, q){
        int query;
        cin >> query;

        if(query == 1){
            int p;
            cin >> p;
            pc[p] = pc[0];
        }
        if(query == 2){
            int p;
            string s;
            cin >> p >> s;
            reverse(s.begin(), s.end());
            int index = pc[p];
            pc[p] = n + cnt + 1;
            if(mp.find(index) != mp.end()){
                mp[pc[p]] = {index, s};
            }else{
                mp[pc[p]] = {-1, s};
            }
            cnt++;        
        }
        if(query == 3){
            int p;
            cin >> p;
            pc[0] = pc[p]; 
        }
    }
    string ans = "";
    if(mp.find(pc[0]) != mp.end()){
        auto item = mp[pc[0]];
        while(item.first != -1){
            string s = item.second;
            ans += s;
            item = mp[item.first];
        }
        string s = item.second;
        ans += s;
        reverse(ans.begin(), ans.end());
    }
    cout << ans << endl;

    return 0;
}
2
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
2
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?