Educational Codeforces Round 45

Editorial
A問題
B問題
C問題
D問題
E問題
F問題
G問題(未解決)

Editorial

codeforces.com

A問題

問題

codeforces.com

$N$ 個の解説ボックスと $M$ 個の団体チームが存在しており、各団体チームに均等に解説ボックスを割り当てたい
$N$ を $M$ で割り切れないときは、各団体チームに解説ボックスを割り当てることが出来ない

1つの解説ボックスを解体するのに $a$ burles支払う
1つの解説ボックスを建てるのに $b$ burles支払う

各団体チームに同じ数の解説ボックスを配布したい時、支払うburlesの最小値を求める

考察

解説ボックスの数を $M$ (団体チーム数)で割り切れるまで
解体する( $a$ burles支払う)か
建てる( $b$ burles支払う)かどちらか一方を行うことを考えると
$N \mod M = 解体する回数$
$N - (N \mod M) = 解説ボックスを建てる回数$
が分かる
結果的に支払うburlesの最小値は $min(N \mod M \times a, (N - N \mod M) \times b)$ になる

ソースコード

Submission #39089978 - Codeforces

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class A {

    long N,M;
    int A,B;

    private void solve() {
        N = nextLong();
        M = nextLong();
        A = nextInt();
        B = nextInt();

        long mod = N % M;

        long a = A * (M - mod);
        long b = B * mod;

        long ans = Math.min(a, b);
        out.println(ans);
    }
}

B問題

問題

codeforces.com

皿の上に $N(1 \le N \le 2 \times 10^5)$ 体のバクテリアが存在する
$i$ 番目のバクテリアの大きさは $a_i(1 \le a_i \le 10^6)$ である
$K(1 \le K \le 10^6)$ という定数が与えられる

$i$ 番目のバクテリアは以下の条件を満たすとき、 $j$ 番目のバクテリアを食べることが出来る

$a_i \gt a_j$
$a_i \le a_j + K$

食べられた $j$ 番目のバクテリアは皿の上から消える( $i$ 番目のバクテリアの大きさは変化しない)

最終的に皿の上に残存しているバクテリアの数の最小値を求める

考察

まず、大きさの昇順にソートする
$a_i$ は重複する場合があるので、同じ $a_i$ はまとめる
大きさの昇順に $a_i$ を見ていき、 $a_{i-1} + K \ge a_i$ を満たす場合
$a_{i-1}$ のバクテリアを除いていく

ソースコード

Submission #39101019 - Codeforces

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class B {

    int N,K;
    ArrayList<Integer> a;

    private void solve() {
        N = nextInt();
        K = nextInt();
        a = new ArrayList<>();
        for(int i = 0;i < N;i++) {
            a.add(nextInt());
        }

        Collections.sort(a);
        TreeMap<Integer,Integer> map = new TreeMap<>();
        for(int v : a) {
            if (map.containsKey(v)) {
                map.put(v, map.get(v) + 1);
            } else {
                map.put(v, 1);
            }
        }
        ArrayList<Integer> b = new ArrayList<>();
        for(int v : map.keySet()) {
            b.add(v);
        }

        int ans = N;
        for(int i = 0;i < b.size() - 1;i++) {
            int j = i + 1;
            if (b.get(i) < b.get(j) && b.get(i) + K >= b.get(j)) {
                ans -= map.get(b.get(i));
            }
        }

        out.println(ans);
    }
}

C問題

問題

codeforces.com

$N(1 \le N \le 3 \times 10^5)$ 個の"(",")"のみが含まれる文字列 $s_i(1 \le i \le N)$ が与えられる

2つの文字列 $s_i, s_j$ を選び、文字列結合した結果 $s_i + s_j$ が有効な括弧文字列であるペア $(i, j)$ の数を求める
$i \neq j$ でペア $(i, j)$ と $(j, i)$ が有効な括弧文字列である場合、どちらも別々でカウントする
$i = j$ でペア $(i,j)$ と $(j, i)$ が有効な括弧文字列である場合、1つとカウントする

考察

3つパターンで $N$ 個の括弧文字列を分ける

既に有効な括弧文字列である場合
文字列の左から順に見ていく。")"を見ている時、その文字列内で"("と")"で対応できていない")"の数が1つ以上の場合
文字列の右から順に見ていく。"("を見ている時、その文字列内で"("と")"で対応できていない"("の数が1つ以上の場合

