2017-09-12

Codeforces Round #433 Div.2 D / Div.1 B - Jury Meeting

http://codeforces.com/contest/854/problem/D

問題概要

(N+1)個の町があり、1～Nの町に一人ずつ人が住んでいる。また町0 → 町(1～Nのどれか) に飛ぶ飛行機と、町(1～Nのどれか) → 町0 に飛ぶ飛行機の2種類がある。飛行機を使って1～Nの町の人を全員町0に呼び、さらに全員が集まっている状態でK日間以上過ごさせ、その後全員を元の町に送り返したい。M個の飛行機の運行情報（出発日、出発元の町、行き先の町、チケット代）が与えられるので、条件を満たすような全員分チケットの買い方のうちもっとも安く済むときの合計代金を求めよ。

1 <= N <= 10⁵

0 <= M <= 10⁵

解法

尺取り法っぽくやる。全員分の行きチケットを確保したとき、使える帰りチケットは行きチケットの中で一番遅い日付＋K日目以降のものだけになる。逆にいえば、以降であればどれでも使えることになるので、帰りのチケットの価格はそれより後ろのチケットの価格の最小値とみなしてしまってよい。あとは行きのチケット・帰りのチケットをそれぞれ日付順に並べてキューに突っ込み、行きキューから日付を一個取り出すごとに帰りのキューから行きの日付＋Kより小さいものを弾いていく。こうすると行きチケットは既にキューから取り出したものがすべて使え、帰りチケットはまだ取り出してないものがすべて使えることになる。この過程でそれぞれの番号のチケットの値を管理していけば逐次最小値を更新していくことができる。

感想

解法自体はそんなに複雑ではないが細かいところをいろいろ気を付けなければならずかなりしんどい問題だと思った。こういうのにも慣れていかないとな～～～～～～

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

immutable long INF = 1L << 59;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto K = s[2];

    auto go = new Tuple!(int, long)[][](N);
    auto back = new Tuple!(int, long)[][](N);

    foreach (_; 0..M) {
        s = readln.split.map!(to!int);
        if (s[2] == 0)
            go[s[1]-1] ~= tuple(s[0], s[3].to!long);
        else
            back[s[2]-1] ~= tuple(s[0], s[3].to!long);
    }

    foreach (i; 0..N)
        go[i].sort!"a[0] < b[0]"();
    foreach (i; 0..N)
        back[i].sort!"a[0] < b[0]"();

    if (go.map!(g => g.length == 0).any ||
        back.map!(b => b.length == 0).any) {
        writeln(-1);
        return;
    }

    foreach (i; 0..N)
        foreach (j; 1..go[i].length) 
            go[i][j][1] = min(go[i][j][1], go[i][j-1][1]);
    
    foreach (i; 0..N) 
        for (int j = back[i].length.to!int - 1; j >= 1; --j)
            back[i][j-1][1] = min(back[i][j-1][1], back[i][j][1]);


    auto q1 = new BinaryHeap!(Array!(Tuple!(int, int, long)), "a[0] > b[0]");
    auto q2 = new BinaryHeap!(Array!(Tuple!(int, int, long)), "a[0] > b[0]");
    
    foreach (i; 0..N)
        foreach (j; 0..go[i].length)
            q1.insert(tuple(go[i][j][0], i, go[i][j][1]));
    foreach (i; 0..N)
        foreach (j; 0..back[i].length)
            q2.insert(tuple(back[i][j][0], i, (j + 1 == back[i].length ? INF : back[i][j+1][1])));

    int used_cnt = 0;
    auto used = new bool[](N);
    auto ans1 = new long[](N);
    auto ans2 = new long[](N);
    foreach (i; 0..N)
        ans2[i] = back[i][0][1];
    long sum1 = 0;
    long sum2 = ans2.sum;
    long ans = INF;
    bool end = false;
    
    
    while (!q1.empty && !end) {
        auto t = q1.front;
        auto d = t[0];
        auto n = t[1];
        auto c = t[2];
        q1.removeFront;
        sum1 -= ans1[n];
        ans1[n] = c;
        sum1 += ans1[n];
        if (!used[n]) {
            used_cnt += 1;
            used[n] = true;
        }

        if (used_cnt < N)
            continue;


        while (!q2.empty && q2.front()[0] <= d + K) {
            t = q2.front;
            n = t[1];
            c = t[2];
            q2.removeFront;
            
            if (c == INF) {
                end = true;
                break;
            }
                
            sum2 -= ans2[n];
            ans2[n] = c;
            sum2 += ans2[n];
        }

        if (!end)
            ans = min(ans, sum1 + sum2);
    }

    if (ans >= INF)
        ans = -1;
    ans.writeln;
}

