Codeforces #486 Div3 - tookunn’s diary

Editorial
A問題
B問題
C問題
D問題
E問題
F問題

Editorial

codeforces.com

A問題

問題

codeforces.com

長さ $N(1\le N\le 100)$ の数列 $a(1 \le a_i \le 100)$ が与えられる
数列 $a$ から値が重複しないように $K(1 \le K \le N)$ 個取り出せるか

取り出せる場合は $K$ 個の $a_i(1 \le i \le K)$ の $i$ を出力する

考察

$a$ に含まれる整数の種類が $K$ 個未満なら取り出すのは不可能
$K$ 個以上の場合は $map[a_i] = i$

ソースコード

Submission #38839259 - Codeforces

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

public class A {

    int N,K;
    int[] a;

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

        a = new int[N];
        for(int i = 0;i < N;i++) {
            a[i] = nextInt();
        }

        int[] map = new int[100 + 1];

        for(int i = 0;i < N;i++) {
            map[a[i]] = i + 1;
        }

        ArrayList<Integer> ans = new ArrayList<>();
        for(int i = 0;i < 100 + 1;i++) {
            if (map[i] > 0) {
                ans.add(map[i]);
            }
        }

        if (ans.size() < K){
            out.println("NO");
            return;
        }

        out.println("YES");
        for(int i = 0;i < K;i++) {
            if (i != 0) {
                out.print(" ");
            }
            out.print(ans.get(i));
        }
        out.println();
    }
}

B問題

問題

codeforces.com

$N(1 \le N \le 100)$ 個の文字列 $S(1 \le len(S_i) \le 100)$ が与えられる
$S_{i-1}$ が部分文字列として $S_i$ に含まれるように $N$ 個の文字列を並べ替えが可能か
可能な場合、並べ替えた $N$ 個の文字列 $S$ を出力する

考察

文字列の長さで $N$ 個の文字列 $S$ をソートして
$S_{i-1}$ が部分文字列として $S_i$ に含まれているかを $i(1 \le i \le N-1)$ についてチェック

文字列の長さでソートするのはよく考えると分かる

$len(S_{i-1}) = len(S_i)$ の場合 $S_{i-1}$ が部分文字列として $S_i$ に含まれるのは $S_{i-1} = S_i$ の場合のみ
並べ替えが可能な場合、 $S_i(1 \le i \le N-1)$ が部分文字列として $S_j(i \lt j \le N)$ に必ず含まれていなければいけない

ソースコード

Submission #38842064 - Codeforces

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

public class B {

    int N;
    String[] s;

    private void sort(String[] s) {

        for(int i = 0;i < N;i++) {
            for(int j = i+1;j < N;j++) {
                if (s[i].length() > s[j].length()) {
                    String tmp = s[i];
                    s[i] = s[j];
                    s[j] = tmp;
                }
            }
        }
    }

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

        sort(s);
        for(int i = 0;i < N-1;i++) {
            if (s[i+1].indexOf(s[i]) == -1) {
                out.println("NO");
                return;
            }
        }
        out.println("YES");
        for(int i = 0;i < N;i++) {
            out.println(s[i]);
        }
    }
}

C問題

問題

codeforces.com

$K(2 \le K \le 2 \times 10^5)$ 個の長さ $n_i(1 \le n_i \lt 2 \times 10^5)$ の各数列 $a(-10^4 \le a_i \le 10^4)$ が与えられる
各数列の長さの総和 $(\sum_{i = 0}^K n_i)$ は $2 \times 10^5$ 以下である

2つの数列 $a_i$ と $a_j$ を選び、以下の操作が出来る $(i \neq j)$

$a_i$ と $a_j$ からそれぞれ1つずつ $a_{i,x},a_{j,y}$ を取り除く $(1 \le x\le n_i), (1 \le y \le n_j)$

操作後、数列 $a_i$ の総和と数列 $a_j$ の総和を等しくすることが可能か

可能な場合は $i,x$ と $j,y$ を出力する

考察

操作後の2つの数列の総和を等しくしたいので、どの数列からどの値を取り除いて数列の総和はどうなるのかをあらかじめ求めておく。(以下のようなペアを作っておく)
$(要素を取り除いた後の総和, 何番目の数列, 何番目の要素) = (sum, i, x)$

