朝の部

問題1: 鳥の撃ち合い

問題文:

n×nのグリッド上に、各格子点に1羽ずつ鳥がいます。(0,0)を除いて、すべての格子点に鳥がいます。(0,0)には無音の機関銃があり、任意の角度で発射できます。機関銃を発射すると、(0,0)から放射状に伸びる直線上にあるすべての鳥が撃たれます。最大でk回発射できます。撃てる鳥の最大数はいくつでしょうか？

ただし、m羽の鳥は事前に風に乗って飛び去っています。

制約: 1≤n≤4000000, 1≤k≤16000000000000, 1≤m≤min(n×n-1,2500)

解法:

まず、m=0の場合を考えます。各点は高々1つの直線上にしか存在しないため、各直線が打てる鳥の数を計算し、そのうち大きい方からk個を選びます。y=xを除き、すべての直線は一意であり、傾きが1未満の直線と1より大きい直線は一対一で対応できるため、傾きが1未満の直線のみを考えます。

(0,0)を通る直線y=(p/q)x(p= x])です。f[1]が0に等しいかどうかを判定します。

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
const int N = 2e5 + 10;
vector<int> g[N];
int n, a[N];
int f[N];

void dfs(int u, int fa) {
    ll sum = 0;
    for(int v : g[u]) {
        if(v == fa) continue;
        dfs(v, u);
        sum += f[v];
    }
    f[u] += max(0LL, sum - 1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 2; i <= n; i++) 
        cin >> a[i];
    
    for(int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    
    ll l = 1, r = 1e9, ans = 0; 
    while(l <= r) {
        ll mid = (l + r) >> 1;
        for(int i = 1; i <= n; i++) 
            f[i] = (a[i] >= mid);
        
        dfs(1, 0);
        
        if(f[1] == 0) 
            r = mid - 1;
        else {
            ans = mid;
            l = mid + 1;
        }
    }
    cout << ans;

    return 0;
}

問題2: 無向グラフの彩色

問題文:

n個の頂点とm辺の無向グラフが与えられます。k種類の色（1からkまで）を使用して頂点を彩色します。隣接する頂点同士の色の番号の合計がzにならないようにしてください。条件を満たす彩色の方法は何通りありますか？答えは1000000007で割った余りを求めてください。

制約: 1≤n≤18, 0≤m≤min(18,n×(n-1)/2), 1≤k≤10^9, 2≤z≤2×10^9

解法:

包含排除原理を考えます。不可行辺をcolor_u + color_v = zとなる辺(u,v)と定義します。不可行辺の集合Sに対して、このグラフを構築します。

孤立点の場合、彩色の可能性はk通りです。

次に、頂点数>1の連結成分を考えます。2つのケースがあります：

• この連結成分に奇閉路がある場合：zが偶数の場合、すべての頂点をz/2に彩色するしかありません。そうでなければ彩色不可能です。
• この連結成分に奇閉路がない場合：1つの頂点の色が決まれば、連結成分全体の色が決まります。1つの頂点の可能性は以下の通りです：

1. k×2 < zの場合：0
2. k >= z-1の場合：z-1
3. それ以外の場合：2×k - (z-1)

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;
const int N = 18 + 3, mod = 1e9 + 7;

int n, m, k, z;
int from[N], to[N], nodecnt;

ll qpow(ll x, ll y) {
    ll ret = 1;
    while(y) {
        if(y & 1) ret = (ret * x) % mod;
        x = (x * x) % mod;
        y >>= 1;
    }
    return ret;
}

struct edge {
    int v, next;
} edges[N << 1];
int head[N], idx;

void add_edge(int u, int v) {
    edges[++idx] = {v, head[u]};
    head[u] = idx;
}

int col[N];

int popcount(int x) {
    if(!x) return 0;
    return popcount(x >> 1) + (x & 1); 
}

void build(int S) {
    idx = 0; nodecnt = 0;
    for(int i = 1; i <= n; i++) {
        head[i] = 0;
        col[i] = 0;
    }
    
    for(int i = 0; i < m; i++) {
        if((1 << i) & S) {
            add_edge(from[i + 1], to[i + 1]);
            add_edge(to[i + 1], from[i + 1]);
        }
    }  
    
    for(int i = 1; i <= n; i++) 
        if(head[i]) 
            nodecnt++;
}

bool checker(int u) {
    bool flag = true;
    for(int i = head[u]; i; i = edges[i].next) {
        int v = edges[i].v;
        if(!col[v]) {
            col[v] = -col[u];
            flag &= checker(v);
        } else if(col[v] + col[u] != 0) 
            flag = false;
    }
    return flag;
}

ll solve_component() {
    ll ret = 1;
    for(int i = 1; i <= n; i++) {
        if(!col[i] && head[i]) {
            col[i] = 1;
            if(checker(i) && (z <= 2 * k)) 
                ret = (ret * component_color_options()) % mod;
            else if((z & 1) || z > 2 * k) 
                ret = 0;
        }
    }
    return ret;
}

ll component_color_options() {
    if(k >= z - 1) return z - 1;
    if(2 * k < z) return 0;
    return 2 * k - z + 1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k >> z;
    for(int i = 1; i <= m; i++) 
        cin >> from[i] >> to[i];
    
    ll ans = 0;
    for(int S = 0; S < (1 << m); S++) {
        build(S);
        ll sign = (popcount(S) & 1) ? -1 : 1;
        ll term = (qpow(k, n - nodecnt) * sign * solve_component()) % mod;
        ans = (ans + term + mod) % mod;
    }
    cout << ans;

    return 0;
}