山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

Codeforces Round #501 (Div. 3) に参加した感想

問題

http://codeforces.com/contest/1015

結果はA問題まで解くことができました。多分、今回の区分が一番下だったと思うんですが、僕には難しい問題でしたね。

A. Points in Segments

数直線上で考えると分かりやすいと思います。

区間 [ 1, m] に対して n 個の区間を塗りつぶしていきます。そして、塗りつぶされなかった自然数の数を数えて出力します。

アルゴリズムとしてはいもす法が考えられるんですが、別に使わなくても時間内に間に合うと思ったので、愚直に塗りつぶしていきました。

コード
import java.util.ArrayList;
import java.util.Scanner;

public class ProblemA {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int []l = new int[n];
        int []r = new int[n];
        for(int i = 0; i < n; i++) {
            l[i] = scan.nextInt();
            r[i] = scan.nextInt();
        }
        scan.close();
        int []num = new int[m +1];
        for(int i = 0; i < n; i++) {
            for(int k = l[i]; k <= r[i]; k++) {
                num[k]++;
            }
        }

        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i = 1; i <= m; i++) {
            if(num[i] == 0) {
                list.add(i);
            }
        }
        System.out.println(list.size());
        for(int i = 0; i < list.size() - 1; i++) {
            System.out.print(list.get(i) + " ");
        }
        if(list.size() == 0) {
            System.exit(0);
        }
        System.out.println(list.get(list.size() - 1));
    }
}

B. Obtaining the String

実装系の問題でしょうか。最初の文字列から揃えていきます。文字の種類とその数が一致しなければ、文字の入れ替えによって文字列が一致することはありません。

コード
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class ProblemB {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String s = scan.next();
        String t = scan.next();
        scan.close();
        String []a1 = s.split("");
        String []a2 = t.split("");
        Arrays.sort(a1);
        Arrays.sort(a2);
        for(int i = 0; i < n; i++) {
            if(!a1[i].equals(a2[i])) {
                System.out.println(-1);
                System.exit(0);
            }
        }
        a1 = s.split("");
        a2 = t.split("");
        StringBuilder sb = new StringBuilder(s);
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i = 0; i < n; i++) {
            String k1 = sb.substring(i, i + 1);
            String k2 = t.substring(i, i + 1);
            if(k1.equals(k2)) {
                continue;
            }
            for(int j = i + 1; j < n; j++) {
                k1 = sb.substring(j, j + 1);
                if(k1.equals(k2)) {
                    //System.out.println(k1);
                    sb.insert(i, k1);
                    sb.deleteCharAt(j + 1);
                    //System.out.println(sb);
                    for(int k = j - 1; k >= i; k --) {
                        list.add(k + 1);
                    }
                    break;
                }

            }

        }
        //System.out.println(sb);

        System.out.println(list.size());
        for(int i = 0; i < list.size() - 1; i++) {
            System.out.print(list.get(i) + " ");
        }
        if(list.size() == 0) {
            System.exit(0);
        }
        System.out.println(list.get(list.size() - 1));
    }
    static void swap(String[] s, int i, int j) {
        String t = s[i];
        s[i] = s[j];
        s[j] = t;
    }
}

C. Songs Compression

問題自体はそこまで難しくありませんが、時間制限が厳しかったです。

解法としては、 a の総和に対して、 c = a - b としたものを降順に並べて、総和から引いていきます。

Arrays.sortを使うと制限時間が厳しかったです。なので、優先順位付きキューを使います。優先順位付きキューはデフォルトでは昇順なので、これを降順に格納するようにします。

java - Change priorityQueue to max priorityqueue - Stack Overflow

コード
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class ProblemC2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long m = scan.nextLong();
        //int []a = new int[n];
        //int []b = new int[n];
        long sum1 = 0;
        long sum2 = 0;
        //long []c = new long[n];

        Queue<Long> queue = new PriorityQueue<Long>(n, Collections.reverseOrder());
        for(int i = 0; i < n; i++) {
            long a = scan.nextLong();
            long b = scan.nextLong();
            long t = a - b;
            queue.add(t);
            //c[i] = a - b;
            sum1 += a;
            sum2 += b;
        }
        scan.close();
        //int []c = new int[n];


        //Arrays.sort(c);
        if(sum1 <= m) {
            System.out.println(0);
            System.exit(0);
        }
        if(sum2 > m) {
            System.out.println(-1);
            System.exit(0);
        }

        int cnt = 1;

        while(queue.size() != 0) {
            long t = queue.poll();
            sum1 -= t;
            if(sum1 <= m) {
                break;
            }
            cnt ++;
        }
        System.out.println(cnt);
    }
}

感想

問題CですがC++だとソートしても大丈夫なんでしょうか。Javaで提出されたコードを見るとArrays.sortを使っているものもあったので、僕のコードが悪かったんだとおもいます。

言語による有利不利はあると思いますが、Javaで通らないということは無いと思います。2番目に多い言語だった気がします。でも、その差を知識で吸収していくのは大変ですね。