Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI 模擬予選 2014-2015 解説++

JOI

こんばんは, kagamiz です.
この記事は JOI 模擬予選 2014-2015 の 解説pdf の補足(というかひとことコメント)を目的として書かれた記事です.

それぞれの問題の kagamiz 解 / yosupot 解を載せます.

あと, なるべく早くに KOJ に今日の模擬予選の問題はアップロードします.

1. チョコボール (Choco Balls)

[補足] サンプルが少し弱くて点数を落としてる人が何人か見受けられましたが, 問題文はしっかり読みましょう. また, 例年問 1 は手計算できるような問題が出るのでケースを手で解いてみるのもしっかり得点を稼ぐコツです.

[kagamiz 解]

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int a, b, c, d;
    
    scanf("%d %d %d %d", &a, &b, &c, &d);
    
    printf("%d\n", (max(0, c * d - a * b) + b - 1) / b);
    
    return (0);
}

[yosupot 解]

//ヘッダ略

using namespace std;
typedef long long ll;

int main() {
	double a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << max(0.0, ceil((c*d - a*b) / b)) << endl;
	return 0;
}

2. 温泉 (Spa)

[補足] ありません. 問題文に書かれている処理をきちんと行いましょう.

[kagamiz 解]

#include <bits/stdc++.h>

using namespace std;

int A[128];

int main()
{
    int N, C;
    
    scanf("%d %d", &N, &C);
    
    for (int i = 0; i < N; i++){
        int l, r;
        scanf("%d %d", &l, &r);
        
        bool ok = false;
        for (int j = l; j <= r; j++){
            if (A[j] < C){
                printf("%d\n", j);
                ok = true;
                A[j]++;
                break;
            }
        }
        
        if (!ok) printf("-1\n");
    }
    
    return (0);
}

[yosupot 解]

//ヘッダ略

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;

int u[110];
int main() {
    int n, c;
    cin >> n >> c;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r; r++;
        int res = -1;
        for (int j = l; j < r; j++) {
            if (u[j] < c) {
                u[j]++;
                res = j;
                break;
            }
        }
        cout << res << endl;
    }
    return 0;
}

3. 花占い (Flower Fortune-Telling)

[補足] 完答者が 24 人で, 問 4 より少なくなりました. こういう問題は貪欲法を使いたくなりますが, なんでその貪欲法でいいのかというのを簡単に自分の中で説明できるようにすると良いと思います.
DP が先に出て来たならそれを実装するのも良いと思います.
また, この問題は 3 年前の予選で出た「最高のピザ」を意識した問題になっているので, 貪欲ステップを比べてみましょう.

[kagamiz 解]

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, mul[2];
    vector<int> even, odd;
    
    scanf("%d %d %d", &n, mul + 1, mul);
    
    for (int i = 0; i < n; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        if (a & 1) odd.push_back(b);
        else even.push_back(b);
    }
    
    sort(even.begin(), even.end());
    sort(odd.begin(), odd.end());
    
    int ans = 0;
    int eSum = 0;
    for (int i = 0; i <= even.size(); i++){
        if (i) eSum += even[i - 1];
        int oSum = 0;
        for (int j = 0; j <= odd.size(); j++){
            if (j) oSum += odd[j - 1];
            ans = max(ans, mul[j & 1] * (i + j) - eSum - oSum);
        }
    }
    
    printf("%d\n", ans);
    
    return (0);
}

[yosupot 解]

//ヘッダ略

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MN = 110;
ll n;
ll x[MN], y[MN];
ll dp[MN][MN][2];
ll solve(int a, int b, int c) {
    if (!b) {
        if (c) return 1LL<<55;
        return 0;
    }
    if (a == n) {
        return 1LL<<55;
    }
    if (dp[a][b][c] != -1) return dp[a][b][c];
    return dp[a][b][c] = min(solve(a+1, b, c), 
        y[a]+solve(a+1, b-1, c^x[a]) );
}

int main() {
    memset(dp, -1, sizeof(dp));
    ll c, d;
    cin >> n >> c >> d;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        x[i] %= 2;
    }
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, i*d-solve(0, i, 0));
        res = max(res, i*c-solve(0, i, 1));
    }
    cout << res << endl;

}

4. あくじのためにあみだしたくじ (A kuji planned for Akuji)