2017-09-12

CS Academy #46 (Div. 1.5) E - Ultimate Orbs

問題記録 CS Academy CSA #46

https://csacademy.com/contest/round-46/task/ultimateorbs/

問題概要

N個のオーブが座標1～Nに順番に並んでいる。各オーブには強さGiが設定されており、左隣あるいは右隣のオーブに対して自分の強さ＋D >= 相手の強さであればそのオーブを吸収できる。吸収した側のオーブは強さの値が相手の強さ分増え、された側は消滅する。(N-1)回の吸収が起こったとき最終的に残る可能性のあるオーブをすべて挙げよ。

1 <= N <= 10⁶

0 <= D <= 10⁹

0 <= Gi <= 10⁹

解法

まず数列の中で最大の強さをもつオーブは明らかに他のオーブを全部吸収できる。ここでその最大のオーブを境界にして数列を左右に分割してみる（ただし境界はどちらにも含めない）と、分割後数列の最大値は明らかに区間内の他の値を全部吸収できる。そして吸収した結果、境界を吸収できるほどの強さになっていればその要素は境界を越えて数列全体を吸収できることになる。もし境界を越えられないのであれば、そのオーブはもちろん区間内の他のオーブも全部ボツになる（最大値が無理なら他のも自明に無理なので）。逆にもし越えられるのであれば、その要素を新たに境界として区間を分割する。この操作を繰り返していくと各区間には「左の境界」と「右の境界」ができていくことになるが、このうちどちらかでも越えられるなら全部の要素を吸収できるとしてよい。なぜなら境界となりえる数値は既に他の値を全部吸収できることが保証されており、そのような値を吸収できる値もまた他の値を全部吸収できるからである。

上で説明したような手続きを実際にプログラムに落とすと以下のような感じになる。

キューから区間を取り出す（区間には左の境界の値、右の境界の値も記録しておく）
区間の総和をとり、左右どちらかの境界を越えられているかチェックする
もし越えられていなければその区間内のインデックスをすべて×にして1に戻る
区間の最大値とそのインデックスを得、そのインデックスを境界として区間を分割しキューに追加する
キューに区間が残っていれば1に戻る
×がついていないオーブを答えとして出力する

区間の総和は累積和を計算しておけばO(1)でできる。区間の最大値はいろいろあるけどセグ木でO(logN)でできる。セグ木はpairとかでインデックスも持つようにすると最大値だけじゃなくてそのインデックスも取ってくるようにできる。この場合和をセグ木にしてもオーダーは変わらないが、この問題はN<=10⁶でO(NlogN)がかなりギリギリなのでその辺頑張らないと通らなかった。（最初は和も最大値もセグ木で最大値の方は値取得→unordered_mapに溜めといた強さごとのインデックス表を二分探索とか悠長なことしてたがTLE祭りだった）

感想

なんか途中ヴェルタースオリジナルみたいになった

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;



class SegmentTreeMax {
public:
    vector<pair<ll, int>> table;
    int size;

    SegmentTreeMax(int n) {
        size = 1;
        while (size <= n) size *= 2;
        size *= 2;
        table = vector<pair<ll, int>>(size, make_pair(-1, -1));
    }

    void assign(int pos, ll num) {
        return assign(pos, num, 0, 0, size/2-1);
    }

    void assign(int pos, ll num, int i, int left, int right) {
        if (left == right) {
            table[i] = make_pair(num, pos);
            return;
        }
        auto mid = (left + right) / 2;
        if (pos <= mid)
            assign(pos, num, i*2+1, left, mid);
        else
            assign(pos, num, i*2+2, mid+1, right);

        if (table[i*2+1].first >= table[i*2+2].first) 
            table[i] = table[i*2+1];
        else
            table[i] = table[i*2+2];
    }

    int query(int pl, int pr) {
        return query(pl, pr, 0, 0, size/2-1).second;
    }

    pair<ll, int> query(int pl, int pr, int i, int left, int right) {
        if (pl > right || pr < left)
            return make_pair(-1, -1);
        else if (pl <= left && right <= pr)
            return table[i];

        pair<ll, int> q1 = query(pl, pr, i*2+1, left, (left+right)/2);
        pair<ll, int> q2 = query(pl, pr, i*2+2, (left+right)/2+1, right);
        return q1.first >= q2.first ? q1 : q2;
    }
};




