Abstruct

第一回アルゴリズム実技検定過去問 - AtCoder の問題AからHまでをJavaで解いてみました。（問題はAからOまでありますが。。。）

また、より少ないコード量で、、というよりも、そこまで時間はかけずに、私なりに素直な考え方のコードで解きました。(少し冗長なところはありますが、ご了承ください。)

1. A 2倍チェック
- 1.1. A 2倍チェックの解答のソースコード
1. B 増減管理
- 2.1. B 増減管理の解答のソースコード
1. C 3番目
- 3.1. C 3番目の解答のソースコード
1. D 重複検査
- 4.1. D 重複検査の解答のソースコード
1. E SNSのログ
- 5.1. E SNSのログの解答のソースコード
1. F DoubleCamelCase Sort
- 6.1. F DoubleCamelCase Sortの解答のソースコード
1. G 組分け
- 7.1. G 組分けの解答のソースコード
1. H まとめ売り
- 8.1. H まとめ売りの解答のソースコード

1. A 2倍チェック

問題のURL : https://atcoder.jp/contests/past201912-open/tasks/past201912_a

1.1. A 2倍チェックの解答のソースコード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


package com.example.coding.atcoder.make_20210315;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.regex.Pattern;

// クラス名はMainに変更して、
// import文も含めて、
// atcoderのソース画面に貼り付ける。
public class A_2倍チェック {
    public static void main(String[] args) {

        String input = "";

        // 入力データの取得
        try (var reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
             var in = new BufferedReader(reader)) {
            String line;

            for (var i = 0; (line = in.readLine()) != null; i++) {
                if (i == 0) {
                    input = line;
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }

        // Input Check
        var p = Pattern.compile("^[0-9]+$");
        var m = p.matcher(input);

        // 数値の場合
        if(m.find()){
            var num = Integer.parseInt(input);
            System.out.println(num * 2);
        }
        // 数値ではなかった場合
        else{
            System.out.println("error");
        }
    }
}

2. B 増減管理

問題のURL : https://atcoder.jp/contests/past201912-open/tasks/past201912_b

2.1. B 増減管理の解答のソースコード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


package com.example.coding.atcoder.make_20210315;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;

// クラス名はMainに変更して、
// import文も含めて、
// atcoderのソース画面に貼り付ける。
public class B_増減管理 {
    public static void main(String[] args) {

        var N = 0;
        var priceList = new ArrayList<Integer>();

        // 入力データの取得
        try (var reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
             var in = new BufferedReader(reader)) {
            String line;

            for (var i = 0; (line = in.readLine()) != null; i++) {
                if(i == 0){
                    N = 0;
                }else{
                    priceList.add(Integer.parseInt(line));
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }

        // 1つ目の要素の取得
        Integer beforePrice = priceList.get(0);

        // 増減チェック
        for(var i = 1; i < N; i++){
            var difference = priceList.get(i) - beforePrice;
            if(difference == 0){
                System.out.println("stay");
            }else if(difference > 0){
                System.out.println("up " + difference);
            }else{
                System.out.println("down " + difference * -1);
            }
            // 前回の値段の更新
            beforePrice = priceList.get(i);
        }
    }
}

3. C 3番目

問題のURL : https://atcoder.jp/contests/past201912-open/tasks/past201912_c

3.1. C 3番目の解答のソースコード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


package com.example.coding.atcoder.make_20210315;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Collections;

// クラス名はMainに変更して、
// import文も含めて、
// atcoderのソース画面に貼り付ける。
public class C_3番目 {
    public static void main(String[] args) {

        var inputData = "";

        // 入力データの取得
        try (var reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
             var in = new BufferedReader(reader)) {
            String line;

            for (var i = 0; (line = in.readLine()) != null; i++) {
                if(i == 0){
                    inputData = line;
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }

        // InputDataを分割して、昇順ソートする。
        var integerList = new ArrayList<Integer>();
        for(var data : inputData.split(" ")){
            integerList.add(Integer.parseInt(data));
        }
        Collections.sort(integerList);
        Collections.reverse(integerList);

        //3番目のデータを出力する。
        System.out.println(integerList.get(2));
    }
}

4. D 重複検査

問題のURL : https://atcoder.jp/contests/past201912-open/tasks/past201912_d

4.1. D 重複検査の解答のソースコード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63


package com.example.coding.atcoder.make_20210315;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

// クラス名はMainに変更して、
// import文も含めて、
// atcoderのソース画面に貼り付ける。
public class D_重複検査{
    public static void main(String[] args) {

        var N = 0;
        var numList = new ArrayList<Integer>();
        var checkMap = new HashMap<Integer, Integer>();


        // 入力データの取得
        try (var reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
             var in = new BufferedReader(reader)) {
            String line;

            for (var i = 0; (line = in.readLine()) != null; i++) {
                if(i == 0){
                    N = Integer.parseInt(line);
                }else{
                    numList.add(Integer.parseInt(line));
                    checkMap.put(i, 0);
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }

        // 入力で与えられたnumListをソートする。
        Collections.sort(numList);

        for(var i = 0; i < N; i++){
            checkMap.put(numList.get(i), checkMap.get(numList.get(i)) + 1);
        }

        var twiceExist = 0;
        var nonExist = 0;
        for(var i = 1; i <= N; i++){
            if(checkMap.get(i) == 0){
                nonExist = i;
            }
            if(checkMap.get(i) == 2){
                twiceExist = i;
            }
        }

        if(twiceExist == 0 && nonExist == 0){
            System.out.println("Correct");
        }else{
            System.out.println(twiceExist + " " + nonExist);
        }
    }
}

5. E SNSのログ

問題のURL : https://atcoder.jp/contests/past201912-open/tasks/past201912_e

5.1. E SNSのログの解答のソースコード

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133


package com.example.coding.atcoder.make_20210315;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;

// クラス名はMainに変更して、
// import文も含めて、
// atcoderのソース画面に貼り付ける。
public class E_SNSのログ {

    private static final String FOLLOW_CHAR = "Y";
    private static final String NOT_FOLLOW_CHAR = "N";
    private static final String SPLIT_CHAR = " ";

    public static void main(String[] args) {

        var N = 0;
        var Q = 0;
        String[][] followArray;
        var followHistory = new ArrayList<String>();

        // 入力データの取得
        try (var reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
             var in = new BufferedReader(reader)) {
            String line;

            for (var i = 0; (line = in.readLine()) != null; i++) {
                if(i == 0){
                    var data = line.split(SPLIT_CHAR);
                    N = Integer.parseInt(data[0]);
                    Q = Integer.parseInt(data[1]);
                }else{
                    followHistory.add(line);
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }

        // フォロー配列の初期化
        followArray = new String[N][N];
        for(var i = 0; i < N; i++){
            for(var j = 0; j < N; j++){
                followArray[i][j] = NOT_FOLLOW_CHAR;
            }
        }

        // フォロー履歴の解析
        for(var history : followHistory){
            var elements = history.split(SPLIT_CHAR);
            var option = Integer.parseInt(elements[0]);
            switch (option){
                case 1:
                    follow(followArray, Integer.parseInt(elements[1])-1, Integer.parseInt(elements[2])-1);
                    break;
                case 2:
                    followBack(followArray, N, Integer.parseInt(elements[1])-1);
                    break;
                case 3:
                    followFollow(followArray, N, Integer.parseInt(elements[1])-1);
                    break;
            }
        }

        // 自分自身へのフォローを解除する
        for(var i = 0; i < N; i++){
            followArray[i][i] = NOT_FOLLOW_CHAR;
        }

        // フォロー配列の出力
        for(var i = 0; i < N; i++){
            for(var j = 0; j < N; j++){
                System.out.print(followArray[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * x が y をフォローする。
     * @param followArray フォロー配列
     * @param x メンバ
     * @param y メンバ
     */
    private static void follow(String[][] followArray, int x, int y){
        followArray[x][y] = FOLLOW_CHAR;
    }

    /**
     * x をフォローしているメンバ集合をTとする。
     * x はTのメンバすべてをフォローする。
     * @param followArray フォロー配列
     * @param N フォロー配列の1辺の長さ
     * @param x メンバ
     */
    private static void followBack(String[][] followArray, int N, int x){
        var T = new ArrayList<Integer>();
        for(var i = 0; i < N; i++){
            if(followArray[i][x].equals(FOLLOW_CHAR)){
                T.add(i);
            }
        }
        for(var member : T){
            followArray[x][member] = FOLLOW_CHAR;
        }
    }

    /**
     * x が フォローしているメンバ集合をTとする。
     * Tのメンバがフォローしているメンバを、xがフォローする。
     * @param followArray フォロー配列
     * @param N フォロー配列の1辺の長さ
     * @param x メンバ
     */
    private static void followFollow(String[][] followArray, int N, int x){
        var T = new ArrayList<Integer>();
        for(var member = 0; member < N; member++){
            if(followArray[x][member].equals(FOLLOW_CHAR)){
                T.add(member);
            }
        }
        for(var member : T){
            for(var i = 0; i < N; i++){
                if(followArray[member][i].equals(FOLLOW_CHAR)){
                    followArray[x][i] = FOLLOW_CHAR;
                }
            }
        }
    }
}

6. F DoubleCamelCase Sort

問題のURL : https://atcoder.jp/contests/past201912-open/tasks/past201912_f

6.1. F DoubleCamelCase Sortの解答のソースコード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


package com.example.coding.atcoder.make_20210315;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// クラス名はMainに変更して、
// import文も含めて、
// atcoderのソース画面に貼り付ける。
public class F_DoubleCamelCaseSort {

    public static void main(String[] args) {

        var inputData = "";

        // 入力データの取得
        try (var reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
             var in = new BufferedReader(reader)) {
            String line;

            for (var i = 0; (line = in.readLine()) != null; i++) {
                inputData = line;
            }
        } catch (IOException e) {
            e.printStackTrace();
        }

        // 入力で与えられたinputDataから単語を切り出す。
        var inputWordList = splitInputData(inputData);

        // 大文字小文字を区別せずにソートする。
        Collections.sort(inputWordList, (s1, s2) -> s1.compareToIgnoreCase(s2));

        // 出力する。
        for(var inputWord : inputWordList){
            System.out.print(inputWord);
        }
    }
    private static List<String> splitInputData(String inputData){
        var inputDataArray = inputData.split("");
        var startFlag = false;
        var sb = new StringBuilder();
        var wordList = new ArrayList<String>();
        for(var element : inputDataArray){

            sb.append(element);
            // 大文字である場合
            if(Character.isUpperCase(element.toCharArray()[0])){

                if(!startFlag){// 開始時点の大文字
                    startFlag = true;
                }else{ // 終了時点の大文字
                    startFlag = false;
                    // 終了時点の大文字であるため、リストに単語を追加する。
                    wordList.add(sb.toString());
                    sb = new StringBuilder();
                }
            }
        }
        return wordList;
    }
}

7. G 組分け

問題のURL : https://atcoder.jp/contests/past201912-open/tasks/past201912_g

7.1. G 組分けの解答のソースコード

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114


package com.example.coding.atcoder.make_20210315;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;

// クラス名はMainに変更して、
// import文も含めて、
// atcoderのソース画面に貼り付ける。
public class G_組分け {
    public static void main(String[] args) {

        var N = 0;
        var inputData = new ArrayList<String>();

        // 入力データの取得
        try (var reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
             var in = new BufferedReader(reader)) {
            String line;

            for (var i = 0; (line = in.readLine()) != null; i++) {
                if(i == 0){
                    N = Integer.parseInt(line);
                }else{
                    inputData.add(line);
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }

        // 幸福度Mapの作成
        var personRelation = new Integer[N][N];

        // 幸福度Mapの初期化
        for(var i = 0; i < inputData.size(); i++){
            var relation = inputData.get(i).split(" ");
            var j = i+1;
            for(var ele : relation){
                personRelation[i][j] = Integer.parseInt(ele);
                personRelation[j][i] = personRelation[i][j];
                j++;
            }
        }

        // N<=10 であるため、全通りのグループ分けを考える。
        var pow3 = 1;
        for(var i = 0; i<N; i++){
            pow3 *= 3;
        }
        // Maxスコアの初期化
        var maxScore = -100000000;
        for(var i = 0; i < pow3; i++){
            // groupDivide[i] が i番目の人のグループ(0,1,2)を表す
            var groupDivide = new Integer[N];
            for(int iDash = i, j = 0; j < N; j++){
                groupDivide[j] = iDash % 3;
                iDash /= 3;
            }
            var score = calcScore(personRelation, groupDivide, N);
            if(maxScore < score){
                maxScore = score;
            }
        }
        System.out.println(maxScore);
    }
    // スコア計算
    private static int calcScore(Integer[][] personRelation, Integer[] groupDivide, int N){
        var group0 = new ArrayList<Integer>();
        var group1 = new ArrayList<Integer>();
        var group2 = new ArrayList<Integer>();
        for(var i = 0; i < N; i++){
            switch (groupDivide[i]){
                case 0:
                    group0.add(i);
                    break;
                case 1:
                    group1.add(i);
                    break;
                case 2:
                    group2.add(i);
                    break;
            }
        }
        var score = 0;
        // Group0の計算
        for(var member1: group0){
            for(var member2: group0) {
                if (member1 < member2) {
                    score += personRelation[member1][member2];
                }
            }
        }
        // Group1の計算
        for(var member1: group1){
            for(var member2: group1) {
                if (member1 < member2) {
                    score += personRelation[member1][member2];
                }
            }
        }
        // Group2の計算
        for(var member1: group2){
            for(var member2: group2) {
                if (member1 < member2) {
                    score += personRelation[member1][member2];
                }
            }
        }
        return score;
    }
}

8. H まとめ売り

問題のURL : https://atcoder.jp/contests/past201912-open/tasks/past201912_h

8.1. H まとめ売りの解答のソースコード

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162


package com.example.coding.atcoder.make_20210315;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

// クラス名はMainに変更して、
// import文も含めて、
// atcoderのソース画面に貼り付ける。
public class H_まとめ売り {
    private static Map<Integer, Integer> gCardMap = new HashMap<>();
    private static int gOffSet = 0;
    private static int gOddOffSet = 0;
    private static int gMin = Integer.MAX_VALUE;
    private static int gOddMin = Integer.MAX_VALUE;
    private static int gOddNum = 0;

    public static void main(String[] args) {
        var N = 0;
        var Q = 0;
        var queryList = new ArrayList<String>();

        // 入力データの取得
        try (var reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
             var in = new BufferedReader(reader)) {
            String line;

            for (var i = 0; (line = in.readLine()) != null; i++) {
                if(i == 0){
                    N = Integer.parseInt(line);
                }else if(i == 1){
                    var cardString = line.split(" ");
                    for(var j = 0; j < cardString.length; j++){
                        // カード番号にするため、i + 1 としている。
                        var num = Integer.parseInt(cardString[j]);
                        gCardMap.put(j+1, num);
                        if((j+1) % 2 == 1){
                            gOddNum++;
                        }
                    }
                }else if(i == 2){
                    Q = Integer.parseInt(line);
                }else{
                    queryList.add(line);
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }

        // 入力で与えられたnumListをソートする。
        long sumSoldCardNum = 0;
        minCheck(N);
        for(var query : queryList){
            var queryArray = query.split(" ");
            var option = Integer.parseInt(queryArray[0]);
            switch (option){
                case 1:
                    sumSoldCardNum += option1Query(Integer.parseInt(queryArray[1]), Integer.parseInt(queryArray[2]));
                    break;
                case 2:
                    sumSoldCardNum += option2Query(Integer.parseInt(queryArray[1]));
                    break;
                case 3:
                    sumSoldCardNum += option3Query(N, Integer.parseInt(queryArray[1]));
                    break;
            }
        }
        System.out.println(sumSoldCardNum);
    }

    /**
     * Option 1の場合の処理
     * 単品販売：カードxをa枚販売する。ただし、在庫が足りない場合は何もしない。1 x a という形式で与えられる。
     * @param x 売るカードの種類
     * @param a 売るカードの枚数
     * @return 売れた枚数
     */
    private static int option1Query(int x, int a){
        if(x % 2 == 1){ // 奇数の場合
            if(gCardMap.get(x) - gOffSet - gOddOffSet >= a){
                // カード枚数の更新
                gCardMap.put(x, gCardMap.get(x) - a);
                if(gOddMin > gCardMap.get(x) - gOffSet - gOddOffSet){
                    gOddMin = gCardMap.get(x) - gOffSet - gOddOffSet;
                    if(gMin > gOddMin){
                        gMin = gOddMin;
                    }
                }
                return a;
            } else{
                return 0;
            }
        }else{ // 偶数の場合
            if(gCardMap.get(x) - gOffSet >= a){
                // カード枚数の更新
                gCardMap.put(x, gCardMap.get(x) - a);
                if(gMin > gCardMap.get(x) - gOffSet){
                    gMin = gCardMap.get(x) - gOffSet;
                }
                return a;
            } else{
                return 0;
            }
        }
    }

    /**
     * Option 2の場合の処理
     * セット販売：番号が奇数であるカードをそれぞれa枚ずつ販売する。ただし、一種類でも在庫が足りない場合は何もしない。2 a という形式で与えられる。
     * @param a 各カードの売却数
     * @return
     */
    private static int option2Query(int a){
        if(gOddMin >= a){
            gOddOffSet += a;
            gOddMin -= a;
            if(gMin > gOddMin) {
                gMin = gOddMin;
            }
            return a * gOddNum;
        }
        return 0;
    }
    /**
     * Option 3の場合の処理
     * 全種類販売：カードを全種類a枚ずつ販売する。ただし、一種類でも在庫が足りない場合は何もしない。3 a という形式で与えられる。
     * @param N カードの種類数
     * @param a 各カードの売却数
     * @return
     */
    private static int option3Query(int N, int a) {
        if(gMin >= a){
            gOffSet += a;
            gMin -= a;
            gOddMin -= a;
            return a * N;
        }
        return 0;
    }

    /**
     * 全カードの最小枚数のチェック
     * @param N カードの種類数
     */
    private static void minCheck(int N){
        for(var i = 1; i <= N; i++){
            if( i % 2 == 1){
                if(gOddMin > gCardMap.get(i)){
                    gOddMin = gCardMap.get(i);
                }
            }
            if(gMin > gCardMap.get(i)){
                gMin = gCardMap.get(i);
            }
        }
    }
}