AtCoder Grand Contest 007 review

Link

• AGC 007 top page
• Editorial

I felt you need more invetiveness/creativeness in this contest, and it was difficult. 

A – Shik and Stone

• Problem

Compared to ARC (regular contest), it is slightly difficult even from problem A.

The most elegant solution is to just check the number of ‘#’ is equal to \(W+H−1\) or not as explained in Editorial.

However, I could not notice it so I checked that we can actually go using only right or down or not.

/*
 * AC	3 ms	256 KB
 */
#include <cstdio>
#include <iostream>

using namespace std;

char a[8][9];

int main(){
    //freopen("a3.in", "r", stdin);
    int h, w;
    scanf("%d %d", &h, &w);
    for (int i = 0; i < h; ++i) {
        scanf("%s", &a[i]);
    }

    int curH = 0, curW = 0;

    while (curH != h-1 || curW != w-1) {
        a[curH][curW] = '.';
        if (curH+1 < h && a[curH+1][curW] == '#') {curH++;}
        else if (curW+1 < w && a[curH][curW+1] == '#') {curW++;}
        else break;
    }
    a[curH][curW] = '.';
    bool ans = true;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (a[i][j] == '#') ans = false;
        }
    }
    printf(ans ? "Possible\n" : "Impossible\n");

    return 0;
}

B – Construct Sequences

• Problem

You need to come up with one construction method which satisfies the 3 conditions.

Editorial way is much more easier than below construction.

/*
 * AC	10 ms	896 KB
 */
#include <cstdio>
#include <iostream>

using namespace std;

int p[20005];
int q[20005];
int a[20005], b[20005];

int main(){
    //freopen("b3.in", "r", stdin);
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &p[i]);
        q[p[i]] = i;
    }
    int lsum = 1, rsum = 1;
    for (int i = 1; i <= n; ++i) {
        lsum += q[i];
        a[i] = lsum + i;
    }
    for (int i = n; i > 0; --i) {
        rsum += q[i];
        b[i] = rsum + (n+1-i);
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d%c", a[i], i == n ? '\n' : ' ');
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d%c", b[i], i == n ? '\n' : ' ');
    }

    return 0;
}

C – Pushing Balls

• Problem

Since most of the participants could not solve it, I’ll skip this.

D – Shik and Game

• Problem

This algorithm takes \(O(N^2)\), which pass only 600 points.

/*
 *
 */
#include <cstdio>
#include <iostream>

#define INF 1000000000000000LL

using namespace std;
typedef long long ll;

ll x[100005];
ll dp[100005];  // dp[i]: minimum time until the exit
                 // after you get coin at i-th place and you haven't feed to the rest yet.

int main(){
    //freopen("d2.in", "r", stdin);
    int N, E, T;
    scanf("%d %d %d", &N, &E, &T);
    x[0] = 0;
    for (int i = 1; i <= N; ++i) {
        scanf("%lli", &x[i]);
    }
    dp[N] = E - x[N];
    //cout << "N = " << N << ", dp[N]= " << dp[N] << endl;
    for (int i = N - 1; i >= 0; --i) {
        dp[i] = INF;
        for (int j = i + 1; j <= N; ++j) {
            if ((2 * (x[j] - x[i+1])) > T) {
                dp[i] = min(dp[i], dp[j] + 3 * (x[j] - x[i+1]) + (x[i+1] - x[i]));
            } else {
                dp[i] = min(dp[i], dp[j] + (x[j] - x[i+1]) + T + (x[i+1] - x[i]));
            }
        }
        //cout << "i = " << i << ", dp[i]= " << dp[i] << endl;
    }

    printf("%lli\n", dp[0]);
    return 0;
}