競プロ日記#25/09/06

典型90問の復習

AtCoder Beginner Contest 158

D - String Formation

• 初のD問題自力AC（茶Diffだけど...）
• 重要な点が3つあった。

1. Dequeを使うことで両端へのアクセスがしやすくなる。
2. Reverseの操作は計算量が膨れてしまうので実際にReverseするのはT == 1となるクエリがトータルで奇数回だった場合に最後に1度だけ行う。それまではReverse状態をフラグで管理して前後どちらにcharを追加するか制御する。
3. T == 1の時に文字列Sの先頭と最後をSwapするのだと勘違いしてペナってしまった。ちゃんと例を見るべきだった。

int main() {
    string S;
    cin >> S;
    long long Q;
    cin >> Q;
    deque <char> D;
    
    for (long long i = 0; i < S.size(); i++){
        D.push_back(S[i]);
    }
    long long revCount = 0;
    bool isRev = false;

    for (long long i = 0; i < Q; i++){
        long long T;
        cin >> T;
        if (T == 1){
            revCount++;
            isRev = !isRev;
        }
        
        if (T == 2){
            long long F;
            char C;
            cin >> F >> C;
            if (isRev == true){
                F = 3 - F;
            }
            if (F == 1){
                D.push_front(C);
            }
            if (F == 2){
                D.push_back(C);
            }
        }
    }
    if (revCount % 2 == 1){
        reverse(D.begin(), D.end());
    }

    cout << string(D.begin(), D.end()) << endl;
}

C - Unlucky 7

• アルゴ式やっててよかった案件。
• if (to_string(i).find('7') == string::npos && decimalToBaseN(8,i).find('7') == string::npos)のようにfind()で7の有無を確認する
• 解説によるとPythonやRubyは記数法の変換が標準メソッドで用意されているらしい。ずるい

// N進数の文字列 S を 10進数に変換
long long baseNToDecimal(long long N,string S) {
   
    long long sum = 0;
    long long base = 1;  // N^i を逐次計算
    for (long long i = S.length() - 1; i >= 0; --i) {
        long long digit = S[i] - '0';
        sum += digit * base;
        base *= N;
    }
}



// 10進数の整数 S を N進数の文字列に変換
string decimalToBaseN(long long N,long long S) {  
    string reversed;
    if (S == 0){
        return "0";
    }
    while(S > 0){
        reversed += to_string(S % N);
        S = S / N;
    }
    reverse(reversed.begin(),reversed.end());
    return reversed;
}



int main() {
    long long N;
    cin >> N;

    long long ans = 0;
    for (long long i = 1; i <= N;i++){
        if (to_string(i).find('7') == string::npos && decimalToBaseN(8,i).find('7') == string::npos){
            ans++;
        }
    }
    cout << ans << endl;
}

競技プログラミングの鉄則

A61 - Adjacent Vertices

• グラフ問題の入門問題

int main() {
    long long N,M;
    cin >> N >> M;
    vector<long long> G[N+1];
    G[0].push_back(0);
    for (long long i = 0;i < M;i++){
        long long A,B;
        cin >> A >> B;
        G[A].push_back(B);
        G[B].push_back(A);
    }
    for (long long i = 1; i <= N;i++){
        cout << i << ": " << "{";
        for (long long j = 0; j < G[i].size();j++){
            if (j != 0){
                cout << ", ";
            }
            cout << G[i][j];
        }
        cout << "}" << endl;
    }
}

B61 - Influencer

• A問題の応用
• 答えとして求められているのは友達を最も多く持っている人の番号なので「友達が最も多い人の添え字」と「友達が最も多い人が持っている友達の数」を管理することに気を付ける

int main() {
    long long N,M;
    cin >> N >> M;
    vector<long long> G[100009];
    for (long long i = 1;i <= M;i++){
        long long A,B;
        cin >> A >> B;
        G[A].push_back(B);
        G[B].push_back(A);
    }
    long long ansSize = 0;
    long long ans = 0;
    for (long long i = 1;i <= N;i++){
        if (G[i].size() > ansSize) {
            ansSize = G[i].size();
            ans = i;
        }
    }

    cout << ans << endl;
}

A62 - Depth First Search

• 深さ優先探索の典型問題

long long N,M,A[100009],B[100009];
vector<long long> G[100009];
bool visited[100009];

void dfs(long long pos){
    visited[pos] = true;
    for (long long i = 0;i < G[pos].size(); i++){
        long long nex = G[pos][i];
        if (visited[nex] == false) {
            dfs(nex);
        }
    }
}

int main() {
    cin >> N >> M;
    for (long long i = 1; i <= M; i++) {
        cin >> A[i] >> B[i];
        G[A[i]].push_back(B[i]);
        G[B[i]].push_back(A[i]);
    }

    for (long long i = 1;i <= N;i++){
        visited[i] = false;
    }

    dfs(1);
    string Answer = "The graph is connected.";
    for (long long i = 1;i <= N;i++){
        if (visited[i] == false) Answer = "The graph is not connected.";
    }

    cout << Answer << endl;
}