$(sum, i,x)$ のペアをソートする
あとは各ペアに対して $sum$ が同じで $i$ が異なるもう一つペアが存在するか二分探索
存在する場合はその2つのペアが解

ソースコード

Submission #38854484 - Codeforces

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

public class C {

    int K;
    int[] N;
    int[][] S;
    ArrayList<D> list;

    private class D implements Comparable<D> {
        long sum;
        int ij,xy;
        public D(long sum,int ij,int xy) {
            this.sum = sum;
            this.ij = ij;
            this.xy = xy;
        }

        public int compareTo(D other) {
            if (this.sum != other.sum) {
                return Long.compare(this.sum, other.sum);
            }

            if (this.ij != other.ij) {
                return Integer.compare(this.ij, other.ij);
            }
            return Integer.compare(this.xy, other.xy);
        }

        public String toString() {
            return "[sum=" + this.sum + " ij=" + this.ij + " xy=" + this.xy + "]";
        }
    }


    private void solve() {
        K = nextInt();
        N = new int[K];
        S = new int[K][];
        list = new ArrayList<>();

        for(int i = 0;i < K;i++) {
            N[i] = nextInt();
            S[i] = new int[N[i]];
            long sum = 0;
            for(int j = 0;j < N[i];j++) {
                S[i][j] = nextInt();
                sum += S[i][j];
            }

            for(int j = 0;j < N[i];j++) {
                long removedSum = sum - S[i][j];
                list.add(new D(removedSum, i + 1, j+1));
            }
        }

        Collections.sort(list);

        ArrayList<D> tmpList = new ArrayList<>();
        D pre = list.get(0);
        for(int i = 1;i < list.size();i++) {
            D next = list.get(i);

            if (!(pre.sum == next.sum && pre.ij == next.ij)) {
                tmpList.add(pre);
                pre = next;
            }
        }
        tmpList.add(pre);
        list = tmpList;

        for(int i = 0;i < list.size();i++) {
            D d1 = list.get(i);

            int low = i;
            int high = list.size();

            while(high - low > 1) {
                int mid = high + low >> 1;
                D d2 = list.get(mid);
                if (d1.compareTo(d2) <= 0) {
                    high = mid;
                } else {
                    low = mid;
                }
            }

            if (high != list.size()) {
                D d2 = list.get(high);
                if (d1.sum == d2.sum && d1.ij != d2.ij) {
                    out.println("YES");
                    out.println(d1.ij + " " + d1.xy);
                    out.println(d2.ij + " " + d2.xy);
                    return;
                }
            }
        }

        out.println("NO");
    }
}

D問題

問題

codeforces.com

数直線上に $N(1 \le N \le 2 \times 10^5)$ 個の点 $x_i(-10^9 \le x_i \le 10^9)$ が存在する
各点同士の距離が2の累乗である点集合を出来るだけ集合に含まれる点の数が多くなるように選びたい

点集合に含まれる点の数の最大値と点を出力する

考察

よく考えたら、4つ以上の点を集合に含めることが出来ないことが分かる

例として、3つの点X,Y,Zを考える $(X \lt Y \lt Z)$
点Xと点Yの距離を $2^a$
点Yと点Zの距離を $2^b$
とすると点Xと点Zの距離を $2^n$ の形にするには $2^a = 2^b$ である必要がある

ここで4つ目の点Wを加えるとする $(X \lt Y \lt Z \lt W)$
点Zと点Wの距離を $2^c$
上記の $2^a = 2^b$ を考えると $2^a = 2^b = 2^c$ から
点Xと点Wの距離は $2^a + 2^b + 2^c$ となり、2の累乗の形に出来ないので、3つまで点を見れば良いことが分かる

「距離」と「点X」を決め打ちして「点Xの位置-距離」または「点Xの位置+距離」に点が存在するならば
その点を集合に追加していく

ソースコード

Submission #38969303 - Codeforces

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

public class D {

    int N;
    ArrayList<Integer> x;

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

        Collections.sort(x);

