AtCoder Beginner Contest 370

A - Raise Both Hands

O(1)
シミュレート

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 L, R;
    cin >> L >> R;

    if(L == 1 && R == 0){
        cout << "Yes" << endl; 
        return 0;
    }

    if(L == 0 && R == 1){
        cout << "No" << endl; 
        return 0;
    }

    cout << "Invalid" << endl; 
    return 0;
}

B - Binary Alchemy

O(N)
シミュレート

元素iと元素jを合成すると、

i≥jのとき元素Ai,j
i<jのとき元素Aj,i

と問題文に条件が記載されています。

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<vector<int>> A(N);

    for(int i=0; i<N; i++){
        for(int j=0; j<i+1; j++){
            int a;
            cin >> a;
            a--;
            A[i].push_back(a);
        }
    }

    int ans = 0;
    for(int i=0; i<N; i++){
        if(i < ans) ans = A[ans][i];
        else ans = A[i][ans];
    }
    cout << ans + 1 << endl;

    return 0;
} 

C - Word Ladder

O(NNlogN)
全探索

まず問題文の理解をしましょう。
辞書順とは何か

aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac

のように先頭の文字列から若いアルファベット順に並んでいる事です。
C++のプログラムではvectorをsort関数で並び替えすると簡単にできます。

答えを格納する配列Xを宣言。
SとTの文字列を一文字ずつ比較します。
文字が異なった際に、S,iをT,iに置き換えて文字列Cとします。
SとTが２文字以上異なった時、文字列Cは複数できます。
一文字だけ置き換えた文字列Cを辞書順に並び替え、先頭の文字列を配列Xに追加します。
これを繰り返します。

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() {
    string S, T;
    cin >> S >> T;

    vector<string> ans;
    while(S != T){
        vector<string> A;
        for(int i=0; i<S.size(); i++){
            string U = S;
            if(U[i] != T[i]){
                U[i] = T[i];
                A.push_back(U);
            }
        }
        sort(A.begin(), A.end());
        ans.push_back(A[0]);
        S = A[0];
    }

    cout << ans.size() << endl;
    for(auto a:ans){
        cout << a << endl;
    }

    return 0;
} 

D - Cross Explosion

O(QlongHlongW)
二分探索の問題です。

BFSを使用するとTLEになります。
この問題はメモ帳を使用して図を作成すると理解度が上がります。
コンテスト中も図を書きましょう。

サンプルの入力１を図にしました。
②は１回目の1,2で破壊される壁を表しています。
③は２回目の1,2で破壊される壁を表しています。
④は３回目の1,3で破壊される壁を表しています。
指定のマスから上、下、左、右の４方向を探索して、壁が存在していた場合に破壊します。

上、下方向を二分探索するためにHWの２次元配列w
左、右方向を二分探索するためにHWの２次元配列h

を用意して、縦、横をlonNの二分探索しましょう。
要素を削除する時は、２次元配列hwを同時に削除しましょう。

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 H, W, Q;
    cin >> H >> W >> Q;
    vector<set<int>> h(H), w(W);
    rep(i, H){
        rep(j, W){
            h[i].insert(j);
            w[j].insert(i);
        }
    }

    auto erase = [&](int i, int j){
        h[i].erase(j);
        w[j].erase(i);
    };

    for(int i=0; i<Q; i++){
        int r, c;
        cin >> r >> c;
        r--; c--;

        if(h[r].count(c)){
            h[r].erase(c);
            w[c].erase(r);
            continue;
        }

        {
            auto itr = h[r].lower_bound(c);
            if(itr != h[r].begin()) erase(r, *prev(itr));
        }

        {
            auto itr = h[r].lower_bound(c);
            if(itr != h[r].end()) erase(r, *itr);
        }

        {
            auto itr = w[c].lower_bound(r);
            if(itr != w[c].begin()) erase(*prev(itr), c);
        }

        {
            auto itr = w[c].lower_bound(r);
            if(itr != w[c].end()) erase(*itr, c);
        }
    }

    int ans = 0;
    for(int i=0; i<H; i++) ans += h[i].size();
    cout << ans << endl;

    return 0;
}