naoya_t@hatenablog

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

Codeforces Round #415 (Div. 2)

こどふぉ参加三回目。
TCO R2Aが終わってすぐのタイミングで。(気づいたらすでに始まってたんだけど)
れじってなかったけれど、開始10分後からextra registrationで飛び入り参加できる制度を利用。

A. Straight «A» (x2367)

Problem - A - Codeforces
平均点を四捨五入して満点になるためにはあといくつ満点を取ればいいか。
k-0.5 <= (Σa_i + xk)/(n+x) < k+0.5 だよね
で、下限だけ見てて、答えが負の値になる可能性のあるコードを書いてた…

int main(){
    int n,k; cin >> n >> k; // 1-100
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    int s = 0;
    rep(i, n) s += a[i];
    // (s + kx)/(n+x) >= k-0.5
    int x = (k*2 - 1) * n - s*2;

    cout << x << endl;
    return 0;
}

そして

↑↑初めて見た!わーい!
修正して再提出。(こういう場合って単に再提出ペナルティ50ptが引かれるだけ、かな)

int main(){
    int n,k; cin >> n >> k; // 1-100
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    int s = 0;
    rep(i, n) s += a[i];
    // (s + kx)/(n+x) >= k-0.5
    int x = (k*2 - 1) * n - s*2;
    if (x < 0) x = 0; /// ←この1行

    cout << x << endl;
    return 0;
}

// pretest passed → hacked → pretest passed (→AC); 336 (0:57)

提出した問題のところに出てる "lock problem" ってアイコンは何?→人のコードを「ハック」(撃墜)するには自分の提出解をロックする必要がある、とのこと(ロックするともう再提出できない)。
(thanks to @agw)

B. Summer sell-off (x1544)

Problem - B - Codeforces
投げた解がWA出してた(のに気付かずにCやってた)。

int main(){
    int n,f; cin >> n >> f; // 1-100
    vector<int> k(n), l(n);
    rep(i, n) {
        cin >> k[i] >> l[i];
    }

    int s = 0;
    priority_queue<int> pq;
    rep(i, n) {
        if (k[i] > l[i]) k[i] = l[i];
        int sgl = min(k[i], l[i]);
        s += sgl;
        int dbl = min(k[i]*2, l[i]);
        pq.push(dbl - sgl);
    }
    rep(i, f) {
        s += pq.top(); pq.pop();
    }
    cout << s << endl;
    return 0;
}

解がINT_MAXを超える可能性があるからlong longに変えて再提出。(ペナルティ50pt)

int main(){
    ll n,f; cin >> n >> f; // 1-100
    vector<ll> k(n), l(n);
    rep(i, n) {
        cin >> k[i] >> l[i];
    }

    ll s = 0;
    priority_queue<ll> pq;
    rep(i, n) {
        if (k[i] > l[i]) k[i] = l[i];
        ll sgl = min(k[i], l[i]);
        s += sgl;
        ll dbl = min(k[i]*2, l[i]);
        pq.push(dbl - sgl);
    }
    rep(i, f) {
        s += pq.top(); pq.pop();
    }
    cout << s << endl;
    return 0;
}

// WA → pretest passed (→AC); 522 (1:47)

C. Do you want a date? (x1030)

Problem - C - Codeforces
ソートして、n個の中から2つ選んだ値について、これが部分集合の最小値・最大値になる回数を求める。5C2の両端としてx回、5C3の両端としてy回、みたいな。パスカルの三角形は同じ行(nCkのnが同じもの)を全部足し合わせると2の累乗 (2^n) になるのでそれを利用。で、これをnC2通り足し合わせる法(O(n^2) か)

// 略
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define found(s,e)  ((s).find(e)!=(s).end())

const ll M=1000000007LL;