        int[] ans = new int[3];
        int size = 0;
        for(int v : x) {
            for(int bit = 0;bit < 31;bit++) {

                int small = v - (1 << bit);
                int big = v + (1 << bit);

                int ind1 = Collections.binarySearch(x, small);
                int ind2 = Collections.binarySearch(x, big);

                if (ind1 >= 0 && ind2 >= 0 && size < 3) {
                    ans[0] = small;
                    ans[1] = v;
                    ans[2] = big;
                    size = 3;
                }

                if (ind1 >= 0 && ind2 < 0 && size < 2) {
                    ans[0] = small;
                    ans[1] = v;
                    ans[2] = -1;
                    size = 2;
                }

                if (ind1 < 0 && ind2 >= 0 && size < 2) {
                    ans[0] = v;
                    ans[1] = big;
                    ans[2] = -1;
                    size = 2;
                }
            }
        }

        if (size == 0) {
            out.println(1);
            out.println(x.get(0));
            return;
        }

        out.println(size);
        for(int i = 0;i < size;i++) {
            if (i != 0) {
                out.print(" ");
            }
            out.print(ans[i]);
        }
        out.println();

    }
}

E問題

問題

codeforces.com

整数 $N(1 \le N \le 10^9)$ が与えられる
$N$ の $i$ 桁目と $i+1$ 桁目を交換する操作(交換操作)が出来る(交換操作後に先頭から0が1文字以上続く整数にするような交換操作は出来ない)
整数 $N$ が25で割り切れる数になるように交換操作を繰り返した場合の交換操作回数の最小値を求めたい

25で割り切れる数に出来ない場合は-1を出力する

考察

$25$ で割り切れる数の下2桁に注目すると
$00,25,50,75$ の繰り返しになること気付くので、下2桁をその4パターンに絞る

まず、下2桁が $25$ になる場合について考える
交換操作回数を最小にしたいので、下1桁目から一番近い $5$ を持つ桁(下1桁目も含む)から $5$ を交換操作をしながら下1桁目に配置する
下2桁目も同様に $2$ を持つ一番近い桁(下1桁目は除く)から交換操作をしながら下2桁目に配置する
その後、先頭1桁目が $0$ の場合は $0$ ではない値を持つ桁から、先頭に値を交換操作を行いながら配置する

下2桁が $25$ になるような最小の交換操作回数は
$下1桁目を5にするための交換操作回数 + 下2桁目を2にするための交換操作回数 + 先頭1桁目を0以外にするための交換操作回数$

$00, 50, 75$ も同じように実際に交換操作を行いながら、交換操作回数の最小値を求める

ソースコード

Submission #39022664 - Codeforces

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

public class E {

    char[] N;

    private void swapFromLToR(int l,int r,char[] ch) {
        for(int k = l;k < r;k++) {
            char tmp = ch[k];
            ch[k] = ch[k+1];
            ch[k+1] = tmp;
        }
    }

    private void swapFromRToL(int l,int r,char[] ch) {
        for(int k = r;k > l;k--) {
            char tmp = ch[k];
            ch[k] = ch[k-1];
            ch[k-1] = tmp;
        }
    }

    private long toLong(char[] ch) {
        long ret = 0L;
        for(char c : ch) {
            ret *= 10;
            ret += c - '0';
        }
        return ret;
    }

    private int calc(char[] ch,char a,char b) {

        int ret = 0;

        int r = -1;
        for(int i = ch.length-1;i >= 0;i--) {
            if (ch[i] == b) {
                r = i;
                break;
            }
        }
        if (r == -1) {
            return Integer.MAX_VALUE;
        }
        swapFromLToR(r,ch.length-1 ,ch);
        ret += ch.length-1 - r;

        int l = -1;
        for(int i = ch.length-2;i >= 0;i--) {
            if (ch[i] == a) {
                l = i;
                break;
            }
        }
        if (l == -1) {
            return Integer.MAX_VALUE;
        }
        swapFromLToR(l, ch.length-2,ch);
        ret += ch.length-2 - l;

        if (ch[0] == '0') {
            int z = -1;
            for(int i = 1;i < ch.length;i++) {
                if (ch[i] != '0') {
                    z = i;
                    break;
                }
            }

            if (z == -1) {
                return Integer.MAX_VALUE;
            }

            swapFromRToL(z, 0, ch);
            ret += z;
        }

        long n = toLong(ch);
        if (n % 25 == 0) {
            return ret;
        }
        return Integer.MAX_VALUE;
    }

