AtCoder Beginner Contest 084

バカ酒飲んで起きたら 20:55
年末は知り合い全員カウントダウン・ジャパンか帰省で暇なので，起き抜けの頭で ABC084 にレジる

163 位だった．100 位圏内は 30 分以内ということで，道のりは厳しく長そう．
レートは 1000 くらいしかないので普通に上がりそうだけど

A - New Year

48 - M を出力する．

int problemA() 
{
    int M;
    cin >> M;

    cout << 48 - M << endl;

    return 0;
}

B - Postal Code

粛々とやる

int problemB() 
{
    int A, B;
    string S;

    cin >> A >> B >> S;

    if (S[A] != '-') {
        cout << "No" << endl;
        return 0;
    }

    for (int i = 0; i <= A + B; i++) {
        if (i == A) continue;
        if (S[i] < '0' || '9' < S[i]) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

C - Special Trains

読解問題　理解したら素直に書けば通るが…

typedef long long lint;

int problemC()
{
    lint N;
    cin >> N;

    lint C[MAX + 1] = {};
    lint S[MAX + 1] = {};
    lint F[MAX + 1] = {};

    for (lint i = 1; i <= N - 1; i++) cin >> C[i] >> S[i] >> F[i];

    for (int i = 1; i <= N; i++) {
        // 開始式開始時 x = 0 に駅 i にいる
        lint x = 0;

        // 駅 j から駅 j + 1 に移動するのに要する時間を加算していく
        for (int j = i; j <= N - 1; j++) {
            // x は駅 j における最初の列車の発車時刻以降
            if (x <= S[j]) {
                x = S[j];
            }
            // x が F[j] で割り切れない時は，直後の発車時刻に合わせる
            else if (x % F[j] != 0) x = (x / F[j] + 1) * F[j];
            // 次の駅までの時間を加算する
            x += C[j];
        }
        cout << x << endl;
    }

    return 0;
}

D - 2017-like Number

範囲内の特殊な素数をカウントしていく問題．クエリの数が多くそのままだと死にそうなので累積和を用いる．

#define MAX 100000

// p[i] : i が素数かどうか
bool p[MAX + 1];
// pp[i] : i 以下の 2017-like number の個数
int pp[MAX + 1];

int problemD()
{
    // エラトステネスの篩
    for (int i = 2; i <= MAX; i++) p[i] = true;
    for (int i = 2; i * i <= MAX; i++) {
        for (int j = i * i; j <= MAX; j += i) {
            p[j] = false;
        }
    }
    
    // 2017-like number の列挙
    for (int i = 2; i <= MAX; i++) {
        int N = (i + 1) / 2;
        if (p[i] && p[N]) pp[i] = 1;
    }

    // 累積和
    for (int i = 2; i < MAX; i++) pp[i + 1] += pp[i];

    int Q;
    cin >> Q;

    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        // 範囲内の 2017-like number の個数を出力
        cout << pp[r] - pp[l - 1] << endl;
    }

    return 0;
}

感想：

A 問題　寝起きでボゲーとしながらサンプルコードを見て，M と 出力の和は 48 になるなー，などと考えながら適当に投げる．1:42

B 問題　粛々とやる問題だったので，はいという感じで書いたら，添字の i とすべき部分をコピペ後 A のまま放置してしまい，デバッグに 3 分ほど時間を浪費する．恥ずかしい．7:41

C 問題を見る　問題文が長い，年寄りは 3 行以上の文章を読むことができない　頑張って読むが 5 分くらい経過する．解法を考えるが脳が遅く，3 分くらい経ったとこで後回しを決め D 問題を見る．15 分くらい

D 問題　ヒャッハーと言いながら 5 分で書いた．篩のコードは最早コピーしてくるより手で書いたほうが速い．20:57

C 問題に戻る　ベッドの上でやっていたので机からメモ用紙とペンをひったくって落書きなどして整理してウンウン唸りながらコードを書いて提出．36:46

D を見る前に C で悩んだのが敗因か　A, B あたりを解いたらとりあえず残りの問題に全部目を通したほうがよさそう．