↑タイトルの英訳がんばった(こなみ)
[補足] 制約をミスりました... $n, m \leqq 10^3$ にするか $n, m \leqq 10^6$ にしても良かったですね.
ここ 4 年間予選問 4 では DP が出続けています. 今年がどうなるかは分かりませんが修行しておくとあとあと役に立つことがあるかもしれません. DP, しよう.

ちなみにこの問題は 3 年前にすぬけさんがやった模擬予選で出題されたものです. すぬけさん, 問題ありがとうございました.

[kagamiz 解]

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int dp[10001];
    memset(dp, -1, sizeof(dp));
    
    int N, M, p;
    
    scanf("%d %d %d", &N, &M, &p);
    
    dp[p] = 0;
    
    for (int i = 0; i < M; i++){
        int X;
        scanf("%d", &X);
        int u = dp[X], v = dp[X + 1];
        if (~u) dp[X + 1] = max(dp[X + 1], u + 1);
        if (~v) dp[X]     = max(dp[X],     v + 1);
    }
    
    printf("%d\n", dp[1]);
    
    return (0);
}

[yosupot 解]

//ヘッダ略

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int dp[10100];

int main() {
    int n, m, p;
    cin >> n >> m >> p; p--;
    fill_n(dp, 10100, -(1<<28));
    dp[p] = 0;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x; x--;
        int a = dp[x], b = dp[x+1];
        dp[x] = max(a, b+1);
        dp[x+1] = max(a+1, b);
    }
    cout << dp[0] << endl;
    return 0;
}

5. 楽しい花の水やり (Watering Flower is Fun)

[補足] 約数の個数の見積ができるかどうかに全て掛かっている気がします. DP の更新式はとてもシンプルなので積極的に部分点を稼ぎに行きましょう. よすぽくん, 問題案ありがとう.

[kagamiz 解]

#include <bits/stdc++.h>

#define MOD (100000)

using namespace std;

int dp[5000];

int main()
{
    long long N;
    
    scanf("%lld", &N);
    
    vector<long long> divi;
    for (long long i = 1; i * i <= N; i++){
        if (N % i == 0){
            divi.push_back(i);
            if (i * i != N) divi.push_back(N / i);
        }
    }
    
    sort(divi.begin(), divi.end());
    
    dp[0] = 1;
    for (int i = 1; i < divi.size(); i++){
        for (int j = 0; j < i; j++){
            if (divi[i] % divi[j] == 0){
                dp[i] = (dp[i] + dp[j]) % MOD;
            }
        }
    }
    
    printf("%d\n", dp[divi.size() - 1]);
    
    return (0);
}

[yosupot 解]

//ヘッダ略

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const ll MD = 100000;
vector<ll> v;
vector<ll> r;
int main() {
    ll n;
    cin >> n;
    for (ll i = 1; i*i <= n; i++) {
        if (n % i == 0) {
            v.push_back(i);
            if (i != n/i) {
                v.push_back(n/i);
            }
        }
    }
    sort(v.begin(), v.end());
    int m = v.size();
    r.resize(m);
    r[0] = 1;
    for (int i = 1; i < m; i++) {
        r[i] = 0;
        for (int j = 0; j < i; j++) {
            if (v[i] % v[j] == 0) {
                r[i] += r[j];
                r[i] %= MD;
            }
        }
    }
    cout << r[m-1] << endl;
    return 0;
}

6. わいわい (Y-y)

[補足] 条件を満たす点は本当に Y 字っぽくなりますよ.
制約に関してですが, 完全にミスりました. せっかく乱数生成式を与えているので $n \leqq 5 \times 10^6$ くらいにするとちょうどいい感じになっていたと思います.
データ構造を用いる問題は予選では出題されませんが, 知っていると解ける問題の幅が広がると思うのでこの位置で出題しました. 模擬だしね. tokoharu さん, 問題案ありがとうございました.

[kagamiz 解]

#include <bits/stdc++.h>

#define MAX_N   (100000)
#define MAX_P   (600000)
#define MOD (1000000007)
#define pos(x, y) (lower_bound(x.begin(), x.end(), y) - x.begin())

using namespace std;

int M, N, A, B;
int X[100001], Y[100001];

