AtCoder Regular Contest 062 review

Link

• ARC 062 top page
• Editorial

C – AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

• Problem

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

using namespace std;

typedef long long ll;

ll t[1005];
ll a[1005];

int main(){
    //freopen("c3.in", "r", stdin);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lli %lli", &t[i], &a[i]);
    }
    ll currentT = 1, currentA = 1;
    for (int i = 0; i < n; ++i) {
        ll multiT = (currentT - 1LL) / t[i] + 1LL;
        ll multiA = (currentA - 1LL) / a[i] + 1LL;
        ll multi = max(multiT, multiA);
        currentT = t[i] * multi;
        currentA = a[i] * multi;
        //printf("%d %lli %lli %lli %lli\n", i, multiT, multiA, currentT, currentA);
    }
    printf("%lli\n", currentT + currentA);
    return 0;
}

D – AtCoDeerくんと変なじゃんけん / AtCoDeer and Rock-Paper

• Problem

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

using namespace std;

int main(){
    freopen("d2.in", "r", stdin);
    string s;
    cin >> s;

    int totalWin = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (i%2 == 0) {
            if (s[i] == 'g') {

            } else {
                totalWin--;
            }
        } else {
            if (s[i] == 'g') {
                totalWin++;
            }
        }
    }

    printf("%d\n", totalWin);
    return 0;
}

E – AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer

• Problem

Implementation based on Editorial.

/*
 * Ref: editorial - http://arc062.contest.atcoder.jp/data/arc/062/editorial.pdf
 */
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>

#define MAX_N 405
#define MAX_C 1000

using namespace std;
typedef long long ll;

int c[MAX_N][4];

ll calc(ll c0, ll c1, ll c2, ll c3) {
    return c0 * MAX_C * MAX_C * MAX_C + c1  * MAX_C * MAX_C + c2 * MAX_C + c3;
}

ll normalizeC(int* start) {
    ll minimum = calc(start[0], start[1], start[2], start[3]);
    for (int i = 0; i < 4; ++i) {
        ll next = calc(start[(0+i)%4], start[(1+i)%4], start[(2+i)%4], start[(3+i)%4]);
        if (minimum > next) {
            minimum = next;
        }
    }
    return minimum;
}

ll normalizeC(int a, int b, int c, int d) {
    int s[4] = {a, b, c, d};
    return normalizeC(s);
}

ll multi(int a, int b, int c, int d) {
    if (a==b && b==c && c==d) return 4;
    if (a==c && b == d) return 2;
    else return 1;
}

int main(){
    //freopen("e3.in", "r", stdin);
    int n;
    scanf("%d", &n);

    map<ll, int> tileMap;
    for (int i = 0; i < n; ++i) {
        scanf("%d %d %d %d", &c[i][0], &c[i][1], &c[i][2], &c[i][3]);
        ll key = normalizeC(c[i]);
        tileMap[key]++;
        //cout << key << ": " <<tileMap[key] << endl;
    }

    ll total = 0;
    for (int i = 0; i < n; ++i) {        // Determine side '1'
        for (int j = i+1; j < n; ++j) {  // Determine side '5'
            ll key1 = normalizeC(c[i]);
            ll key5 = normalizeC(c[j]);
            tileMap[key1]--;
            tileMap[key5]--;
            for (int k = 0; k < 4; ++k) {// Determine rotation of '5'
                ll key2 = normalizeC(c[i][0], c[j][(1+k)%4], c[j][(0+k)%4], c[i][1]);
                ll multiple2 = multi(c[i][0], c[j][(1+k)%4], c[j][(0+k)%4], c[i][1]);
                ll key3 = normalizeC(c[i][1], c[j][(0+k)%4], c[j][(3+k)%4], c[i][2]);
                ll multiple3 = multi(c[i][1], c[j][(0+k)%4], c[j][(3+k)%4], c[i][2]);
                ll key4 = normalizeC(c[i][2], c[j][(3+k)%4], c[j][(2+k)%4], c[i][3]);
                ll multiple4 = multi(c[i][2], c[j][(3+k)%4], c[j][(2+k)%4], c[i][3]);
                ll key6 = normalizeC(c[j][(1+k)%4], c[i][0], c[i][3], c[j][(2+k)%4]);
                ll multiple6 = multi(c[j][(1+k)%4], c[i][0], c[i][3], c[j][(2+k)%4]);
                //cout << key1 << " " << key5 << ": " << key2 << " " << key3 << " "<< key4 << " " << key6 << endl;
                //cout << tileMap[key2] << " " << tileMap[key3] << " "<< tileMap[key4] << " " << tileMap[key6] << endl;
                ll tmp;
                tmp = tileMap[key2] * multiple2;  tileMap[key2]--;
                tmp *= tileMap[key3] * multiple3;  tileMap[key3]--;
                tmp *= tileMap[key4] * multiple4;  tileMap[key4]--;
                tmp *= tileMap[key6] * multiple6;
                tileMap[key2]++; tileMap[key3]++; tileMap[key4]++;
                total += tmp;
            }
            tileMap[key1]++;
            tileMap[key5]++;
        }
    }
    printf("%lli\n", total/3);

    return 0;
}