後は

$パターン1の文字列の数 \times (パターン1の文字列の数-1)$
$パターン2で対応できていない")"の個数がA個の数 \times パターン3で対応できていない"("の個数がA個の数$
$パターン3で対応できていない")"の個数がB個の数 \times パターン3で対応できていない"("の個数がB個の数$

上記のパターンをすべて足した数が解

ソースコード

Submission #39109916 - Codeforces

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class C {

    int N;
    String[] brackets;

    private void solve() {
        N = nextInt();
        brackets = new String[N];
        for(int i = 0;i < N;i++) {
            brackets[i] = next();
        }


        TreeMap<Integer, Integer> leftMinus = new TreeMap<>();
        TreeMap<Integer, Integer> rightPlus = new TreeMap<>();
        int zero = 0;
        for(int i = 0;i < N;i++) {
            char[] b = brackets[i].toCharArray();
            int L = b.length;

            int depth = 0;
            int leftCnt = 0;
            for(int j = 0;j < L;j++) {
                if (b[j] == ')') {
                    depth--;
                } else {
                    depth++;
                }

                if (depth < 0) {
                    leftCnt++;
                }
            }

            depth = 0;
            int rightCnt = 0;
            for(int j = L-1;j >=0;j--) {
                if (b[j] == '(') {
                    depth--;
                } else {
                    depth++;
                }

                if (depth < 0) {
                    rightCnt++;
                }
            }

            if (leftCnt > 0 && rightCnt > 0) {
                continue;
            }

            if (leftCnt == 0 && rightCnt == 0) {
                zero++;
                continue;
            }

            if (leftCnt > 0) {
                if (leftMinus.containsKey(depth)) {
                    leftMinus.put(depth, leftMinus.get(depth) + 1);
                } else {
                    leftMinus.put(depth, 1);
                }
            }

            if (rightCnt > 0) {
                if (rightPlus.containsKey(depth)) {
                    rightPlus.put(depth, rightPlus.get(depth) + 1);
                } else {
                    rightPlus.put(depth, 1);
                }
            }
        }

        long ans = ((long)zero) * (zero);

        for(int m : leftMinus.keySet()) {
            if (rightPlus.containsKey(-m)) {
                ans += ((long) leftMinus.get(m)) * rightPlus.get(-m);
            }
        }

        out.println(ans);
    }
}

D問題

問題

codeforces.com

頂点数が $N(1 \le N \le 1000)$ の0と1を含む正方行列で表される無向グラフ $G$ を考える
$(row, column) = (i,j)$ が1の場合は頂点 $i$ と頂点 $j$ は辺で繋がっていることを表す

無向グラフ $G$ の連結成分の数が $a(1 \le a \le N)$ 、無向グラフ $G$ の補グラフ上の連結成分の数が $b(1 \le b \le N)$ である
無向グラフ $G$ を表すことが出来るかを考える
※補グラフの説明：
補グラフ - Wikipedia

考察

$n=3,4,5$ とかのパターンで色々実験してみると
$a > 1$ の場合は $b = 1$ になることに気付く( $b > 1$ の場合は $a = 1$ )
これは補グラフの特徴として
無向グラフ $G$ 上で辺が繋がっていない頂点同士はグラフ $G$ の補グラフ $H$ 上では辺で繋がることに基づく
例えば、 $N = 4$ の $G$ 上で2つの連結成分 $x, y$ が存在し
連結成分 $x$ では頂点 $0, 1$
連結成分 $y$ では頂点 $2, 3$ を含むとする
$G$ の補グラフ $H$ では
頂点 $0$ は $2,3$ と辺で繋がり、頂点 $1$ も $2,3$ と繋がり、最終的に $H$ では1つの連結成分となる

これで $a > 1$ で $b > 1$ の場合は条件を満たす無向グラフ $G$ を表すことが出来ないことが分かった
あとは $b = 1$ の場合を考えると
連結成分の数が $a$ になるまで頂点同士を辺で繋げていけば良い
$a = 1$ の場合も $b = 1$ の時と同じ考えで解ける

特殊ケースがある
N = 2,A = 1,B = 1
N = 3,A = 1,B = 1

ソースコード

