AtCoder Beginner Contest 188

2021-01-21 约 3522 字预计阅读 8 分钟

比赛地址：https://atcoder.jp/contests/abc188 第一次打，太菜了只写出了 3/6

完整代码（A-F）: Github

$2^N$ players, labeled $1$ through $2^N$ , will compete against each other in a single-elimination programming tournament. The rating of Player ${i}$ is $A_i$ . Any two players have different ratings, and a match between two players always results in the victory of the player with the higher rating.

The tournament looks like a perfect binary tree.Formally, the tournament will proceed as follows:

For each integer ${i= 1, 2 , 3 , …,N}$ in this order, the following happens.
- For each integer ${j(1 \leq j \leq 2^{N-i})}$ , among the players who have never lost, the player with the $(2j-1)$ -th smallest label and the player with the $2j$ -th smallest label play a match against each other.

Find the label of the player who will take second place, that is, lose in the final match.

Constraints

$1 \leq N \leq 16$
$1 \leq A_i \leq 10^9$
$A_i$ are pairwise different
All values in input are integers.

Sample Input 1

2
1 4 2 5

Sample Output 1

解法一

题目的意思就是把输入数组当作一颗完全二叉树的最底层元素，相邻的两个 Player 进行淘汰（rating 低的会被淘汰），求最终 battle 中败者的索引（第二）

import java.util.*;
import java.io.*;

