naoya_t@hatenablog

いわゆるチラシノウラであります

CSAcademy Round #40 (Div. 2 only)

CS Academy
agwたんと話してて、Dだけ見ようと思ったんだけど折角なのでA〜Cも見てみた
(そして、解いたやつをvirtual participationに放り込んだ)
4問解くのに2時間弱かかってたので多分4完だけど、時間切られて焦りながらやるのとは違うんで参考記録

D. Restricted Permutations

右へ左へジグザグと進む(可動域あり)
最初は空の配列に、i=1から順に入れていく
i=kの時の、kの位置ごとの場合の数、を長さNの配列でDP
・右に進む場合:最後の位置より右にならどこにでも置ける。それまでの並びの末尾より後に置かれる場合があるので、配列は右に伸びる。dp[k] を k+1 以降右端までのすべての位置に加算。(011111 + 001111 + 000111 + 000011 + 000001 みたいな);dpを左から右へaccumulateすることになる
・左に進む場合:〃左いならどこにでも置ける。それまでの並びの先頭より前に置かれる場合があるので、配列は左に伸びる。dp[k] を k-1 以前左端までのすべての位置に加算。(100000 + 110000 + 111000 + 111100 + 1111110 みたいな);dp
を右から左へaccumulateすることになる
→AC
手書きだけどメモを貼っておきます
f:id:n4_t:20170804171847j:plain
f:id:n4_t:20170804171859j:plain

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int i=0;i<n;++i)

const ll MOD = 1000000007LL;

ll solve(int n, vector<int>& a) {
    vector<ll> dp(4001, 0);
    int from = 2000, to = from;
    dp[from] = 1LL;
    rep(i, n-1) {
        vector<ll> tmp(4001, 0);
        if (a[i] == 1) {
            // 011...
            int acc = 0;
            for (int j=from; j<=to; ++j) {
                tmp[j] = acc;
                acc = (acc + dp[j]) % MOD;
            }
            tmp[++to] = acc;
        } else {
            // ...110
            int acc = 0;
            for (int j=to; j>=from; --j) {
                tmp[j] = acc;
                acc = (acc + dp[j]) % MOD;
            }
            tmp[--from] = acc;
        }
        dp = tmp;
    }

    ll ans = 0LL;
    for (int j=from; j<=to; ++j) {
        ans += dp[j];
    }
    return ans % MOD;
}

int main() {
    int n; cin >> n;
    vector<int> a(n-1);
    rep(i, n-1) cin >> a[i];
    cout << solve(n, a) << endl;
    return 0;
}

A. Erase Value

数ごとに集計して、合計のいちばん大きい数を捨てる
→AC

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)

int main() {
    int n; cin >> n;
    vector<int> s(1001, 0);
    int total = 0;
    rep(i,n) {
        int ai; cin >> ai;
        s[ai] += ai;
        total += ai;
    }
    int x = *max_element(s.begin(), s.end());
    int ans = total - x;
    cout << ans << endl;
    return 0;
}

B. Move the Bishop

最初斜めじゃなくて縦横に動かしてたわ
64地点だしワーシャルフロイドでいいわ
→AC

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define INF 1000

inline int IX(int y, int x) {
    if (y < 0 || 8 <= y || x < 0 || 8 <= x) return -1;
    return y*8 + x;
}

int solve(int r1, int c1, int r2, int c2) {
    int d[64][64];
    rep(i,64) rep(j,64) d[i][j] = INF;
    rep(y,8) rep(x,8) {
        int f = IX(y,x), g;
        d[f][f] = 0;
        for (int i=1; i<8; ++i) {
            g = IX(y-i, x-i);
            if (g >= 0) d[f][g] = d[g][f] = 1;
            g = IX(y-i, x+i);
            if (g >= 0) d[f][g] = d[g][f] = 1;
            g = IX(y+i, x-i);
            if (g >= 0) d[f][g] = d[g][f] = 1;
            g = IX(y+i, x+i);
            if (g >= 0) d[f][g] = d[g][f] = 1;
        }
    }
    rep(i,64) rep(j,64) rep(k,64) {
        if (d[i][j] > d[i][k] + d[k][j])
            d[i][j] = d[i][k] + d[k][j];
    }
    int ans = d[IX(r1,c1)][IX(r2,c2)];
    return ans < INF ? ans : -1;
}

int main() {
    int r1,c1,r2,c2; cin >>r1>>c1>>r2>>c2;
    --r1; --c1; --r2; --c2;
    cout << solve(r1,c1,r2,c2) << endl;
    return 0;
}

C. Switch the Lights

これは左から取るだけ、でaccumulateしていく(各スイッチの終端を -1 しておいてaccumulateの途上で伏線回収)
これって-1になることはないよね
最初 i≦R_i という制約を見逃してて問題を難しくしてた
→AC

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define rep(var,n)  for(int var=0;var<(n);++var)

#define INTSPACE 11
char _buf[INTSPACE*1000000 + 3];

int loadint() {
    if (fgets(_buf, INTSPACE+3, stdin)==NULL) return 0;
    return atoi(_buf);
}
int loadvec(vector<int>& v, int N=-1) {
    if (N == -1) {
        N = loadint();
        if (N==0) return 0;
    }
    int bufsize = INTSPACE*N + 3;
    if (fgets(_buf, bufsize, stdin)==NULL) return 0;
    v.resize(N);

    int i=0;
    bool last = false;
    for (char *p=&_buf[0]; ;) {
        char *q = p;
        while (*q > ' ') ++q;
        if (*q == 0x0D || *q == 0x0A) last = true;
        *q = 0;
        v[i++] = atoi(p);
        if (last || i == N) break;
        p = q+1;
    }
    // assert(i <= N);
    return i;
}


ll solve(int N, vi& oi, vi& R, vi& C) {
    ll total = 0LL;
    vi io(N+1, 0);
    int acc = 0;
    rep(i, N) {
        int till = R[i]-1;
        acc ^= io[i];
        if (oi[i] ^ acc) {
            total += C[i];
            acc ^= 1;
            io[till+1] ^= 1;
        }
    }
    return total;
    // return -1LL;
}

int main() {
    int N = loadint();
    
    fgets(_buf, N+3, stdin);
    
    vector<int> oi(N, 0);
    rep(i, N) oi[i] = _buf[i] - '0';
    
    vector<int> R(N), C(N);
    loadvec(R, N);
    loadvec(C, N);
    
    ll ans = solve(N, oi, R, C);
    cout << ans << endl;
    
    return 0;
}

E. Direct the Graph

開いてない