LoginSignup
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@RubyLrving(ruby lrving)

AtCoder Beginner Contest 377

Posted at

A - Rearranging ABC

O(N)
文字列Sをソートします。
Sが"ABC"と等しいならYesを出力します。

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;
    cin >> S;
    sort(S.begin(), S.end());
    if(S == "ABC") cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

B - Avoid Rook Attack

O(NNN)
'#'が存在したマスに対して、x軸のマスを全て使用不可、y軸のマスを全て使用不可にします。
3重ループの問題になります。

x軸のマスを全て使用不可、y軸のマスを全て使用不可にする処理を関数化しておくと分かりやすいですね。
最近はラムダ式で書くようにしています。
新しいC++のバージョンに慣れていかないといけないです。

C++
auto used = [](const int x, const int y, int (&graph)[8][8]){
    for(int i=0; i<8; i++){
        graph[y][i] = 1;
        graph[i][x] = 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 N = 8;
    vector<string> S(N);
    rep(i, N) cin >> S[i];
    
    int graph[8][8];
    memset(graph, 0, sizeof(graph));
    auto used = [](const int x, const int y, int (&graph)[8][8]){
        for(int i=0; i<8; i++){
            graph[y][i] = 1;
            graph[i][x] = 1;
        }
    };

    rep(i, N){
        rep(j, N){
            if(S[i][j] == '#'){
                used(j, i, graph);
            }
        }
    }

    int ans = 0;
    rep(i, N){
        rep(j, N){
            if(graph[i][j] == 0) ans++;
        }
    }
    cout << ans << endl;

    return 0;
}

C - Avoid Knight Attack

O(MlogM)
M個のコマが置かれます。
将棋の桂馬、チェスのナイトの動きをします。

x, y
2, 1
2, -1
1, 2
1, -2
-1, 2
-1, -2
-2, 1,
-2, -1

2重ループで処理ができそうです。

C++
for(auto j:{-1, 1}){
    for(auto k:{-2, 2}){
        st.insert({a+j, b+k});
        st.insert({a+k, b+j});
    }
}

新しくコマを置いた時に、M個のコマに取られない位置へ配置します。
またM個のコマがある位置にも配置できません。
M個のコマの移動できる位置は重複します。
setなどのデータ構造を使用します。
出力するデータは、

ans = N * N - (M個のコマの移動できる位置とM個のコマの位置の合計)

となります。
実装しましょう。

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() {
    ll N, M;
    cin >> N >> M;
    set<pair<ll, ll>> st;

    rep(i, M){
        ll a, b;
        cin >> a >> b;
        st.insert({a, b});
        for(auto j:{-1, 1}){
            for(auto k:{-2, 2}){
                st.insert({a+j, b+k});
                st.insert({a+k, b+j});
            }            
        }
    }
    ll ans = N * N;
    for(auto [x, y]:st){
        if(0<x && x<=N && 0<y && y<=N) ans--;
    }
    cout <<  ans << endl;

    return 0;
}

D - Many Segments 2

O(M)
尺取り法の問題です。
Lではなく、Rを固定すると簡単に処理ができます。
サンプル1を例に考察します。

2 4
1 2
3 4

区間[L_i,R_i]を含まないとは、R=2と固定した際、Lの最大値である1以下のl, rの組み合わせを含まないことです。

ans += R - L(i以下の要素で最大のLの値)

を加算していくと答えが求まります。
この問題の鍵は、R_iに対応する最大のLの値を求める事にあります。
Mの制約は2*10^5なので、Rの値の範囲を配列で管理できます。
Rに対応する最大のLを以下の前処理で求めておきます。

C++
vector<ll> P(M+1, 0);
rep(i, N){
    ll l, r;
    cin >> l >> r;
    P[r] = max(P[r], l);
}

P[r] = max(P[r], l);

を思いつくのが大事です。
R=0をMまでループして、R - Lの合計を求めると答えになります。
実装してみましょう。

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() {
    ll N, M;
    cin >> N >> M;
    vector<ll> P(M+1, 0);
    rep(i, N){
        ll l, r;
        cin >> l >> r;
        P[r] = max(P[r], l);
    }
    
    ll left = 0;
    ll ans = 0;
    for(ll right = 1; right<=M; right++){
        left = max(left, P[right]);
        ans += right - left;
    }
    cout << ans << endl;

    return 0;
}
2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?