Typical DP Contest H - ナップザック

http://tdpc.contest.atcoder.jp/tasks/tdpc_knapsack

問題概要

N個のものがあって、それぞれに重さw・価値v・色cが設定されている。重さ合計の最大値Wと使える色の種類の最大値Cが与えられるので、その範囲内で価値の合計が最も高くなるような組合せを選んだときの価値の最大値を求めよ。

N <= 100

W <= 10000

C <= 50

解法

普通にDPをやろうとすると「重さ」と「使った色の種類」を状態に取ってやることになるが、これだと状態数がO(W2C)、遷移がO(NW2C)になって全然間に合わない。

まず必要なのは各色ごと別個にDPを行うことである。つまり色の条件を無視して重さだけで普通のナップザック問題を解くようなDPをやる。これである一色について各重さごとの価値を出すことができる(=ひとつひとつのものを個別にみる必要がなくなり、色単位で考えていくことができるようになる)。

次に(使った色数、重さ)を状態にしてまたDPをやる。色を順番に舐めながら、i色目を使う時には0~(i-1)色目のDPに対して更新をかけ、使った色が一色増えたという扱いにすればよい。以上でC色まで使ったときの重さW以下の最大値が出せる。

最初のDPがO(NWC), 次のDPが(WC2)で十分間に合う。

感想

自力では解けず。2NをN2に落とすというところを考えると典型といえる……のか???

コード (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!int);
    auto N = s[0], W = s[1], C = s[2];
    auto WV = new Tuple!(int, int)[][](55);
    foreach (i; 0..N) {
        s = readln.split.map!(to!int);
        WV[s[2]] ~= tuple(s[0], s[1]);
    }


    auto dp = new int[][](55, 10101);

    foreach (c; 1..55) {
        foreach (c2; iota(c-1, -1, -1)) {
            auto tmp = dp[c2].dup;

            foreach (wv; WV[c]) {
                int w = wv[0], v = wv[1];
                foreach (i; iota(10100, -1, -1))
                    if (tmp[i] > 0 && i + w <= W)
                        tmp[i+w] = max(tmp[i+w], tmp[i] + v);
                if (w <= W)
                    tmp[w] = max(tmp[w], v);
            }

            foreach (i; 0..10101)
                dp[c2+1][i] = max(dp[c2+1][i], tmp[i]);
        }
    }

    dp[C][0..W+1].reduce!max.writeln;
}

Typical DP Contest J - ボール

http://tdpc.contest.atcoder.jp/tasks/tdpc_ball

問題概要

一次元の座標xiにN個の目標物が設置されている。座標xを狙ってボールを投げると等確率でx-1, x, x+1のいずれかにボールが飛んでいき、そこに目標物があればそれを倒せる。狙う座標を最適に選んだとき、すべての目標物を倒すために必要なボール投げ回数の期待値を求めよ。

1 <= N <= 16

0 <= xi <= 15

解法

座標の範囲が狭いので、座標xiに目標物がある/ないの状態をbit列で表せばbitDPができる。遷移がよくわからんが、雰囲気で以下のようにやったら通ってしまった。

  1. 狙う座標の周囲3マスに全部目標物があるとき
  2. どれか1個が倒れた状態に1/3で遷移 + 1 (1回投げれば必ず1個は倒れるので)
  3. 周囲2マスに目標物があるとき
  4. どちらか1個が倒れた状態に1/2で遷移 + 1.5 (どちらか2つにボールが行くのは2/3なので、その逆数)
  5. 周囲1マスに目標物があるとき
  6. その1個が倒れた状態に1/1で遷移 + 3 (1/3の逆数)

通した後もモヤモヤしてたが以下の記事を読んだらすべてが腑に落ちた。

http://pekempey.hatenablog.com/entry/2016/02/05/002257

自己遷移を含む場合(この問題でいうところの何もないところにボールを投げてしまうケース)、遷移を数式で表して式変形するというテクが使えるというのが重要ポイントだったっぽい。

感想

