LoginSignup
0
0

More than 1 year has passed since last update.

@pochama(ぺんぎん)

JavaでABC231(C問題まで)

Posted at

　先日行われたパナソニックプログラミングコンテスト2021(ABC231)に参加しました。
C問題まで解くことができたので、方針とコードを投稿していきたいと思います。

A問題(Water Pressure)

方針

　入力値(Dとする)を100で割ると答えが出ます。計算はdouble型で実施することに注意しました。

コード

　コードではBigDecimal型にして、誤差を減らしていきます。
標準入力と出力に関しては下記ページを参考にしています。

Main.java
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;

public class Main {
    public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        double d = fs.nextDouble();
        BigDecimal ans = new BigDecimal(d / 100.0);

        out.println(ans.doubleValue());


        out.flush();
        fs.close();
    }
}


class FastScanner{
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}

    public void close() {
        try {
            in.close();
        } catch (IOException e) {
            // TODO: handle exception
        }
    }
}

B問題(Election)

方針

　Keyの値を候補者名、Valueの値を獲得票数のMapでデータを管理します。
N回for文でループして、Keyの値に候補者の名前が存在していればValueの値を+1して更新する。存在しなければ、KeyとValueの値を新規に登録する。
for文のループが終了した後に、Map内でValueが最大値になるKeyを取り出して答えとします。

コード

HashMapの最大値を取得する方法は下記サイトを参考にしています。

Main.java
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.NoSuchElementException;

public class Main {
    public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int n = fs.nextInt();

        Map<String, Integer> map = new HashMap<>();

        for(int i = 0;i < n;i++) {
            String name = fs.next();

            if(map.containsKey(name)) {
                map.replace(name, map.get(name) + 1);
            }else {
                map.put(name,1);
            }
        }

        String anString = null;
        Integer maxValue = 0;

        for(Map.Entry<String, Integer> entry: map.entrySet()) {
            if(entry.getValue() > maxValue) {
                anString = entry.getKey();
                maxValue = entry.getValue();
            }
        }

        out.println(anString);


        out.flush();
        fs.close();
    }
}


class FastScanner{
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}

    public void close() {
        try {
            in.close();
        } catch (IOException e) {
            // TODO: handle exception
        }
    }
}

for文を2重ループさせて、実装した方が簡単だったかもしれません💦

C問題(Counting 2)

方針

　生徒の身長を配列で管理して、昇順ソートします。その後、各条件に関して二分探索を行うことによって条件を満たす最小のインデックスを求めることができるので、生徒の総数からその最小値を引いて答えを出すことができます。
　二分探索について解説しているサイトはたくさんありますので、自分が参考にしたサイトを載せておきます。

コード

　実際にコードに落とし込むときには、「めぐる式二分探索」を参考にして実装しています。
この二分探索はバグを減らせることと「条件を満たす最小のインデックス値」を出すことができるのでとても重宝しています。

名前の由来は以下のツイートです。

Main.java
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;

public class Main {
    public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        //生徒の人数
        int n = fs.nextInt();
        //操作の回数
        long q = fs.nextLong();

        //生徒の身長
        long[] a = new long[n];

        for(int i = 0;i < n;i++) {
            a[i] = fs.nextLong();
        }

        //昇順ソート
        Arrays.sort(a);

        for(int i = 0;i < q;i++) {
            //判定となる身長
            int x = fs.nextInt();
            //x以上を満たすindexの最小値がでる。
            int minIndex = binarySerach(a, x, n);
                        //総数から最小のindex値を引く
            out.println(n - minIndex);

        }
        out.flush();
        fs.close();
    }

    /**
     * 二分探索
     * @param a 身長の配列
     * @param x 身長の分岐点
     * @param n 要素数
     */
    public static int binarySerach(long[] a,int x,int n) {
        int ok = n;
        int ng = -1;

        //okとngの要素が必ず隣合う
        while(Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            if(a[mid] >= x) {
                ok = mid;
            }else {
                ng = mid;
            }
        }

        return ok;

    }

}


class FastScanner{
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}

    public void close() {
        try {
            in.close();
        } catch (IOException e) {
            // TODO: handle exception
        }
    }
}

今回は3完でした。
レーティングはマイコンテスト毎に伸びているので、この調子で頑張っていきたいと思います。

参考文献

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0