えんじにあ備忘録

脱よわよわエンジニアを目指すブログ

AtCoder Beginner Contest 287 に参加しました＆反省会

競技プログラミング

AtCoder Beginner Contest 287 の振り返り

  • A、B問題を解くことができた
  • A問題：数え上げ
  • B問題：数字を文字列として扱い比較した。文字列の切り抜きについて調べる
  • C問題：グラフ問題と見て即座にD問題に移った。しかし、一度探索したノードを再び探索した場合にNoとなるだけでは、と考えた
  • D問題：愚直に実装したが14のテストケースでTLEになった
    文字列の切り抜きに苦戦した
    添字の単純なミスに時間を取られた

A問題

atcoder.jp

方針

  • Si= ForとAgainstの数を数え上げて比較する

解説から

B問題

atcoder.jp

方針

  • 与えられた文字列Sの末尾3文字を切り出す
  • 切り出した文字列がTと一致するかを判定する
  • それぞれのi、jについてすべてを試す二重ループとなる

解説から

二分探索を活用する

  • Tを辞書順で昇順に並べ替えておく
  • 計算量はO(logM)
  • 制約がN,M ≤ 2*105と大きくなった場合、想定解では実行時間に間に合わないが、この方法なら余裕を持って間に合う https://atcoder.jp/contests/abc287/editorial/5606
 sort(begin(t), end(t)); // tは文字列を格納したベクター
    int answer = 0;
    for (int i = 0; i < n; ++i) {
        if (binary_search(begin(t), end(t), s[i].substr(3))) {
            answer += 1;
        }
    }

C問題

atcoder.jp

解説*1から

与えられたグラフがパスグラフ（一本道のようなダイアグラム）であるための必要条件 - 辺がちょうど N-1 本 - すべての頂点の次数が 2 以下 - グラフが連結

実装例

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u -= 1;
        v -= 1;
        //無向グラフのため(u,v)、（v,u）をベクターに格納する
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    // 辺がちょうど N-1 本かを確認
    if (m != n - 1) {
        cout << "No\n";
        return 0;
    }
    
    for (int i = 0; i < n; ++i) {
        // すべての頂点の次数が 2 以下かを確認
        if (graph[i].size() > 2) {
            cout << "No\n";
            return 0;
        }
    }
    vector<bool> reach(n);
    queue<int> que;
    reach[0] = true;
    que.push(0);
    while (not que.empty()) {
        const int u = que.front();
        que.pop();
        for (const int v : graph[u]) {
            if (not reach[v]) {
                reach[v] = true;
                que.push(v);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        // グラフが連結かを確認
        if (!reach[i]) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
}

D問題

atcoder.jp

方針

  • 文字a,bがマッチするとはa==b、a==?、b==?の場合
  • Sの先頭のx文字を切り抜いた文字列とSの末尾のT-x文字を切り抜いた文字列を結合した文字列S'とTの各文字がマッチするかを判定する
  • 二重ループになる →TLEになった原因

解説*2から

  • 各xについてS′とTがマッチするというのは「Sの先頭x文字とTの先頭x文字がそれぞれマッチし、さらにSの末尾∣T∣−x文字とTの末尾∣T∣−x文字がそれぞれマッチする」と言い換えられる
  • pre[i]をSの先頭i文字とTの先頭i文字がマッチするかどうかを表す配列、suf[i]iをS の末尾i文字とTの末尾i文字がマッチするかどうかを表す配列とし、前計算を行う事でx=0,1,2,…,∣T∣それぞれに対してO(1)で答えることが可能になる

実装例

#include <bits/stdc++.h>
using namespace std;

bool match_or_not(char a,char b){
    return a=='?' || b=='?' || a==b;
}

int main() {
    
    string S,T;
    cin>>S>>T;
    
    vector<int> pre(S.size()+1,false),suf(S.size()+1,false);
    
    pre[0] = true;
    for(int i=0;i<T.size();i++){
        if(!match_or_not(S[i],T[i]))break;
        pre[i+1] = true;
    }
    
    reverse(S.begin(),S.end());
    reverse(T.begin(),T.end());
    
    suf[0] = true;
    for(int i=0;i<T.size();i++){
        if(!match_or_not(S[i],T[i]))break;
        suf[i+1] = true;
    }
    
    for(int i=0;i<=T.size();i++){
        if(pre[i] && suf[T.size()-i])printf("Yes\n");
        else printf("No\n");
    }
    
    return 0;
}

*1:https://atcoder.jp/contests/abc287/editorial/5608

*2:https://atcoder.jp/contests/abc287/editorial/5631