期待値DPの基本的な流れは 期待値(次の状態) × 遷移確率 で、「次の状態」が自己遷移になっている場合には式を立てて解く、という感じで理解しておけばいいんだろうか。

コード (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 N = readln.chomp.to!int;
    auto X = readln.split.map!(to!int).array;


    auto mem = new real[](1 << 16);
    mem.fill(-1);

    real dfs(int mask) {
        if (mem[mask] >= 0)
            return mem[mask];
        if (mask == 0)
            return 0;

        real ret = 1L << 59;

        foreach (i; 1..15) {
            int b = (mask & (0b111 << (i - 1))) >> (i - 1);
            int nmask = mask & ~(0b111 << (i - 1));
            real tmp = 1L << 59;
            
            if (b == 0b111) {
                tmp =
                    dfs(nmask | (0b011 << (i - 1))) / 3 +
                    dfs(nmask | (0b101 << (i - 1))) / 3 +
                    dfs(nmask | (0b110 << (i - 1))) / 3 + 1;
            } else if (b == 0b011) {
                tmp =
                    dfs(nmask | (0b001 << (i - 1))) / 2 +
                    dfs(nmask | (0b010 << (i - 1))) / 2 + 1.5L;
            } else if (b == 0b101) {
                tmp =
                    dfs(nmask | (0b001 << (i - 1))) / 2 +
                    dfs(nmask | (0b100 << (i - 1))) / 2 + 1.5L;
            } else if (b == 0b110) {
                tmp =
                    dfs(nmask | (0b010 << (i - 1))) / 2 +
                    dfs(nmask | (0b100 << (i - 1))) / 2 + 1.5L;
            } else if (b.popcnt == 1) {
                tmp = dfs(nmask) + 3.0L;
            }
            
            ret = min(ret, tmp);
        }

        mem[mask] = ret;
        return ret;
    }

    
    int mask = 0;
    foreach (x; X)
        mask |= (1 << x);
    writefln("%.9f", dfs(mask));
}

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 <= 105

0 <= M <= 105

解法

尺取り法っぽくやる。全員分の行きチケットを確保したとき、使える帰りチケットは行きチケットの中で一番遅い日付+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;
}

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

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

問題概要

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

1 <= N <= 106

0 <= D <= 109

0 <= Gi <= 109

解法

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

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

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

区間の総和は累積和を計算しておけばO(1)でできる。区間の最大値はいろいろあるけどセグ木でO(logN)でできる。セグ木はpairとかでインデックスも持つようにすると最大値だけじゃなくてそのインデックスも取ってくるようにできる。この場合和をセグ木にしてもオーダーは変わらないが、この問題はN<=106で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;
}

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

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

問題概要

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

N <= 100

max(A) <= 109

解法

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

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

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

というわけで問題は特定の素数に対する操作をどう表すか、という点に移る。例えば21と23を因数に持つ要素があり、他の要素に2xの因数は含まれていなかったとすると、選べる2kはk=1, 2, 3の3通りである。1を選ぶと21が20に、23が22になる。2を選ぶと21は割り切れないので変わらず、23は21になる。これを一般化すると、素数pに対して数列中の因数にpa, pb, pc,…が存在している場合、取れる操作はp1~p^(最大の指数)のうちひとつを選んで割ることである。選んだ数未満の指数は割り切れないので変化せず、選んだ数以上の指数は選んだ数のぶん引き算される。これが遷移になる。ここで230 > 109より最大の指数は高々30程度であり、さらに一回の操作で最大の指数は必ず小さくなっていくので、状態数も大して増えない。というわけである素数pについてpxの因数がある・ないを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;
}

AtCoder Regular Contest 082 F - Sandglass

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 <= 109

1 <= K <= 105

1 <= Q <= 105

解法

砂が一度でも全部どちらかに寄ってしまえば、あとの動きは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]);
    }
}

AtCoder Regular Contest 082 E - ConvexScore

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

問題概要

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

N <= 200

解法

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

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

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

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

感想

いやわからんわ

コード (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;
}