unsigned int r(){ 
	static unsigned int  x = 123456789,
	                     y = 362436069,
	                     z = 521288629,
	                     w = A;
	unsigned int t = (x ^ (x << 11)); 
	x = y; y = z; z = w;
	
	return (w = (w ^ (w >> 19) ^ (t ^ (t >> 8)))); 
}

void generate(int X[], int Y[])
{
    for (int i = M; i < N; i++){
        X[i] = r() % (2 * B + 1); X[i] -= B;
        Y[i] = r() % (2 * B + 1); Y[i] -= B;
    }
}

int bit[MAX_P + 10];
long long c1[MAX_N], c2[MAX_N], c3[MAX_N];

void add(int p, int x)
{
    for (p++; p <= MAX_P; p += p & -p) bit[p] += x;
}

int sum(int p)
{
    int ret = 0;
    for (p++; p > 0; p &= (p - 1)) ret += bit[p];
    
    return (ret);
}

vector<int> xs;
void calc(long long *out, pair<pair<int, int>, int> *pt)
{
    memset(bit, 0, sizeof(bit));
    
    for (int i = 0; i < N;){
        int j = i;
        while (j < N && pt[i].first.first == pt[j].first.first){
            out[pt[j].second] += sum(pos(xs, pt[j].first.second) - 1);
            j++;
        }
        for (int it = i; it < j; it++){
            add(pos(xs, pt[it].first.second), 1);
        }
        i = j;
    }
}

int main()
{
    scanf("%d %d %d %d", &N, &M, &A, &B);
    
    for (int i = 0; i < M; i++){
        scanf("%d %d", X + i, Y + i);
    }
    
    generate(X, Y);
    
    for (int i = 0; i < N; i++){
        xs.push_back(X[i]); xs.push_back(-X[i]);
        xs.push_back(Y[i]); xs.push_back(-Y[i]);
        xs.push_back(X[i] - Y[i]);
        xs.push_back(Y[i] - X[i]);
    }
    
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    
    pair<pair<int, int>, int> pt[MAX_N];
    
    for (int i = 0; i < N; i++){
        pt[i] = make_pair(make_pair(X[i], Y[i]), i);
    }
    sort(pt, pt + N);
    calc(c1, pt);
    
    for (int i = 0; i < N; i++){
        pt[i] = make_pair(make_pair(-(X[i] - Y[i]), -Y[i]), i);
    }
    sort(pt, pt + N);
    calc(c2, pt);
    
    for (int i = 0; i < N; i++){
        pt[i] = make_pair(make_pair(-X[i], -(Y[i] - X[i])), i);
    }
    sort(pt, pt + N);
    calc(c3, pt);
    
    long long ans = 0;
    for (int i = 0; i < N; i++){
        ans = (ans + ((c1[i] * c2[i]) % MOD * c3[i]) % MOD) % MOD;
    }
    
    printf("%lld\n", ans);
    
    return (0);
}

[yosupot 解] (!!参考にしないこと!!)

#include <iostream>
#include <cstdio>
#include <vector>
#include <valarray>
#include <cassert>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<P, int> D;
const int MN = 100100;
const ll MD = 1e9+7;

struct Tree {
    struct Node;
    using NP = Node*;
    static Node last_d;
    static NP last;
    struct Node {
        NP l, r;
        int sz;
        ll value;
        Node(ll v) :l(last), r(last), sz(1), value(v) {}
        Node(NP l, NP r, int sz = 0) :l(l), r(r), sz(sz) {}
        void push() {

        }
        NP update() {
            sz = 1+l->sz+r->sz;
            return this;
        }
        int lb(ll a) {
            if (!sz) return 0;
            if (a <= value) return l->lb(a);
            return l->sz + 1 + r->lb(a);
        }
    } *n;

    static uint xor128(){
        static uint x=123456789,y=362436069,z=521288629,w=88675123;
        uint t;
        t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
    }
    static NP merge(NP l, NP r) {
        if (!l->sz) return r;
        if (!r->sz) return l; 
        l->push(); r->push();
        if (xor128() % (l->sz + r->sz) < l->sz) {
            l->r = merge(l->r, r);
            return l->update();
        } else {
            r->l = merge(l, r->l);
            return r->update();
        }
    }
    static pair<NP, NP> split(NP x, int k) {
        if (!x->sz) return {last, last};
        x->push();
        if (k <= x->l->sz) {
            auto y = split(x->l, k);
            x->l = y.second;
            y.second = x->update();
            return y;
        } else {
            auto y = split(x->r, k- x->l->sz -1);
            x->r = y.first;
            y.first = x->update();
            return y;
        }
    }