ll ADD(ll x, ll y) { return (x+y) % M; }
ll SUB(ll x, ll y) { return (x-y+M) % M; }
ll MUL(ll x, ll y) { return x*y % M; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { return MUL(x, POW(y, M-2)); }

int main(){
    int n;
    vector<int> a;

    int n; cin >> n; // 1-3e5
    a.resize(n);
    rep(i, n) {
        cin >> a[i];
    }
    sort(all(a));

    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }
/*
    if (n == 2) {
        cout << a[1] - a[0] << endl;
        return 0;
    }
*/
    // O(n)
    vector<ll> pw(n+1);
    pw[0] = 1LL;
    rep(i, n) pw[i+1] = (pw[i] * 2LL) % M;

    // O(n^2)
    ll ans = 0;
    repC2(i,j,n) {
        ll d = a[j] - a[i];
        ll k = pw[j-i-1];
        ans = (ans + pw[j-i-1]*d) % M;
    }

    cout << ans << endl;
    return 0;
}

→1投目TLE;
iostream遅い?gets+atoiにして再提出。読み込みだけで1秒弱かかってたのを数十msecにまで落とせた(※ここで読み込み部分の所要時間しか計測してなかったのがTLEを2回も投げてしまった原因)
→2投目TLE;;
ああ。(3e5)^2 はO(n^2)だと2秒で解けない…ローカルで最悪ケース作って試したら全然帰ってこない
それぞれの値が、最大値、最小値として使われる回数を求めて、最大値で使われる合計 - 最小値で使われる合計、を求める。どれも1+2+4+8+... みたいな形 (=2^n - 1)。
これならO(n)だ。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define found(s,e)  ((s).find(e)!=(s).end())


const ll M=1000000007LL;

ll ADD(ll x, ll y) { return (x+y) % M; }
ll SUB(ll x, ll y) { return (x-y+M) % M; }
ll MUL(ll x, ll y) { return x*y % M; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { return MUL(x, POW(y, M-2)); }

// #include "cout11.h"
int main(){
    int n;
    vector<int> a;

    char buf[3300000];

    gets(buf);
    n = atoi(buf);
    a.resize(n);

    gets(buf);
    int i=0;
    for (char *p=&buf[0]; ;) {
        char *q = p;
        while (*q >= 48) ++q;
        *q = 0;
        a[i++] = atoi(p);
        if (i == n) break;
        p = q+1;
    }

    sort(all(a));

    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }
/*
    if (n == 2) {
        cout << a[1] - a[0] << endl;
        return 0;
    }
*/
    // O(n)
    vector<ll> pw(n+1);
    pw[0] = 1LL;
    rep(i, n) pw[i+1] = (pw[i] * 2LL) % M;

    // O(n)
    ll pos = 0, neg = 0;
    for (ll i=n-1,m=0; i>=0; --i) {
        neg = (neg + a[i] * m) % M;
        m = (m*2LL + 1LL) % M;
    }
    for (ll i=0,m=0; i<n; ++i) {
        pos = (pos + a[i] * m) % M;
        m = (m*2LL + 1LL) % M;
    }

    ll ans = SUB(pos, neg);
    cout << ans << endl;
    return 0;
}

→3投目pretest passed (→AC); 776 (1:44)

D. Glad to see you! (x51)

開いてない

E. Find a car (x5)

開いてない

system test

終わってから少し寝てて
起きたら結果が出てた。
724位で、レーティング微減。1615→1601 (-14)

今回学んだこと

  • こどふぉはラウンド開始後にも参加登録できるタイミングがある
  • ハック(=撃墜)するには自分の解をロックする必要がある。(ロックすると再提出できない)
  • ハックされた問題でも再提出できる(自分がロックしていなければ?)
  • ロックしていなければ再提出は何度でもできるが、再提出ペナルティは1回につき50ポイント。
  • 問題を開こうが開くまいが1分につき 1/250 ずつ配点が目減りしていくので、Aからではなく(自分が解けそうな)配点の大きな問題から解いたほうがいい。