ll A[1000010];
ll B[1000010];
bool ok[1000010];

ll sumq(int l, int r) {
    return B[r+1] - B[l];
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    memset(B, 0, sizeof(B));
    memset(ok, 0, sizeof(ok));

    int N;
    ll D;
    cin >> N >> D;
    REP(i, N) cin >> A[i];
    REP(i, N) B[i+1] = B[i] + A[i];

    SegmentTreeMax stmax = SegmentTreeMax(N);
    REP(i, N) stmax.assign(i, A[i]);

    deque<tuple<ll, int, int, ll, ll>> q;
    q.push_back(make_tuple(stmax.query(0, N-1), 0, N-1, -1, -1));

    while (!q.empty()) {
        auto t = q.front();
        int m = get<0>(t);
        int l = get<1>(t);
        int r = get<2>(t);
        ll lv = get<3>(t);
        ll rv = get<4>(t);
        q.pop_front();

        ll s = sumq(l, r);
        if (s + D < lv && s + D < rv) {
            REP2(i, l, r+1) ok[i] = false;
            continue;
        }

        ok[m] = true;

        ll nlv = lv == -1 ? (1LL << 59) : lv;
        ll nrv = rv == -1 ? (1LL << 59) : rv;

        if (m > l)
            q.push_back(make_tuple(stmax.query(l, m - 1), l, m - 1, nlv, A[m]));
        if (m < r)
            q.push_back(make_tuple(stmax.query(m + 1, r), m + 1, r, A[m], nrv));
    }


    REP(i, N) if (ok[i]) cout << i + 1 << " ";
    cout << endl;

    return 0;
}

2017-09-11

Codeforces Round #432 Div.2 E / Div.1 C - Arpa and a game with Mojtaba

問題記録 Codeforces CF #432 Grundy数

http://codeforces.com/contest/850/problem/C

問題概要

先手と後手に分かれて以下のような2人ゲームを行う。まずN要素の数列Aが与えられる。プレイヤーは手番ごとに素数pと正整数kを選び、数列のうちp^kで割り切れる要素をp^kで割る。ただしどの要素も割り切れないようなp, kを選ぶことはできない。これを繰り返し、先に自分の手番においてp, kを選べなくなった方が負けとなる。先手と後手が最適な行動を繰り返したときどちらが勝つか求めよ。

N <= 100

max(A) <= 10⁹

解法

Grundy数の問題。原理は置いといてGrundy数を扱う上で必要な操作は以下の2点である。

1つの山では遷移先のmexをとる
複数の山では各山のmexをxorする

この問題ではある素数pを選んだときの操作が他の素数には影響を与えないので、各素数を独立に考えることができる（上で言う「1つの山」に相当）。つまり各素数の範囲内でGrundy数を求め、最後にそれらのxorをとれば答えが出る。

というわけで問題は特定の素数に対する操作をどう表すか、という点に移る。例えば2¹と2³を因数に持つ要素があり、他の要素に2^xの因数は含まれていなかったとすると、選べる2^kはk=1, 2, 3の3通りである。1を選ぶと2¹が2⁰に、2³が2²になる。2を選ぶと2¹は割り切れないので変わらず、2³は2¹になる。これを一般化すると、素数pに対して数列中の因数にp^a, p^b, p^c,…が存在している場合、取れる操作はp¹～p^（最大の指数）のうちひとつを選んで割ることである。選んだ数未満の指数は割り切れないので変化せず、選んだ数以上の指数は選んだ数のぶん引き算される。これが遷移になる。ここで2³⁰ > 10⁹より最大の指数は高々30程度であり、さらに一回の操作で最大の指数は必ず小さくなっていくので、状態数も大して増えない。というわけである素数pについてp^xの因数がある・ないをboolのテーブルで表し再帰的に遷移を追っていけばpのGrundy数を求めることができる。boolのテーブルにはbitsetみたいなのを使えば実装しやすい（別にintでもできる（今気づいた））。

感想

ちょうどいい感じのGrundy練習問題だった

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;

const int MAX = 32;
int N;
int A[101010];
unordered_map<int, bitset<MAX>> B;
unordered_map<bitset<MAX>, int> mem;