class Main {
    //2^16 = 65536
    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int N = Integer.valueOf(br.readLine());
        int[] w = read(br);
        LinkedList<Player> queue = new LinkedList<>();
        for (int i = 0; i < (1<<N); i++) {
            queue.addLast(new Player(i+1, w[i]));
        }
        while (queue.size() > 2) {
            Player p1 = queue.removeFirst();
            Player p2 = queue.removeFirst();
            queue.addLast(p1.rank > p2.rank ? p1 : p2);
        }
        Player p1 = queue.get(0);
        Player p2 = queue.get(1);
        System.out.println(p1.rank > p2.rank ? p2.i : p1.i);
    }

    static class Player{
        int i;
        int rank;
        public Player (int i, int rank) {
            this.rank = rank;
            this.i = i;
        }
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

D - Snuke Prime

Snuke Inc. offers various kinds of services.

A payment plan called Snuke Prime is available.In this plan, by paying $C$ yen (the currency of Japan) per day, you can use all services offered by the company without additional fees.

You can start your subscription to this plan at the beginning of any day and cancel your subscription at the end of any day.

Takahashi is going to use $N$ of the services offered by the company.

He will use the $i$ -th of those services from the beginning of the $a_i$ -th day until the end of the $b_i$ -th day, where today is the first day. Without a subscription to Snuke Prime, he has to pay $c_i$ yen per day to use the $i$ -th service.

Find the minimum total amount of money Takahashi has to pay to use the services.

Constraints

$1 \leq N \leq 2 \times 10^5$
$1 \leq C \leq 10^9$
$1 \leq a_i \leq b_i \leq 10^9$
$1 \leq c_i \leq 10^9$
All values in input are integers.

Sample Input 1

2 6
1 2 4
2 2 4

Sample Output 1

解法一

这题卡了好久，一开始题目的意思就理解了很久，直到结束也没整明白（英语捉急），最后看别人题解的时候才明白啥意思。Otz

这里大概的意思就是说：高桥要使用给出的所有服务，这些服务从 $a_i$ 天开始到 $b_i$ 天结束，每天需要支付 $c_i$ ，同时该公司有另一项政策，就是订阅Snuke Prime，当天支付 $C$ 后就可以使用当天出现的所有服务，不用额外的付钱。比如样例一，第一项服务第一天支付 4，第二天支付 6 同时使用第一项服务和第二项服务，总共 10，这样消费是最小的。

要求总体最小的消耗，我们就得知道每天的最小花费是多大，这里题目给的是一个区间 $a_i \sim b_i$ 内所有时间的花费 $c[i]$ ，而这题数据很大，暴力必然是不可行的。解决办法就是构建出差分数组，然后按时间戳排序，计算使用每天出现的各项服务的总花费，和 $C$ 取一个最小值，然后乘以对应的区间的天数，累加起来就是结果

//1652ms
import java.util.*;
import java.io.*;

class Main {

    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        int N = in[0];
        int C = in[1];
        HashMap<Integer, Long> diff = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int[] abc = read(br);
            int a = abc[0], b = abc[1], c = abc[2];
            // Java 的 map 确实蛋疼。..
            diff.put(a, diff.getOrDefault(a, 0l)+c); diff.put(b+1, diff.getOrDefault(b+1, 0l)-c);
        }
        long res = 0;
        int last = 0; // 上一个时间点
        long sum = 0; // 差分前缀和
        Integer[] keys = diff.keySet().toArray(new Integer[0]);
        // 按照时间排序
        Arrays.sort(keys);
        for (Integer key : keys) {
            long min = Math.min(sum, C);
            res += min * (key-last);
            last = key;
            sum += diff.get(key);
        }
        System.out.println(res);
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

public class D {
    public static void main(String[] args) throws Exception {
        new Main().main();
    }
}

解法二

扫描线的做法，其实和差分思路一样，但是不需要 hash，相比于上面的解法，会稍微快一点

//913ms
import java.util.*;
import java.io.*;

class Event {
    int t, c;
    public Event(int t, int c) {
        this.t = t;
        this.c = c;
    }
}

class Main {

    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        int N = in[0];
        int C = in[1];
        List<Event> events = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int[] abc = read(br);
            int a = abc[0], b = abc[1], c = abc[2];
            events.add(new Event(a, c));
            events.add(new Event(b+1, -c));
        }
        long res = 0;
        int last = 0; // 上一个时间点
        long sum = 0;
        // 按照时间排序
        Collections.sort(events, (e1, e2)->e1.t-e2.t);
        for (Event event : events) {
            long min = Math.min(sum, C);
            res += min * (event.t-last);
            last = event.t;
            sum += event.c;
        }
        System.out.println(res);
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

E - Peddler

In Takahashi Kingdom, there are $N$ towns, called Town $1$ through Town $N$ . There are also $M$ roads in the kingdom, called Road $1$ through Road $M$ . By traversing Road $i$ , you can travel from Town $X_i$ to Town $Y_i$ , but not vice versa. Here, it is guaranteed that $X_i < Y_i$ .

Gold is actively traded in this kingdom. At Town $i$ , you can buy or sell $1$ kilogram of gold for $A_i$ yen (the currency of Japan).

Takahashi, a traveling salesman, plans to buy $1$ kilogram of gold at some town, traverse one or more roads, and sell $1$ kilogram of gold at another town.

Find the maximum possible profit (that is, the selling price minus the buying price) in this plan.

Constraints

$2 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
$1 \leq A_i \leq 10^9$
$1 \leq X_i < Y_i \leq N$
$(X_i, Y_i) \neq (X_j, Y_j)(i \neq j)$
All values in input are integers.

Sample Input 1

Sample Output 1

We can achieve the profit of $3$ yen, as follows:

At Town $1$ , buy one kilogram of gold for $2$ yen.
Traverse Road $2$ to get to Town $2$ .
Traverse Road $1$ to get to Town $4$ .
At Town $4$ , sell one kilogram of gold for $5$ yen.

解法一

这题其实和买卖股票题是一样的，但是我一开始以为题目是有环的。实际上题目条件中说了 $X_i < Y_i$ 所以这就是一个 DAG，直接 DP 就行了， $dp[i]$ 代表从起点（初始入度为 0 的点）到当前节点 $i$ 最低的买入价格。过程中统计一个最大的 $w[j]-dp[i]$ 就行了， $w[j]$ 为当前节点卖出价格， $dp[i]$ 为源点到当前 $j$ 节点之前的最低买入价格（不包括 $j$ ，题目说了不能就地买卖，收益可以为负）

这里的做法是用 BFS 遍历图，从入度为 0 的节点开始，当某个子节点入度为 0 的时候再把他加入队列，保证递推的正确性，过程中维护各个节点的 $dp$ 值，同时计算最大受益，整个过程需要遍历所有的节点和边，所以时间复杂度 $O(N+M)$

//一开始用 hashmap 建图未优化，1000ms+
//改成 ArrayList 建图 845ms，要不是 Java 的 List 太难用我也不会用 map 建图。..
import java.util.*;
import java.io.*;

class Main {

    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int INF = 0x3f3f3f3f;
        int[] nm = read(br);
        int N = nm[0], M = nm[1];
        int[] w = read(br);
        //节点入度数
        int[] in = new int[N];
        List<Integer>[] adj = new ArrayList[N];
        for (int i = 0; i < M; i++) {
            int[] xy = read(br);
            int x = xy[0]-1, y = xy[1]-1;
            if (adj[x] == null) {
                adj[x] = new ArrayList<>();
            }
            adj[x].add(y);
            in[y]++;
        }
        int[] dp = new int[N];
        Arrays.fill(dp, INF);
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            if (in[i] == 0) {
                queue.add(i);
                dp[i] = w[i];
            }
        }
        int res = -INF;
        while (!queue.isEmpty()) {
            int i = queue.poll();
            if (adj[i]==null) continue;
            for (Integer j : adj[i]) {
                res = Math.max(res, w[j] - dp[i]);
                //这里 WA 了好几发。.. 这里 dp[j] 不只在这里计算一次，前面可能计算过了，所以需要对过往的 dp[j] 取 min
                dp[j] = Math.min(dp[j], Math.min(w[j], dp[i]));
                in[j]--;
                if (in[j] == 0) {
                    queue.add(j);
                }
            }
        }
        System.out.println(res);
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

优化后的直接递推的写法，因为题目说了 $x < y$ 所以实际上只能从前向后，所以我们直接循序遍历就一定能保证之前的节点是计算过的，不需要借助队列

//时间上和上面差不多
import java.util.*;
import java.io.*;

class Main {

    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int INF = 0x3f3f3f3f;
        int[] nm = read(br);
        int N = nm[0], M = nm[1];
        int[] w = read(br);
        List<Integer>[] adj = new ArrayList[N];
        for (int i = 0; i < M; i++) {
            int[] xy = read(br);
            int x = xy[0]-1, y = xy[1]-1;
            if (adj[x] == null) {
                adj[x] = new ArrayList<>();
            }
            adj[x].add(y);
        }
        int[] dp = new int[N];
        Arrays.fill(dp, INF);
        int res = -INF;
        //题目说了 x<y，其实也就说明了只能从前向后走，所以直接顺序遍历是没问题的
        for (int i = 0; i < N; i++) {
            //更新当前节点的 dp[i]
            dp[i] = Math.min(dp[i], w[i]);
            if (adj[i]==null) continue;
            for (Integer j : adj[i]) {
                res = Math.max(res, w[j] - dp[i]);
                //这里 WA 了好几发。.. 这里 dp[j] 不只在这里计算一次，前面可能计算过了，所以需要对过往的 dp[j] 取 min
                dp[j] = Math.min(dp[j], Math.min(w[j], dp[i]));
            }
        }
        System.out.println(res);
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

解法二

这个是参考了官方题解，这种解法当图不是 DAG 的时候也适用，也就是不考虑 $xy$ 大小关系，给的图只是一个普通的有向图。

首先对各个城镇的金子价格进行排序，从低到高，然后从价格最低的城镇 $x_1$ 开始 BFS，搜索 $x_1$ 能到达的城镇 $y_i$ ，记录最大的收益，并标记到过的城镇，然后从价格第二低的城镇 $x_2$ 开始同样的操作，但是这一次我们之前已经被标记过的 $x_1$ 能到达的城镇 $y_i$ 便不用再入队了，因为收益一定小于从 $x_1$ 开始的收益。因为需要对点进行排序，所以整体的复杂度 $O(NlogN+M)$

import java.util.*;
import java.io.*;

class Main {

    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int INF = 0x3f3f3f3f;
        int[] nm = read(br);
        int N = nm[0], M = nm[1];
        int[] w = read(br);
        Integer[] tid = new Integer[N];
        for (int i = 0; i < N; i++) tid[i] = i;
        //将 id 按照 cost 从小到大排序
        Arrays.sort(tid, (t1,t2)->w[t1]-w[t2]);
        List<Integer>[] adj = new ArrayList[N];
        for (int i = 0; i < M; i++) {
            int[] xy = read(br);
            int x = xy[0]-1, y = xy[1]-1;
            if (adj[x] == null) {
                adj[x] = new ArrayList<>();
            }
            adj[x].add(y);
        }
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visit = new boolean[N];
        int res = -INF;
        for (int i = 0; i < N; i++) {
            if (visit[tid[i]]) continue;
            queue.add(tid[i]);
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                if (adj[cur]==null) continue;
                for (Integer j : adj[cur]) {
                    if (visit[j]) continue;
                    visit[j] = true;
                    res = Math.max(res, w[j]-w[tid[i]]);
                    queue.add(j);
                }
            }   
        }
        System.out.println(res);
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

F - +1-1x2

Takahashi has written an integer $X$ on a blackboard. He can do the following three kinds of operations any number of times in any order:

increase the value written on the blackboard by $1$ ;
decrease the value written on the blackboard by $1$ ;
multiply the value written on the blackboard by $2$ .

Find the minimum number of operations required to have $Y$ written on the blackboard.

Constraints

$1 \le X \le 10^{18}$
$1 \le Y \le 10^{18}$
$X$ and $Y$ are integers.

Sample Input 1

3 9

Sample Output 1

解法一

这个 F 其实很简单。.. 甚至我之前也做过类似的题（吃掉-N-个橘子的最少天数），但是比赛的时候题都没看😂

这题如果直接考虑从 $X \rightarrow Y$ 的话，每层递归都有 3 个分支，很明显会爆栈。我们可以将问题转化从 $Y \rightarrow X$ 的等价问题，反过来 $Y$ 转化成 $X$ 就有三种选择： $y-1$ , $y+1$ , $y/2$ 。首先 $y/2$ 时 $y$ 必须要是偶数，奇数情况只考虑 $y+1$ 和 $y-1$ ，那么 $y$ 为偶数时能考虑加一和减一分支吗？

$y$ 为偶数（只考虑 $y > x$ ，小于 $x$ 差值就是答案），这时候 $y+1$ 会增大 $y$ 和 $x$ 的差距，那么有没有可能是 $y+2$ 然后再除二使得次数更少呢？也是不可能的， $(y+2)/2 = y/2+1$ ，转换到同一个值，前者需要 3 次变化，而后者只需要 2 次变化，所以直接除 2 是最优选择
$y-1$ 同理，但是我们也需要考虑 $y$ 和 $x$ 差距很小的时候， $y$ 直接一步步的减到 $x$ 的情况

如此一来，我们再加上记忆化，复杂度直线下降，每个分支都有除 2，时间复杂度降低为对数级别

import java.util.*;
import java.io.*;

class Main {

    static HashMap<Long, Long> dp = new HashMap<>();

    public static void main(String... args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        long[] xy = read(br);
        long x = xy[0], y = xy[1];
        if (x >= y) {
            System.out.println(x-y);
            return;
        }
        System.out.println(dfs(x, y));
    }

    public static long dfs (long x, long y) {
        if (x > y) return x-y;
        if (x == y)  return 0;
        if (dp.containsKey(y)) {
            return dp.get(y);
        }
        long res = y-x;
        if (y%2==0) {
            res = Math.min(dfs(x, y/2)+1, res);
        } else {
            res = Math.min(dfs(x, (y-1)/2)+2, res);
            res = Math.min(dfs(x, (y+1)/2)+2, res);
        }
        dp.put(y, res);
        return res;
    }

    public static long[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
    }
}

目录

AtCoder Beginner Contest 188

A - Three-Point Shot

B - Orthogonality

C - ABC Tournament

解法一

D - Snuke Prime

解法一

解法二

E - Peddler

解法一

解法二

F - +1-1x2

解法一