ABC138振り返り

AtCoder

昨日のABC138を振り返る。

A問題

これはif文がわかれば解ける問題なので、詳細は書かない。

        if (n < 3200) {
            System.out.println("red");
        } else {
            System.out.println(s);
        }

B問題

逆数ってなんだったっけ・・？と一瞬なったものの、問題文にあった式に従ってfor文で回せば通った。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String ns = sc.nextLine();
        int n = Integer.parseInt(ns);
        
        String inputs = sc.nextLine();
        String[] input = inputs.split(" ");
        
        double sum = 0;
        for (int i = 0; i < input.length; i++) {
            sum += 1 / Double.parseDouble(input[i]);
        }
        
        System.out.println(1 / sum);
    }
}

C問題

問題が少し複雑になってきた。 2個選んで、半分にして、それを順次繰り返していき、最大値を得るってことは、順々に小さいもの2つを選択していくのがいいので、何はともあれまずはソート。
で、どう書こうと思案したところ、「繰り返す」「要素が一つになれば終了」「処理対象はだんだん小さくなっていく（配列の長さが1ずつ減っていく）」という観点から再帰を思いついた。

ただ、PDFの解説を読んだところ、さっぱりわからん状態だった・・。

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

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String ns = sc.nextLine();
        int n = Integer.parseInt(ns);
        
        String inputs = sc.nextLine();
        String[] input = inputs.split(" ");
        
        double[] nums = new double[input.length];
        for (int i = 0; i < input.length; i++) {
            nums[i] = Integer.parseInt(input[i]);
        }
        //まずはソートする
        Arrays.sort(nums);
        
        double result = makeResult(nums);
        System.out.println(result);
        
    }
    
    //再帰処理を行う
    private static double makeResult(double[] nums) {
        //配列の長さが1になったら終了
        if (nums.length == 1) {
            return nums[0];
        }
        //新しい配列は処理対象の配列より要素数が一つ減る。
        double[] newNums = new double[nums.length - 1];
        //新しい要素の1番目は処理対象配列の要素の先頭2つを足して割ったものにする。
        newNums[0] = (nums[0] + nums[1]) / 2;
        //あとは配列の要素をコピーすればいいはず
        for (int i = 1; i < newNums.length; i++) {
            newNums[i] = nums[i + 1];
        }
        return makeResult(newNums);
    }
}

D問題

アルゴリズム的には正しかったぽいけど、TLEが出てしまったので、計算量的にだめ。

私の考え方としてはとりあえずNodeクラスを作って、各NodeにさらにListで子要素を持たせる風にした。 これだと確かにNQの計算量（解説より）になってしまうよね・・。 つーか解説読んでもよくわからん。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String ns = sc.nextLine();
        String[] h = ns.split(" ");
        List<Node> list = new ArrayList<>();
        list.add(new Node(0));
        int N = Integer.parseInt(h[0]);
        int Q = Integer.parseInt(h[1]);
        for (int i = 1; i <= N; i++) {
            list.add(new Node(i));
        }
        
        //ノードの連結部分の処理
        for (int i = 0; i < N - 1; i++) {
            String in = sc.nextLine();
            String[] inputs = in.split(" ");
            int a = Integer.parseInt(inputs[0]);
            int b = Integer.parseInt(inputs[1]);
            list.get(a).addChild(list.get(b));
        }
        
        for (int i = 1; i <= Q; i++) {
            String input = sc.nextLine();
            String[] inputs = input.split(" ");
            int nodeId = Integer.parseInt(inputs[0]);
            int addCount = Integer.parseInt(inputs[1]);
            Node node = list.get(nodeId);
            node.addCount(addCount);
        }
        
        list.remove(0);
        String result = list.stream().map(n -> String.valueOf(n.count)).collect(Collectors.joining(" "));
        System.out.println(result);
    }
    
    static class Node {
        int id;
        long count;
        List<Node> children = new ArrayList<Main.Node>();;
        
        Node(int id) {
            this.id = id;
            this.count = 0;
        }
        
        public void addChild(Node node) {
            children.add(node);
        }
        
        public void addCount(long count) {
            this.count += count;
            for (Node node : this.children) {
                node.addCount(count);
            }
        }
        
        @Override
        public String toString() {
            return String.valueOf(this.id) + this.count;
        }
    }
}