AtCoder Beginner Contest 371

A - Jiro

O(1)
二番目に年上の人はBのパターンを考察します。

a < b < c
c < b < a

この2パターンを条件にします。
二番目に年上の人は、AとCのパターンも同じです。

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() {
    char ab, ac, bc;
    cin >> ab >> ac >> bc;

    if((ab == '<' && ac == '>') || (ab == '>' && ac == '<')){
        cout << 'A' << endl;
    }

    if((ab == '<' && bc == '<') || (ab == '>' && bc == '>')){
        cout << 'B' << endl;
    }

    if((ac == '<' && bc == '>') || (ac == '>' && bc == '<')){
        cout << 'C' << endl;
    }
    return 0;
}

B - Taro

O(N)
N戸の家に長男が生まれたか配列taroで管理します。
長男が生まれたかどうかは、

taro[i] == false && B[i] == '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() {
    int N, M;
    cin >> N >> M;
    vector<int> A(M);
    vector<char> B(M);
    rep(i, M) cin >> A[i] >> B[i];

    vector<bool> taro(N+1, false);
    rep(i, M){
        if(!taro[A[i]] && B[i] == 'M'){
            taro[A[i]] = true;
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }

    return 0;
} 

C - Make Isomorphic

O(N^2 * N!)
この問題は難易度が高いです。
難易度が高いですが、この問題はC問題のレベルです。

C問題に出題される分類として、
全探索（dfs, bfs, 順列全探索, bit全探索）
簡単な累積和
簡単な二分探索
簡単な動的計画法
などがあり、今回は順列全探索に当たります。

類題としてC - Graph Isomorphismがあります。

グラフの同型を判定します。
頂点の番号に関係なく、同じ形をしているかになります。
グラフGとHの対応する頂点を直接判定するのではなく、頂点を管理する配列Pを中間テーブルとして用意します。

• GとPとHが示す頂点は同じ

グラフ	0	1	2	3	4
G	0	1	2	3	4
P	0	1	2	3	4
H	0	1	2	3	4

• Pを順列全探索して、Gの頂点0, 1とHの頂点2, 3を比較できるようにする

グラフ	0	1	2	3	4
G	0	1	2	3	4
P	2	3	0	1	4
H	0	1	2	3	4

この時、

G[u][v] != H[a][b]

なら、「Ai,j円を支払って、頂点iと頂点jを結ぶ辺がなければ追加し、あれば取り除く。」を行います。

cost += A[a][b]

考察したので実装します。

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;
    int Mg, Mh;
    cin >> Mg;
    bool G[30][30], H[30][30];
    rep(i, 30) rep(j, 30) G[i][j] = false;
    rep(i, 30) rep(j, 30) H[i][j] = false;
    int A[30][30];
    rep(i, 30) rep(j, 30) A[i][j] = 0;
    rep(i, Mg){
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u][v] = true;
        G[v][u] = true;
    }
    cin >> Mh;
    rep(i, Mh){
        int a, b;
        cin >> a >> b;
        a--, b--;
        H[a][b] = true;
        H[b][a] = true;
    }
    for(int i=0; i<N-1; i++){
        for(int j=i+1; j<N; j++){
            cin >> A[i][j];
            A[j][i] = A[i][j];
        }
    }

    vector<int> P;
    rep(i, N) P.push_back(i);

    int ans = 1e9;
    do {
        int cost = 0;
        for(int u=0; u<N; u++){
            for(int v=u+1; v<N; v++){
                int a = P[u];
                int b = P[v];
                if(G[u][v] != H[a][b]){
                    cost += A[a][b];
                }
            }
        }
        ans = min(ans, cost);
    }while(next_permutation(P.begin(), P.end()));

    cout << ans << endl;
    return 0;
} 

D - 1D Country

O(NlongNlongN)

X	0	1	2	3	4	5	6	7
P	0	1	0	2	0	3	0	4

L <= Xi <= Rの間にある村の村人の総数を表示します。

L = 0
R = 8
の時、10になります。

L = 5
R = 8
の時、7になります。
累積和が使えそうです。

X	0	1	2	3	4	5	6	7
PP	0	1	1	3	3	6	6	10

PP[7] - PP[4] = 7

あとはL、RとXの比較を行う必要があります。
Xは昇順に並んでいます。
二分探索を行うことで、LとRが示す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() {
    int N;
    cin >> N;
    vector<ll> X(N), P(N);
    rep(i, N) cin >> X[i];
    rep(i, N) cin >> P[i];
    int Q;
    cin >> Q;
    vector<ll> L(Q), R(Q);
    rep(i, Q) cin >> L[i] >> R[i];
    vector<ll> PP(N+1);
    rep(i, N) PP[i+1] = PP[i] + P[i];

    rep(i, Q){
        int l = lower_bound(X.begin(), X.end(), L[i]) - X.begin();
        int r = upper_bound(X.begin(), X.end(), R[i]) - X.begin();

        cout << PP[r] - PP[l] << endl;
    }

    return 0;
}