int grundy(bitset<MAX> b) {
    if (mem.find(b) != mem.end())
        return mem[b];
    else if (b.count() == 0)
        return 0;

    int m = 0;
    REP(i, MAX) if (b[i]) m = i;
    vector<int> mex;
    
    REP2(i, 1, m+1) {
        bitset<MAX> c(b);
        c[i] = false;
        REP2(j, i+1, MAX) if (c[j]) c[j] = false, c[j - i] = true;
        mex.push_back(grundy(c));
    }

    sort(mex.begin(), mex.end());
    mex.erase(unique(mex.begin(), mex.end()), mex.end());
    int i = 0;
    for ( ; i < mex.size() && mex[i] == i; ++i) ;

    mem[b] = i;
    return i;
}

int main() {
    cin >> N;
    REP(i, N) cin >> A[i];

    for (int i = 0; i < N; ++i) {
        for (int p = 2; p * p <= A[i]; ++p) {
            int cnt = 0;
            while (A[i] % p == 0) {
                ++cnt;
                A[i] /= p;
            }
            if (cnt > 0)
                B[p][cnt] = true;
        }
        if (A[i] > 1)
            B[A[i]][1] = true;
    }
    
    int ans = 0;
    for (auto itr: B) {
        ans ^= grundy(itr.second);
    }

    cout << (ans ? "Mojtaba" : "Arpa") << endl;
    
    return 0;
}

2017-09-10

AtCoder Regular Contest 082 F - Sandglass

問題記録 AtCoder ARC ARC #082

http://arc082.contest.atcoder.jp/tasks/arc082_d

問題概要

砂時計に合計X[g]の砂が入っている。砂は1秒に1[g]のペースで上から下に落ちる。砂時計はr1, r2, …, rK秒後にひっくり返される。ここでQ個のクエリ(ti, ai)が与えられるので、初めに砂時計の上の方にai[g], 下の方に(X-ai)[g]入っていた場合、ti秒後にもともと上だった方のパーツに砂が何g入っているか求めよ。

1 <= X <= 10⁹

1 <= K <= 10⁵

1 <= Q <= 10⁵

解法

砂が一度でも全部どちらかに寄ってしまえば、あとの動きはaに関わらず同じになる。まだ一度も寄っていない場合はaに関する単純な一次式になる。というわけで

パーツAに全部寄った場合
パーツBに全部寄った場合
まだ一度も全部寄りになってない場合

の3パターンを持ちながらひっくり返しをシミュレーションしていけばよい。3番目のパターンを見ていればaがこれ以上/以下ならこっちのパーツに全部寄る、みたいな条件は出る。

感想

頑張って手元でいろいろ書いてたらできた

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;


void main() {
    auto X = readln.chomp.to!long;
    auto K = readln.chomp.to!int + 2;
    auto RR = 0 ~ readln.split.map!(to!long).array ~ 10L^^10;
    auto R = (K-1).iota.map!(i => RR[i+1] - RR[i]).array;
    auto Q = readln.chomp.to!int;
    auto T = new long[](Q);
    auto A = new long[](Q);
    foreach (i; 0..Q) {
        auto s = readln.split.map!(to!long);
        T[i] = s[0];
        A[i] = s[1];
    }


    long[] sim0 = [0, X];
    long[] simX = [X, 0];
    long[] simN = [0, X];
    long ub = -1;
    long lb = 1L << 59;


    int q = 0;

    foreach (t; 0..K-1) {
        for ( ; q < Q && RR[t] <= T[q] && T[q] < RR[t+1]; q++) {
            debug {writeln([RR[t], T[q], RR[t+1]]);}
            debug {sim0.writeln; simX.writeln;}

            long ans;

            if (A[q] <= ub) {
                ans = max(0, sim0[0] - T[q] + RR[t]);
            } else if (A[q] >= lb) {
                ans = max(0, simX[0] - T[q] + RR[t]);
            } else if (t % 2 == 0) {
                ans = max(0, simN[0] + A[q] - T[q] + RR[t]);
            } else {
                ans = max(0, simN[0] - A[q] - T[q] + RR[t]);
            }

            if (t % 2)
                ans = X - ans;
            ans.writeln;
        }

        long d0 = min(sim0[0], R[t]);
        sim0[0] -= d0;
        sim0[1] += d0;
        swap(sim0[0], sim0[1]);

        long dX = min(simX[0], R[t]);
        simX[0] -= dX;
        simX[1] += dX;
        swap(simX[1], simX[0]);

        simN[0] -= R[t];
        simN[1] += R[t];
        swap(simN[0], simN[1]);

        if (t % 2 == 0)
            ub = max(ub, -simN[1]);
        else
            lb = min(lb, simN[1]);
    }
}

