AtCoder Beginner Contest 168 ABC168 参加記

4完で水パフォでした。長針は離散的に動きません。余弦定理がTwitterトレンドに入っていて笑っていました。

• 提出へのリンク

順位表

A - ∴ (Therefore)

確認します。

int main() {
    int N;
    cin >> N;
    if(N%10 == 3){
        cout << "bon" << endl;
        return 0;
    }
    int a[] = {2,4,5,7,9};
    rep(i,5){
        if(N%10 == a[i]){
            cout << "hon" << endl;
            return 0;
        }
    }
    cout << "pon" << endl;
}

B - ... (Triple Dots)

サイズの確認をしましょう。

int main() {
    int K;
    string S;
    cin >> K >> S;
    if(S.size() > K){
        rep(i,K){
            cout << S[i];
        }
        cout << "..." << endl;
    }    
    else{
        cout << S << endl;v
    }
}

C - : (Colon)

余弦定理を使いましょう。 です。長針は分の割合分だけ進んでいることに注意してください。。。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    double A, B, H, M;
    cin >> A >> B >> H >> M;
    double x = H * 2*PI / 12 + M/60 * 2*PI / 12;
    double y = M * 2*PI / 60;
    double theta = min(abs(x-y), 2*PI - abs(x-y));
    double c = A*A + B*B - 2 * A * B * cos(theta);
    cout << sqrt(c) << endl;
}

D - .. (Double Dots)

BFSして前の頂点をメモするだけでいいです。

vvec<int> G;
int main() {

    int N, M;
    cin >> N >> M;
    G.resize(N);
    vector<bool> visited(N, false);
    vector<int> ans(N);
    rep(i,M){
        int a, b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    queue<int> q;
    q.push(0);
    visited[0] = true;
    while(not q.empty()){
        int v = q.front();
        q.pop();
        for(auto &nv: G[v]){
            if(visited[nv])continue;
            ans[nv] = v;
            visited[nv] = true;
            q.push(nv);
        }
    }
    cout << "Yes" << endl;
    rep1(i,N){
        cout << ans[i]+1 <<endl;
    }
}

E - ∙ (Bullet)

となるペアごとに独立に場合の数を考え、最後にかけ算しましょう。や、に注意しましょう（注意せず通せませんでした）。

実装では、それぞれのペアに関して、約分していいので（今回は比が一致してれば仲が悪い）gcdで割り算した上で、で個数を管理しました。片方を確認したらもう片方は使わないので、フラグを管理しておくといいと思います。

ll gcd(ll a,ll b){
    if(b == 0) return a;
    return gcd(b, a%b);
}

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N),B(N);
    map<pair<ll, l_l>, ll> mp;
    rep(i,N){
        cin >> A[i] >> B[i];
        if(A[i] == 0 && B[i] == 0){
            mp[{0, {0LL,0LL}}]++;
            continue;
        }
        if(A[i] == 0 && B[i] != 0){
            mp[{2, {0,1}}]++;
            continue;
        }
        if(A[i] != 0 && B[i] == 0){
            mp[{-2, {1,0}}]++;
            continue;
        }
        ll G = gcd(abs(A[i]), abs(B[i]));
        A[i] /= G;
        B[i] /= G;
        if((A[i] < 0 && B[i] > 0) || (A[i] > 0 && B[i] < 0)){
            mp[{-1,{abs(A[i]),abs(B[i])}}]++;
        }
        if((A[i] > 0 && B[i] > 0) || (A[i] < 0 && B[i] < 0)){
            mp[{1,{abs(A[i]),abs(B[i])}}]++;
        }
    }
    mint ans = 1;
    mint ori = 0;
    for(auto &p: mp){
        int fugo = p.first.first;
        ll a = p.first.second.first;
        ll b = p.first.second.second;
        ll cnt = p.second;
        if(cnt == -1)continue; 
        if(cnt == 0)continue;
        if(fugo == 0){
            ori = cnt;
            continue;
        }
        pair<ll, l_l> gyaku = {-fugo, {b,a}};
        //逆符号で、逆のやつ{-fugo, {b,a}}が存在するかどうか
        if(mp[gyaku] > 0){
            //dump(gyaku);
            ll cnt2 = mp[gyaku];
            ans *= mint(2).modpow(cnt) + mint(2).modpow(cnt2) - 1;
            mp[gyaku] = -1;
        }
        else{
            ans *= mint(2).modpow(cnt);
        }
    }
    ans += ori;
    ans = ans - 1;
    cout << ans << endl;
}

F - Bracket Sequencing

まだ手をつけていません。