ABC157を振り返る

セグ木を覚えるチャンスが巡って来ましたね。

AtCoder Beginner Contest 157 - AtCoder

A問題

A - Duplex Printing NをKで割った時の繰り上げを表現したい時、(N+(K-1))/Kで出せます。天才かな? 今回なら(N+1)/2を出力すれば良いです。

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

void solve() {
    int N;
    cin >> N;
    cout << (N+1)/2 << endl;
}

int main() {
    solve();
    return 0;
}

B問題

B - Bingo ビンゴカードのライン数は(2N+2)です。縦のライン+横のライン+対角線のラインです。 今回は8LINE用意すれば良いです。

二次元配列を使って、ビンゴカードを使用してうまく書いていきましょう。

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

void solve() {
    // 8lines
    vector<vector<int>> eight_lines(8);
    // create yoko
    REP(i,3) {
        vector<int> line(3);
        REP(j,3) {
            int A;
            cin >> A;
            line[j] = A;
        }
        eight_lines[i] = line;
    }
    // 4,5,6 create
    REP(i,3) {
        vector<int> line(3);
        REP(j,3) {
            line[j] = eight_lines[j][i];
        }
        eight_lines[3+i] = line;
    }
    // 7,8 create
    vector<int> seven_line(3);
    seven_line[0] = eight_lines[0][0];
    seven_line[1] = eight_lines[1][1];
    seven_line[2] = eight_lines[2][2];

    eight_lines[6] = seven_line;

    vector<int> eight_line(3);
    eight_line[0] = eight_lines[2][0];
    eight_line[1] = eight_lines[1][1];
    eight_line[2] = eight_lines[0][2];

    eight_lines[7] = eight_line;

    // test
    for(const auto &lns: eight_lines) {
        for (const auto &l: lns) {
            cerr << l << " ";
        }
        cerr << endl;
    }

    vector<vector<bool>> is_opened(8,vector<bool>(3,false));

    int N;
    cin >> N;
    REP(i,N) {
        int b;
        cin >> b;
        REP(j,8) {
            REP(k,3) {
                if (eight_lines[j][k] == b) is_opened[j][k] = true;
            }
        }
    }

    REP(i,8) {
        if (all_of(ALL(is_opened[i]),[](bool x){ return x; })) {
            cerr << "opened " << i << endl;
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
    return;

}

int main() {
    solve();
    return 0;
}

C問題

C - Guess The Number 場合分けアンド場合分けアンド場合分け 貪欲に求めていけばいいです。 最終ケースが N==1,M==0っぽいので気をつけよう!(一敗)

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

void solve() {
    int N,M;
    cin >> N >> M;
    vector<int> rules(N+1,-1);
    bool failCheck = false;
    REP(_,M) {
        int s,c;
        cin >> s >> c;

        // 先頭に0は禁止
        if (s==1 && c==0) {
            failCheck = true;
        }

        if (rules[s] == -1) {
            rules[s] = c;
            continue;
        }

        // コリジョン
        if (rules[s] != c) {
            cout << -1 << endl;
            return;
        }
    }

    // 先頭が0でも良い場合
    if (failCheck) {
        if (rules[1] == 0 && N == 1) cout << 0 << endl;
        else cout << -1 << endl;
        return;
    }

    // maybe last case
    if (N == 1 && M == 0) {
        cout << 0 << endl;
        return;
    }

    REP(i,N) {
        // 最小
        auto mini = (i == 0) ? 1 : 0;
        // 制約があるならそれを使う
        cout << ( (rules[i+1] != -1) ? rules[i+1] : mini);
    }
    cout << endl;
}

int main() {
    solve();
    return 0;
}

D問題

D - Friend Suggestions Union-Findをコピペしました。(あまりにコピペなためコード略) 友達関係の数は属する友達関係のサイズから直接の友達の数とブロックし合っている数を引けば良いです。

E問題

E - Simple String Queries セグメント木を知っていますか?私は名前しか知りません。

記事書こうと思ったけど時間かかりそうなのでまた別記事にします。その時にでもば

Share on: