読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

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

Codeforces Round #412 (rated, Div. 2, base on VK Cup 2017 Round 3)

Codeforcesに参加したの7年ぶりらしい
前回が2010年3月の "Codeforces Beta Round #4 (Div. 2 Only)"
5/8 0:45am JST〜(3時間)。
(途中英会話レッスンとかしながらの片手間だったけれど)3問(A,B,C)通して、
1515→1615 (Expert)
f:id:n4_t:20170508180554p:plain

A. Is it rated?

問題文が何言ってるのかわからなくて戸惑う
多分、ratedなコンテストなら、格下の参加者が格上より上位に来たらratingに何らかの変動があるはずだという点をチェックするだけなんだよね。

(略)
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 found(s,e)  ((s).find(e)!=(s).end())

int main(){
    int n; cin >> n; // 2-1000
    vector<int> a(n), b(n);
    bool rated = false;
    rep(i, n) {
        int ai, bi; cin >> ai >> bi; // -4126
        a[i] = ai; b[i] = bi;
        int d = bi - ai;
        if (d != 0) { rated = true; break; }
    }

    if (rated) {
        cout << "rated" << endl;
    } else {
        bool up = false;
        rep(i, n-1) {
            if (b[i] < b[i+1]) { up = true; break; }
        }
        if (up)
            cout << "unrated" << endl;
        else
            cout << "maybe" << endl;
    }

    return 0;
}

B. T-Shirt Hunt

謎の計算式が生み出す数字をもとにスコアを調整する
どこまで計算したらいいか分からんので適当

(略)
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 found(s,e)  ((s).find(e)!=(s).end())

int main(){
    int p, x, y; cin >> p >> x >> y;
    // p:26-500 , 1<=y<=x<=2e4

    set<int> R;

    int minhk = 99999999;

    for (int s=y; ; ++s) {
        int o = s - x;
        if (o % 50) continue;

        R.clear();
        int i = (s / 50) % 475;
        rep(j, 25) {
            i = (i*96 + 42) % 475;
            R.insert(26+i);
        }

        if (found(R, p)) {
            int hk = 0;
            if (o > 0) {
                if (o % 100) o += 50;
                hk = o / 100;
            }
            minhk = min(minhk, hk);
        }
        if (s > 1000001) break;
    }

    cout << minhk << endl;
}

C. Success Rate

  • (x+a)/(y+b) = p/q
  • a,bは非負整数。0≦a≦b
  • pとqは互いに素

を満たす最小の(aと)bが存在するか。
x/(y+b) ≦ p/q ≦ (x+b)/(y+b)
b→∞のとき 左辺→0, 右辺→1 だし、(y+b)がqの倍数になるように選べば何でも(0と1以外なら)表現できるだろう。
0 (p/q=0/1)と1 (p/q=1/1) のケースは?x>0なら0は無理。x<yなら1は無理。
あとは、qa-pb=(py-xq) を満たす最小の非負整数bを求めるだけ。 
で。探索範囲が広すぎると思ったらにぶたんを疑え、とagwたんと最近話してたところだったのだけれど数学的に条件を突き詰めて解いた。
(ここまで通した)

(略)
typedef long long ll;
#define all(c)  (c).begin(),(c).end()
#define rep(var,n)  for(int var=0;var<(n);var++)

int main(){
    int _T; cin>>_T; // 1-100
    rep(_t,_T){
        ll x,y,p,q; cin >> x >> y >> p >> q;
        // 0-1e9;
        //assert(p < q);
        ll ans = -1;
        if (p == q) { // 1/1
            ans = (x == y) ? 0 : -1;
            cout << ans << endl;
            continue;
        }
        else if (p == 0) {
            ans = (x == 0) ? 0 : -1;
            cout << ans << endl;
            continue;
        }

        ll amin = max(0LL, (ll)ceil(1.0*p*y/q - x));
        ll m = (x+amin)/p;
        if ((x+amin) % p != 0) ++m;
        ll mmin = (y - x) / (q - p);
        m = max(m, mmin-1); // -1した意味は漠然とした不安
        for (; ; ++m) {
            ll b = q*m - y;
            ll a = p*m - x;
            if (a <= b) {
                cout << b << endl;
                break;
            }
        }
    }
}

D. Dynamic Problem Scoring

(これは時間足りなかった)
この問題、そう難しい設定ではないと思うのだけれど、自分で解けるまで問題文のTest Caseの説明が何を言いたかったのか分からなかった。
(参加人数、正解者数)から問題の配点(500〜3000)のある点数に恣意的に設定するために必要なチートアカウント数を求めるのは問題Cに似ているけれどこちらはもっと簡単。2≦n≦120だから、高々その32倍までを調べれば十分と見た。
で、問題の配点が6通り、これが5問あるから6^5=7776通りで、二人の得点がどうなるか計算して、勝てるパターンにするためには(それが可能なら)チートが何アカウント必要か見て、その最小値。
ただそれだけのことのはずなんだけど手間取った。
問題ごとにチートアカウント必要数を求めてその最大値、みたいに最初書いてたので答えが合わない。あるチートアカウント数で、その配点にすることが可能か、という計算でないといけなかった。

(略)
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 rep1(var,n)  for(int var=1;var<=(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

#define MAXDEPTH 3841  // 120x32=3840
#define INFTY 99999999

ll C(ll x, ll y, ll q) {
    ll p = 1LL;

    if (1 == q) { // 1/1
        return (x == y) ? 0 : -1;
    }
    ll amin = max(0LL, (ll)ceil(1.0*y/q - x));
    ll m = x + amin;
    ll mmin = (y - x) / (q - 1);
    m = max(m, mmin-1);
    for (; ; ++m) {
        ll b = q*m - y;
        ll a =   m - x;
        if (a <= b) return b;
    }
}

int sc(double r) {
    if (r > 0.5) return 1;
    if (r > 0.25) return 2;
    if (r > 0.125) return 3;
    if (r > 0.0625) return 4;
    if (r > 0.03125) return 5;
    return 6;
}

int main(){
    int n; cin >> n; // 2..120
    vector<vector<int> > a(n, vector<int>(5));
    vector<int> ns(5, 0);
    rep(i, n) {
        rep(j, 5) {
            int aij; cin >> aij;
            a[i][j] = aij;
            if (aij != -1) ns[j]++;
        }
    }

    vector<vector<set<int> > > q(5, vector<set<int> >(MAXDEPTH));
    rep(j, 5) {
        int x = ns[j], y = n;
        double r = (double)x / y;
        int _sc = sc(r);
        q[j][0].insert(_sc);
        for (int v=1; v<MAXDEPTH; ++v) {
            int maxu = (a[0][j] != -1) ? v : 0;
            for (int u=0; u<=maxu; ++u) {
                double r = (double)(x+u) / (y+v);
                int _sc = sc(r);
                q[j][v].insert(_sc);
            }
        }
    }

    int tmin = INFTY;
    vector<int> i(5);
    for (i[0]=1; i[0]<=6; ++i[0])
    for (i[1]=1; i[1]<=6; ++i[1])
    for (i[2]=1; i[2]<=6; ++i[2])
    for (i[3]=1; i[3]<=6; ++i[3])
    for (i[4]=1; i[4]<=6; ++i[4]) {
        int v=0, p=0;
        rep(j, 5) {
            if (a[0][j] != -1)
                v += 2 * i[j] * (250 - a[0][j]);
            if (a[1][j] != -1)
                p += 2 * i[j] * (250 - a[1][j]);
        }
        if (v <= p) continue;

        int t = -1;
        for (int k=0; k<MAXDEPTH; ++k) {
            int f = 0;
            rep(j, 5) {
                if (found(q[j][k], i[j])) ++f;
            }
            if (f == 5) {
                t = k; break;
            }
        }
        if (t == -1) continue;
        tmin = min(tmin, t);
    }

    if (tmin == INFTY)
        cout << -1 << endl;
    else
        cout << tmin << endl;

    return 0;
}

E. Prairie Partition

(開いてない)

F. Perishable Roads

(開いてない)