Codeforces Round #501 (Div. 3) に参加した感想 - ヤマカサのプログラミング勉強日記

問題

結果は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番目に多い言語だった気がします。でも、その差を知識で吸収していくのは大変ですね。