競プロ勉強会 第2回

今回から新たに電電時代の学友Rくんも参加してくれました! 何回も一緒に定期テスト解いてるので知っていたのですが, さすがの賢さでした…

CODE FESTIVAL 2015 予選A D 壊れた電車

今までと同じようにチェック関数を用意してから二分探索を行う問題。p = max(minute - dist *2, (minute - dist)/2) + x[i] + 1;のところで詰まってました…

int n, m;
int x[100010];
bool isCheck(LL minute) {
    LL p = 0;
    REP(i, m) {
        int dist = x[i] - p;
        if (dist > minute) {
            return false;
        } else if (dist> 0) {
            p = max(minute - dist *2, (minute - dist)/2) + x[i] + 1;
        } else {
            p = max(p, x[i] + minute + 1);
        }
    }
    return p >= n;
}
int main(int argc, char *argv[]) {
    cin >> n >> m;
    REP(i, m) {
        cin >> x[i];
        x[i]--;
    }
    LL left = 0;
    LL right = n * 2;
    LL mid;
    while (right - left > 1) {
        mid = (right + left) / 2;
        if (isCheck(mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }
    if (isCheck(left)) {
        cout << left << endl;
    } else {
        cout << right << endl;
    }
    return 0;
}

ARC 060 C 高橋君とカード

全探索すればいけた問題。いろいろ小難しいことを考えがちだが, まず全探索や貪欲法を考えてそっからチューニングしていくべきだと思った。けど、これ一瞬で書いてるFさんには一生届かない気もしてます。

int n, a;
int x[51];
int main(int argc, const char *argv[])
{
    cin >> n >> a;
    REP(i, n) {
        cin >> x[i];
        x[i] -= a;
    }
    map<LL, LL> m;
    m[0] = 1;
    REP(i, n) {
        map<LL, LL> mTmp = m;
        REPI(it, mTmp) {
            m[it->first + x[i]] += it->second;
        }
    }
    cout << m[0] - 1 << endl;
    return 0;
}