Submission #39414034 - Codeforces

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class D {

    int N,A,B;

    private void solve() {
        N = nextInt();
        A = nextInt();
        B = nextInt();

        int min = Math.min(A ,B);
        if (min > 1) {
            out.println("NO");
            return;
        }

        if ((N == 2 && A == 1 && B == 1) || (N == 3 && A == 1 && B == 1)) {
            out.println("NO");
            return;
        }

        int[][] G = new int[N][N];

        if (A == 1) {
            for(int i = 0;i < N;i++) {
                for(int j = 0;j < N;j++) {
                    if (i == j) {
                        G[i][j] = 0;
                    } else {
                        G[i][j] = 1;
                    }
                }
            }
            for(int i = 0;i < N - B;i++) {
                G[i][i+1] = 0;
                G[i+1][i] = 0;
            }
        } else {
            for(int i = 0;i < N - A;i++) {
                G[i][i+1] = 1;
                G[i+1][i] = 1;
            }
        }

        out.println("YES");
        for(int i = 0;i < N;i++) {
            for(int j = 0;j < N;j++) {
                out.print(G[i][j]);
            }
            out.println();
        }
    }
}

E問題

問題

codeforces.com

Adilbekの家はx軸上で表される通りに存在している
通りはとても暗いので、照らすためにいくつかの照明を設置したい
通りには照明を設置するための $N(1 \le N \le 10^6)$ 箇所があり、それぞれ $0 から N-1$ に対応している
しかし、 $M(1 \le M \le N)$ 箇所にはランプが設置出来ない
それぞれパワーの違いによって異なるタイプの照明がある
位置 $x$ に設置し、パワーが $l$ である照明は区間 $[ x, x + l ]$ を照らす
照明はパワーが $1 から K(1 \le K \le N \le 10^6)$ までの異なるタイプがそれぞれ無限個売っている
客は1つのタイプしか購入できない
パワーが $l$ の照明を購入するには $a_l(1 \le a_l \le 10^6)$ のコストが掛かる
通りの全体 $[0 : N]$ を照らすための照明を購入する最小コストを求める

考察

各パワー $l(1 \le l \le K)$ について
$N$ 箇所すべて照らせるように $[x , x+l],[x + l + 1 , x + l \times 2 + 1],,,$ を照らすように貪欲に試していく。
試していく途中で $x + l + 1$ がランプが設置出来ない位置の場合は
区間 $[x+1 , x + l]$ 内(既に設置した1つ前のランプの位置と設置出来ない位置の間)でランプが設置出来る最大の位置に次のランプを設置するようにする

$N$ と $K$ の制約から間に合わないと思ってしまったが、意外と間に合う
これは各パワー $l$ を試していく中で $l$ が増加していき、ランプが照らす範囲が大きくなり、ランプを置く候補が絞られていくイメージから

ソースコード

Submission #39438365 - Codeforces

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class E {

    int N,M,K;
    int[] s,a;

    private void solve() {
        N = nextInt();
        M = nextInt();
        K = nextInt();

        s = new int[M];
        for(int i = 0;i < M;i++) {
            s[i] = nextInt();
        }
        a = new int[K + 1];
        for(int i = 1;i <= K;i++) {
            a[i] = nextInt();
        }

        boolean[] blocked = new boolean[N + 1];
        for(int i = 0;i < M;i++) {
            blocked[s[i]] = true;
        }

        int[] notBlockIndex = new int[N + 1];
        notBlockIndex[N] = N;
        int index = 0;
        for(int i = 0;i < N;i++) {
            if (!blocked[i]) {
                index = i;
            }
            notBlockIndex[i] = index;
        }

        long ans = Long.MAX_VALUE;
        for(int i = 1;i <= K;i++) {
            int now = 0;
            long count = 0;

            if (blocked[now]) {
                continue;
            }

            while(now < N) {
                int next = Math.min(N, now + i);
                int nextnext = notBlockIndex[next];

                if (now == nextnext) {
                    break;
                }
                now = nextnext;
                count++;
            }

            if (!blocked[now] && now >= N) {
                ans = Math.min(ans, count * a[i]);
            }
        }

        if (ans == Long.MAX_VALUE) {
            ans = -1;
        }
        out.println(ans);
    }
}

F問題

問題

codeforces.com

