KEYENCE Programming Contest 2019 A-C解説

A - Beginning

問題

A - Beginning

解説

並べ替えて1974にできるか判定するということは、順番は関係ないということなので、1,4,7,9が1つづつ含まれていればいいということになります。 それをそのまま実装してもいいですし、ソートして1,4,7,9になるかを判定するという実装でもいいかもしれません。

ソートを使う方のコード例です

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = {sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt()};
        Arrays.sort(arr);
        int[] ok = {1,4,7,9};
        System.out.println(Arrays.equals(arr, ok) ? "YES" : "NO");
    }
}

B - KEYENCE String

問題

B - KEYENCE String

解説

キーエンス型文字列の定義は、連続した部分文字列(空でも良い)を1度だけ取り除くことで keyenceになるかです。

この定義から、Sがキーエンス型文字列の時、Sがどんな状態かは3通りあります。

1. 先頭がkeyence
2. 末尾がkeyence
3. 先頭がkeyenceを前半と後半に分けた前半で、末尾が後半

最後のはわかりにくいと思います。例を出すと、keyenceをkeyとenceにわけたとき、keyhogehogeenceがキーエンス型文字列という感じです。

これをどう実装するかというと、keyecneをfor文で回してk+eyence, ke+yence, key+....という風に切っていき、前半が先頭にあり、後半が末尾にあるかを判定すればいいです。

コード例です。 substringメソッドでok("keyence")を切断して、startWithとendWithメソッドで判定しています。 先頭がkeyecne、末尾がkeyenceの場合はそれぞれ、 keyence+"", ""+keyenceという切り方ともいえるので、キーエンス型文字列の全パターンが列挙できています。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String ok = "keyence";
        String s = sc.next();
        for (int i = 0; i < ok.length(); i++) {
            if(s.startsWith(ok.substring(0,i)) && s.endsWith(ok.substring(i))) {
                System.out.println("YES");
                return;
            }
        }
        System.out.println("NO");
    }
}

C - Exam and Wizard

問題

C - Exam and Wizard

解説

総和が同じにならないといけないということから、準備が足りない試験に準備が足りている試験から、その余った分を配るという問題です。そして、変更した場所ができるだけ少なくないといけません。これを考えていきます。

• 準備時間も必要な時間もちょうどの試験の場合(a[i]==b[i])、なにも変更する必要はありません。変更回数に影響がありません。
• 準備が足りない試験(a[i] < b[i])は必ず変更しなければいけません。配られる側は必ず変更されます。
• 準備が足りて、余りある試験(a[i] > b[i])は、準備が足りていない試験があるなら余った準備時間(a[i] - b[i])を配ります。配る側は配らない場合もあるので、変更しない場合もあります。

変更回数を減らすには、最後の、余った分を配る側をできるだけ少なくすればいいということになります。 すると、沢山余っている試験から順番に足りない部分に余った分を配ればいいということがわかるので、実装します。

実装上の注意

配られる側は、必ず変更されるので、全部でどれだけ足りていないかがわかればよく、個別にどれだけ足りないかはいりません。

配る側は、変更されるかわからないので、個別にどれだけ配れるかをlistで持っておく必要があります。

コード例

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //input
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        for (int i = 0; i < n; i++) b[i] = sc.nextInt();

        //余っている準備時間を試験ごとにわけてソートしたもの
        PriorityQueue<Integer> surplus = new PriorityQueue<>(Comparator.reverseOrder());
        //変更回数
        int count = 0;
        long shortage = 0L;//不足している準備時間

        for (int i = 0; i < n; i++) {
            if (a[i] == b[i]) continue;//ちょうどの場合
            if (a[i] > b[i]) {//余っている場合
                surplus.add(a[i] - b[i]);
            } else {//足りない場合
                shortage += (b[i] - a[i]);
                count++;
            }
        }
        while (shortage > 0) {
            Integer i = surplus.poll();
            if (i == null) {//足りない部分があるのに、もう配るものが無い場合、無理
                System.out.println(-1);
                return;
            }
            shortage -= i;
            count++;
        }

        System.out.println(count);
    }
}