    private void solve() {
        N = next().toCharArray();

        int ans = calc(Arrays.copyOf(N,N.length),'2','5');
        ans = Math.min(ans,calc(Arrays.copyOf(N,N.length),'5', '0'));
        ans = Math.min(ans,calc(Arrays.copyOf(N,N.length),'7', '5'));
        ans = Math.min(ans,calc(Arrays.copyOf(N,N.length),'0', '0'));

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

F問題

問題

codeforces.com

数直線上でPolycarpは $x=0$ から $x=a(1 \le a \le \lceil \frac{n}{2} \rceil)$ に移動したい(左から右への移動のみ可能)
$n(1 \le n \le 2000)$ 個の雨が降っている区間 $[l_i,r_i](0 \le l_i \lt r_i \le a)$ が与えられ、(この区間同士は重ならない)
さらに $m(1 \le m \le 2000)$ 個の傘の位置 $x_i(0 \le x_i \le a)$ 、重さ $p_i(, 1 \le p_i \le 10^5)$ が与えられる
Polycarpは初めに $x = 0$ から出発する時は傘を持っていない

Polycarpは $x = 0$ から $x = a$ に移動する間、傘を拾ったり、捨てることができ、傘はいくつでも拾うことが出来る
Polycarpは雨で濡れたくないので、雨が降っている区間を移動している間は少なくとも1つ以上の傘を持っている必要がある

雨が降っていない区間では傘を持っている必要は無く、雨が降っている区間内で傘を交換出来る
1単位移動するごとに持っている傘の重さの総和の分だけ疲労が増加する
$x = 0$ から $x = a$ に移動する際、出来るだけ疲労が少ないようにしたいので、
疲労の最小値を求める

$x= 0$ から $x = a$ に移動が出来ない場合、-1を出力する

考察

$dp[i + 1][j] := x=iに移動する際に傘jを持って移動する最小の疲労の総和$
傘を持っていない状態を $j=M$ としてDPをする

基本的には $x=0,1,2,3,4...$ のように1単位ずつ移動することを考えると、複数の傘を同時に持つのは最適ではないことが分かり
どの傘を $x=i$ の時に持っていればよいかをさらに考えるとDPでまとめられるかという発想になりそう

実装に関しては最初メモ化再帰で実装していたがなぜかWAが取れず、結局forDPに直して通した

ソースコード

Submission #39193925 - Codeforces

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

public class F {
    private static final long INF = (long)1e17+7;
    int A,N,M;
    int[] U;
    long[] P;
    boolean[] R;
    long[][] dp;

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

        R = new boolean[A + 1];
        for(int i = 0;i < N;i++) {
            int l = nextInt();
            int r = nextInt();

            for(int j = l;j < r;j++) {
                R[j] = true;
            }
        }

        U = new int[A + 1];
        Arrays.fill(U, -1);
        P = new long[M];
        Arrays.fill(P, INF);
        for(int i = 0;i < M;i++) {
            int x = nextInt();
            P[i] = nextInt();
            if (U[x] == -1 || P[U[x]] >= P[i]) {
                U[x] = i;
            }
        }

        dp = new long[A + 1][M + 1];
        for(int i = 0;i < A + 1;i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][M] = 0;
        for(int i = 0;i < A;i++) {
            for(int j = 0;j < M + 1;j++) {
                if (dp[i][j] == INF) {
                    continue;
                }
                if (!R[i]) {
                    dp[i + 1][M] = Math.min(dp[i + 1][M],dp[i][j]);
                }

                if (j < M) {
                    dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + P[j]);
                }

                if (U[i] != -1) {
                    dp[i + 1][U[i]] = Math.min(dp[i + 1][U[i]], dp[i][j] + P[U[i]]);
                }
            }
        }

        long ans = INF;
        for(int i = 0;i < M + 1;i++) {
            ans = Math.min(ans, dp[A][i]);
        }

        if (ans == INF) {
            out.println(-1);
        } else {
            out.println(ans);
        }
    }
}