$N(1 \le N \le 2 \times 10^5)$ 個の分岐点と $M(0 \le M \le 2 \times 10^5)$ 本のパイプで構成されている水分配システムがある
$i(1 \le i \le M)$ 番目のパイプは分岐点 $x_i$ と $y_i$ 間に接続されている
$f_i >= 0$ の場合は $x_i$ から $y_i$ に向かって $f_i$ の水が流れる
$f_i < 0$ の場合は $y_i$ から $x_i$ に向かって $|f_i|$ の水が流れる
この $f_1,f_2,f_3, ..., f_M$ を求めたい
$i(1 \le i \le N)$ 番目の分岐点に水の流入量と水の放出量の差 $s_i(-10^4 \le s_i \le 10^4)$ が定められている
$s_i >= 0$ の場合は $i$ 番目の分岐点への水の流入量が水の放出量より $s_i$ 多いことを表す
$s_i < 0$ の場合は $i$ 番目の分岐点からの水の放出量が水の流入量より $|s_i|$ 多いことを表す
$f_1,f_2,f_3, ..., f_M$ が上記の要件を満たすように出来るか
出来る場合は $f_1,f_2,f_3, ..., f_M$ を出力し、不可能な場合-1を出力する

考察

要件を満たす $f_i$ を求められるかは各分岐点の放出量の総和と各分岐点の流出量の総和が等しく出来るかで分かる

適当な分岐点 $i$ を決め、パイプ $k$ で接続している分岐点 $j$ に水を放出または、 $j$ から $i$ へ水を流入すること考える
パイプが分岐点 $i$ から $j$ に接続されている場合、 $f_k = s_i \times (-1)$
パイプが分岐点 $j$ から $i$ に接続されている場合、 $f_k = s_i$
そして $s_j$ から $s_i$ 分の流量を加える

これを分岐点 $j$ と接続されている次の分岐点間のパイプについて同様に考え、繰り返していき
すべてのパイプについて流量をDFS等で貪欲に決めていく

ソースコード

Submission #39543693 - Codeforces

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.NoSuchElementException;

public class F {

    int N,M;
    int[] x,y;
    long[] s,flow,sum;
    boolean[] visited;
    ArrayList<Edge>[] graph;

    private class Edge {
        int ind, to, dir;
        public Edge(int ind, int to, int dir) {
            this.ind = ind;
            this.to = to;
            this.dir = dir;
        }
    }

    private void dfs(int n) {
        visited[n] = true;

        for(Edge e : graph[n]) {
            if (visited[e.to]) {
                continue;
            }
            dfs(e.to);
            flow[e.ind] = s[e.to] * e.dir;
            s[n] += s[e.to];
        }
    }


    @SuppressWarnings("unchecked")
    private void solve() {
        N = nextInt();
        s = new long[N];
        sum = new long[N];
        for(int i = 0;i < N;i++) {
            s[i] = nextInt();
        }
        M = nextInt();
        x = new int[M];
        y = new int[M];
        for(int i = 0;i < M;i++) {
            x[i] = nextInt()-1;
            y[i] = nextInt()-1;
        }

        long sum = 0;
        for(int i = 0;i < N;i++) {
            sum += s[i];
        }
        if (sum != 0) {
            out.println("Impossible");
            return;
        }

        graph = new ArrayList[N];
        for(int i = 0;i < N;i++) {
            graph[i] = new ArrayList<>();
        }

        for(int i = 0;i < M;i++) {
            graph[x[i]].add(new Edge(i, y[i], 1));
            graph[y[i]].add(new Edge(i, x[i], -1));
        }

        flow = new long[M];
        visited = new boolean[N];
        dfs(0);

        out.println("Possible");
        for(int i = 0;i < M;i++) {
            out.println(flow[i]);
        }
        out.println();
    }
}

G問題(未解決)

問題

codeforces.com

$N$ 個の頂点を含む木が与えられる
頂点 $i$ には数値 $a_i$ が書かれている
関数 $g(x,y)$ は頂点 $x$ と頂点 $y$ 間のパスに含まれる頂点( $x,y$ を含める)に書かれている数値の最大公約数を求める
$1から2 \times 10^5$ の各整数に対して $g(x,y)$ の計算結果がその整数に対応している $(x,y)$ のペア数を数えたい