AtCoder 267

Link

A

#include <bits/stdc++.h>
using namespace std;
string ss[100] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};
int main() {
    string a;
    cin >> a;
    int t = 0;
    for (int i = 0; i < 5; ++i) if (a == ss[i]) t = i;
    printf("%d", 6 - t - 1);
    return 0;
}

B

#include <bits/stdc++.h>
using namespace std;
int x[15], y[15];
int main() {
//    freopen("1.in", "r", stdin);
    string a;
    cin >> a;
    if (a[0] == '1') { printf("No"); return 0; }
    for (int i = 1; i <= 10; ++i) {
        x[i] = (a[i - 1] == '1');    
    }
    y[1] += x[7]; y[2] += x[4]; y[3] += x[8] + x[2];
    y[4] += x[5] + x[1]; y[5] += x[9] + x[3]; y[6] += x[6];
    y[7] += x[10];
    
    
    for (int i = 2; i <= 6; ++i) {
        if (y[i] == 0) {
            int LS = 0, RS = 0;
            for (int L = i - 1; L >= 1; --L) {
                if (y[L] != 0) LS = 1;
            }
            for (int R = i + 1; R <= 7; ++R) {
                if (y[R] != 0) RS = 1;
            }
            if (LS && RS) { printf("Yes"); return 0; }
        }
    }
    printf("No");
    return 0;
}

C

$$L$$から$$R$$までの一部とすると（$$R=L+M-1$$）、以下のような計算する$$

\sum{i=1}^{M}i\times A_i = \sum{i=L}^{R} i\times Ai-(L-1)\times \sum{i=L}^{R} A_i

$$

INFに注意する。

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 2e5 + 10;
int a[maxn];
ll b[maxn], c[maxn];
const ll INF = (1ll << 60);
int main() {
//    freopen("1.in", "r", stdin);
    int N, M;
    cin >> N >> M;
    ll MAX = -INF; 
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &a[i]);    
        b[i] = b[i - 1] + (ll)i * a[i];
        c[i] = c[i - 1] + a[i];
    }
    for (int i = 1; i <= N - M + 1; ++i) {
        ll TEMP = b[i + M - 1] - b[i - 1];
        ll T2 = c[i + M - 1] - c[i - 1];
        
        MAX = max(MAX, TEMP - (ll)(i - 1) * T2);
    }    
    printf("%lld", MAX);
    return 0;
}

D

Cのような直接計算するのは無理。

動的計画法を行う。

時間計算量$O(nm)$。

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 2010;
int a[maxn];
ll dp[maxn][maxn];
const ll INF = (1ll << 60);
int main() {
//    freopen("1.in", "r", stdin);
    int N, M;
    cin >> N >> M;
    ll MAX = -INF; 
    for (int j = 1; j <= M; ++j) dp[0][j] = -INF;    
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &a[i]);
        for (int j = 1; j <= M; ++j) dp[i][j] = -INF;    
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            if (j > i) break;
            dp[i][j] = dp[i - 1][j];
            dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + (ll)j * a[i]);
        }
        MAX = max(MAX, dp[i][M]);
    }    
    printf("%lld\n", MAX);
    return 0;
}

E

ダイクストラ法のように、プライオリティーキューを使うことで $O((N+M)log(N+M))$ で解くことができる。

もう一つの方法は、答えを二分探索で行いう。スタックでコストはX以下の頂点を入れる。

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 2e5 + 10;
vector<int>e[maxn];
ll a[maxn], g[maxn];
bool del[maxn];
int main() {
//    freopen("1.in", "r", stdin);
    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        scanf("%lld", &a[i]);
    }
    for (int i = 1; i <= M; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
        g[x] += a[y]; g[y] += a[x];
    }
    priority_queue<pair<ll,int> >q;
    for (int i = 1; i <= N; ++i) {
        q.push(make_pair(-g[i], i));
    }
    ll ans = 0;
    while(q.size()) {
        pair<ll,int>QQ = q.top(); q.pop();
        
        int x = QQ.second;
        
        if (del[x] || g[x] != -QQ.first) continue;
        
        del[x] = 1;
        ans = max(ans, -QQ.first);
        for (int i = 0; i < e[x].size(); ++i) {
            int t = e[x][i]; if (!del[t]) {
                g[t] -= a[x];
                q.push(make_pair(-g[t], t));
            }
        }
    //    printf("X = %d   ans = %d\n" , x, ans);
    }
    printf("%lld", ans);
    return 0;
}

F

木の直径を利用する。

木の直径の両端の頂点を $L,R$とおく。
このとき、任意の頂点 $u$ に対し、$L,R$ のいずれかは $u$ から最も遠い点である。

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 2e5 + 10;
vector<int>e[maxn];
int G[maxn][20], H[maxn][20];
int dep[maxn], n;
void dfs(int x, int fa, int F[][20]) {
    F[x][0] = fa;
    for (int i = 0; i < e[x].size(); ++i) {
        int u = e[x][i];
        for (int i = 1; i <= 17; ++i) F[x][i] = F[F[x][i - 1]][i - 1];    
        if (u == fa) continue;
        dfs(u, x, F);
    }
    return;
}
void init() {
    for (int i = 1; i <= n; ++i) dep[i] = 0;
}
void FIND(int x, int fa) {
    for (int i = 0; i < e[x].size(); ++i) {
        if (e[x][i] == fa) continue;
        dep[e[x][i]] = dep[x] + 1;
        FIND(e[x][i], x);
    }
}    
int get() {
    int mx = 0, ans = 0;
    for (int i = 1; i <= n; ++i) if (dep[i] > mx) mx = dep[i], ans = i;
    return ans;  
}
int solve(int x, int dis, int F[][20]) {
    int now = x;
    for (int i = 20; i >= 0; --i) if ((dis >> i) & 1) now = F[now][i];    
    return now == 0 ? -1 : now;
}    
int main() {
    //freopen("1.in", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n - 1; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    init();
    FIND(1, 0);
    int L = get();
    
    init();
    FIND(L, 0);
    int R = get();
    
    dfs(L, 0, G);
    dfs(R, 0, H);
          
    int Q;
    cin >> Q;
    for (int i = 1; i <= Q; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);    
        int TA = solve(x, y, G);
        int TB = solve(x, y, H);
        printf("%d\n", max(TA, TB));
    }
    return 0;
}

E

Ex