    Tree() : n(last) {}
    Tree(NP n) : n(n) {}
    int sz() {
        return n->sz;
    }
    void merge(Tree r) {
        n = merge(n, r.n);
    }
    Tree split(int k) {
        auto u = split(n, k);
        n = u.first;
        return Tree(u.second);
    }
    void insert(ll v) {
        auto u = split(n, n->lb(v));
        n = merge(merge(u.first, new Node(v)), u.second);
    }
    int lb(ll l) {
        return n->lb(l);
    }
};
Tree::Node Tree::last_d = Tree::Node(NULL, NULL, 0);
Tree::NP Tree::last = &last_d;

int n;

D d[MN];
ll res[MN];
void calc() { // x_j < x_i && y_j < y_i なるjの個数をiそれぞれについて計算
	Tree t;
	sort(d, d+n, [](const D &x, const D &y) -> bool {
		if (x.first.first != y.first.first) return x.first.first < y.first.first;
		if (x.first.second != y.first.second) return x.first.second > y.first.second;
		return x.second < y.second;
	});

	//return;
	for (int i = 0; i < n; i++) {
		D u = d[i];
		res[u.second] = t.lb(u.first.second);
		t.insert(u.first.second);
	}
}

P a[MN];
ll ans[MN];
ll solve() {
	fill_n(ans, n, 1);
	for (int i = 0; i < n; i++) {
		d[i].first = P(a[i].first, a[i].second);
		d[i].second = i;
	}
	calc();
	for (int i = 0; i < n; i++) {
		ans[i] *= res[i];
		ans[i] %= MD;
	}
	for (int i = 0; i < n; i++) {
		d[i].first = P(a[i].second-a[i].first, -a[i].second);
		d[i].second = i;
	}
	calc();
	for (int i = 0; i < n; i++) {
		ans[i] *= res[i];
		ans[i] %= MD;
	}
	for (int i = 0; i < n; i++) {
		d[i].first = P(-a[i].first, a[i].first-a[i].second);
		d[i].second = i;
	}
	calc();
	for (int i = 0; i < n; i++) {
		ans[i] *= res[i];
		ans[i] %= MD;
	}

	ll u = 0;
	for (int i = 0; i < n; i++) {
		u += ans[i];
		u %= MD;
	}
	return u;
}

ll x[MN], y[MN];
ll solve2() {
	for (int i = 0; i < n; i++) {
		x[i] = a[i].first;
		y[i] = a[i].second;
	}
	ll res = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				for (int l = 0; l < n; l++) {
					if (i == j) continue;
					if (i == k) continue;
					if (i == l) continue;
					if (j == k) continue;
					if (j == l) continue;
					if (k == l) continue;
					if (x[i] >= x[j] || y[i] >= y[j]) continue;

					if (x[j] >= x[k]) continue;
					if (y[j] >= y[k]) continue;
					if (y[k] >= y[j] + x[k] - x[j]) continue;

					if (x[j] >= x[l]) continue;
					if (x[l] >= x[j] + (y[l] - y[j])) continue;
					if (y[j] >= y[l]) continue;
					res++;
				}
			}
		}
	}
	return res;
}


int N, M, A, B;
ll X[MN], Y[MN];
unsigned int r(){ 
	static unsigned int  x = 123456789,
	                     y = 362436069,
	                     z = 521288629,
	                     w = A;
	unsigned int t = (x ^ (x << 11)); 
	x = y; y = z; z = w;
	
	return (w = (w ^ (w >> 19) ^ (t ^ (t >> 8)))); 
}

void generate(ll X[], ll Y[])
{
    for (int i = M; i < N; i++){
        X[i] = r() % (2 * B + 1); X[i] -= B;
        Y[i] = r() % (2 * B + 1); Y[i] -= B;
    }
}

int main() {
	cin >> N >> M >> A >> B;
	for (int i = 0; i < M; i++) {
		cin >> X[i] >> Y[i];
	}
	generate(X, Y);
	n = N;
	for (int i = 0; i < N; i++) {
		a[i] = P(X[i], Y[i]);
	}
	cout << solve() << endl;
	return 0;
}