2017-09-10

AtCoder Regular Contest 082 E - ConvexScore

問題記録 AtCoder ARC ARC #082 幾何

http://arc082.contest.atcoder.jp/tasks/arc082_c

問題概要

二次元平面上のN個の点が与えられる。これらの点の部分集合Sであって凸多角形をなすものについて考える。このようなSの凸包に対し、凸包の周上の点と内部の点の数の合計をnとし、2^n-|S|をSのスコアとする。すべてのSの合計を求めよ。

N <= 200

解法

実は各点を選ぶ・選ばないの2^N通りの全列挙が、スコア計算と実質同じことをやっている。例えば凸包Sに対して内部の点が3個あった場合スコアは2³=8になるが、2^Nの列挙においてこれに対応するのは「Sの点がすべて選ばれる＋内部の点が任意に選ばれる＋他は選ばれない」というパターンである。これは内部の点を選ぶ・選ばないで2³=8通りであり、スコアと一致する。なので基本的には2^Nを計算すればスコアの合計は全部数えたことになる。あとはそこから余分な選び方を引けばよい。余分な選び方は

選ばれる点が1個以下の場合
選ばれる点の凸包が線分になる場合

の2パターンがある。前者も後者も明らかに凸多角形をなさないので、スコア計算対象から外れるためである。

ここで前者は明らかに(N+1)通りある。後者は同じ直線に載っている点集合の数をxとすると2^x通りある（前者との重複を引くと2^x-x-1通り）。これらを2^Nから引けばそれが答えになる。後者の求め方についてはまずありうる直線を列挙しその直線上に乗っている点を数えると、直線列挙でO(N²)（ありうる2点の組合せの列挙）、直線に乗っている点の探索でO(N)の合わせてO(N³)で答えが求まる。

感想

いやわからんわ

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
 
long powmod(long a, long x, long m) {
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}
 
void main() {
    auto N = readln.chomp.to!int;
    auto X = new long[](N);
    auto Y = new long[](N);
    foreach (i; 0..N) {
        auto s = readln.split.map!(to!long);
        X[i] = s[0];
        Y[i] = s[1];
    }
 
    bool line(int i, int j, int k) {
        if (X[i] == X[j]) return X[i] == X[k];
        if (Y[i] == Y[j]) return Y[i] == Y[k];
        if (X[i] == X[k]) return X[i] == X[j];
        if (Y[i] == Y[k]) return Y[i] == Y[j];
        return (Y[k] - Y[i]) * (X[j] - X[i]) == (Y[j] - Y[i]) * (X[k] - X[i]);
    }
 
    const long MOD = 998244353;
    auto used = new bool[][](N, N);
    long ans = 1 + N;
 
 
    foreach (i; 0..N) {
        foreach (j; i+1..N) {
            if (used[i][j])
                continue;
            
            long cnt = 2;
            int[] v = [i, j];
 
            foreach (k; j+1..N) {
                if (used[i][k] || !line(i, j, k))
                    continue;
                cnt += 1;
                v ~= k;
            }
 
            foreach (a; 0..v.length)
                foreach (b; a+1..v.length)
                    used[v[a]][v[b]] = true;
 
            ans += powmod(2, cnt, MOD) - cnt - 1;
            ans %= MOD;
        }
    }
 
    ans = powmod(2, N, MOD) - ans;
    ans = (ans % MOD + MOD) % MOD;
    ans.writeln;
}

2017-09-09

Codeforces Round #432 Div.2 D / Div.1 B - Arpa and a list of numbers

問題記録 Codeforces CF #432

http://codeforces.com/contest/850/problem/B

問題概要

N要素の数列Aが与えられる。以下の操作を好きなだけ繰り返して、数列の全要素のGCDが1でなくなるようにしたい。目的を達成する最小のコストを求めよ。

操作1. コストxで数列から任意の1要素を取り除く
操作2. コストyで数列の任意の1要素に1を足す

1 <= n <= 5×10⁵

1 <= x, y <= 10⁹

1 <= a <= 10⁶

解法

最終的なGCDを固定して考える（この数をgとする）。gの倍数ごとに区間を分けて、その区間ごとに数えるとうまいこといく。

具体的には(kg, (k+1)g]のような区間に含まれる数がgを約数に持つためには、(k+1)gのところまでインクリメントされるしかない。何回目のインクリメントまでがxより得かはxをyで割れば出る。つまり上の区間のうち決まった境界より左の数はxで処理し、右の数はy×距離で処理することになる。境界を仮にmとすると、前者はkg～mの区間に現れる数を累積和すれば求まる。後者は距離に応じてxの係数がインクリメントするので単純な累積和だとだめで、区間内にその数がn回現れるならn回カウントされるような累積和を使いたい。これはxで使った累積和に対してさらに累積和を取ると得られるのでそれを使う（伝われ）、あとそれだけだと区間左外の分もカウントしてしまってるのでそれは良い感じに引く。

頑張ったんですが説明無理だったので要点だけ言うと①GCDを固定します②固定したGCDの倍数ごとに区間を区切ります③区間ごとに累積和を良い感じにやってO(1)で計算します　という感じです。①はO(max(A)), ②はならしでO(log(max(A)))のあわせてO(max(A)log(max(A))).

感想

そもそも解法がむずい上に境界まわりの処理が鬼すぎる、あと解法を書くのもむずすぎる

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
 
void main() {
    auto s = readln.split.map!(to!long);
    auto N = s[0].to!int;
    auto X = s[1];
    auto Y = s[2];
    auto A = readln.split.map!(to!int).array;
    A.sort();
    
    const int MAX = 10^^6 + 1;
    const int border = ((X - 1) / Y).to!int;


    auto cnt = new long[](MAX * 2); 
    auto cntsum = new long[](MAX * 2);
    
    foreach (i; 0..N)
        cnt[A[i]] += 1;
    foreach (i; 0..MAX*2-1)
        cnt[i + 1] += cnt[i];
    foreach (i; 0..MAX*2-1)
        cntsum[i + 1] += cntsum[i] + cnt[i + 1];


    long ans = 1L << 59;
    
    foreach (g; 2..MAX) {
        long tmp = 0;
        for (int l = 1; l < MAX; l += g) {
            int r = l + g - 1;
            int m = max(l, r - border);
            long y = Y * (cntsum[r - 1] - cntsum[m - 1] - cnt[m - 1] * (r - m));
            long x = X * (cnt[m - 1] - cnt[l - 1]);
            tmp += x + y;
        }
        ans = min(ans, tmp);
    }

    debug {
        cnt[0..20].writeln;
        cntsum[0..20].writeln;
    }
    
    ans.writeln;
}

2017-09-09

Codeforces Round #432 Div.2 C / Div.1 A - Five Dimensional Points

問題記録 Codeforces CF #432 幾何

http://codeforces.com/contest/850/problem/A

問題概要

5次元空間上のN個点が与えられる。この中のある点aについて、異なる点b, cを取ってきたときにab, acのなす角が90度未満となるb, cが存在するとき、aを悪い点と呼び、そうでない場合良い点と呼ぶ。良い点をすべて答えよ。

1 <= N <= 10³

解法

Nが33より大きいとき、答えは0である。そうでない場合はN³で全探索すればよい。理由：5次元空間には5個の軸があって2⁵個の象限が存在する。ある点を原点にとったとき同じ象限に存在する点が2点以上あれば、これら3つでつくられる角度は90度未満になる。鳩の巣原理から原点＋32象限よりも多くの点が存在すれば必ず同じ象限に2点が存在することになるので、良い点は存在しないことになる。

問題

天才すぎる

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
     
real angular(int[] x, int[] y, int z[]) {
    int[] v1 = vec(x, y);
    int[] v2 = vec(x, z);
    return acos(product(v1, v2) / sqrt(product(v1, v1) * product(v2, v2)));
}

real product(int[] v1, int[] v2) {
    return v1.length.iota.map!(i => v1[i] * v2[i]).sum.to!real;
}

int[] vec(int[] x, int[] y) {
    return x.length.iota.map!(i => y[i] - x[i]).array;
}


void main() {
    auto N = readln.chomp.to!int;
    auto P = N.iota.map!(_ => readln.split.map!(to!int).array).array;

    if (N >= 50) {
        0.writeln;
        return;
    }

    
    const real EPS = 0.0001;
    auto ans = new bool[N];
    fill(ans, true);
    
    foreach (i; 0..N)
        foreach (j; 0..N)
            foreach (k; 0..N)
                if (i != j && j != k && k != i && angular(P[i], P[j], P[k]) < PI / 2 - EPS)
                    ans[i] = false;

    ans.sum.writeln;
    N.iota.filter!(i => ans[i]).map!(i => (i + 1).to!string).join(" ").writeln;
}