LoginSignup
0
0

More than 1 year has passed since last update.

@pochama(ぺんぎん)

JavaでABC232(C問題まで)

Last updated at Posted at 2021-12-21

ABC232の問題を解いたので、解き方とコードを投稿します。
使用言語はJavaです。

A問題(QQ solver)

方針

文字列の先頭と末尾の文字を取り出して、それぞれ数値に変換してから計算します。

コード

　標準入力と出力は以下の記事を参考にしています。

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);

        String s = fs.next();
        int a = Character.getNumericValue(s.charAt(0));
        int b = Character.getNumericValue(s.charAt(s.length() - 1));

        out.println(a * b);
        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問題(Caesar Cipher)

方針

  1. アルファベットの数である26回分のループを用意する。
  2. 1.で用意したループ処理の中で、文字列を構成する各文字を一つずつずらして、指定する文字列と一致するか判定する。(文字がzまで到達した場合はaに戻る処理を実装します。)

コード

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);

        String string = fs.next();
        String tString = fs.next();

        char[] ch = string.toCharArray();
        char[] tch = tString.toCharArray();

        for(int k = 0;k <= 26;k++) {
            String str1 = new String(ch);
            String string2 = new String(tch);
            if(str1.equals(string2)) {
                out.println("Yes");
                out.flush();
                fs.close();
                return;
            }
            for(int i = 0;i < string.length();i++) {
                if(ch[i] == 'z') {
                    ch[i] = (char) (ch[i] - 25);
                }else {
                    ch[i] = (char) (ch[i] + 1);
                }

            }
        }

        out.println("No");
        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
        }
    }
}

C問題(Graph Isomorphism)

方針

  1. 高橋くんのおもちゃに関してボールiとjが紐で結ばれているかどうかを配列にまとめる。(結ばれている場合は1,そうで無い場合は0とする。)
  2. 青木くんのおもちゃも高橋くんと同様に管理する。
  3. 順列Pを全探索する。
  4. 問題文の条件に従ってグラフが同じ型かどうかを判定する。

コード

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();
        //紐の総数
        int m = fs.nextInt();

        //高橋くんのおもちゃにおいて、ボールを結ぶ紐が存在するかどうか管理する
        int[][] x = new int[n][n];

        for(int i = 0;i < m;i++) {
            int a = fs.nextInt();
            int b = fs.nextInt();
            a--;
            b--;
            x[a][b] = 1;
            x[b][a] = 1;
        }

        //青木くんの場合も同様に管理する
        int[][] y = new int[n][n];
        for(int i = 0;i < m;i++) {
            int c = fs.nextInt();
            int d = fs.nextInt();

            c--;
            d--;
            y[c][d] = 1;
            y[d][c] = 1;
        }

        //順列P
        int[] p = new int[n];
        for(int i = 0;i < n;i++) {
            p[i] = i + 1;
        }

        do {
            boolean ok = true;

            //Pが条件を満たすかどうかを判定する。
            for(int i = 0;i < n;i++) {
                for(int j = 0;j < n;j++) {
                    if(x[i][j] != y[p[i] - 1][p[j] - 1]) {
                        ok = false;
                    }
                }
            }
            if(ok) {
                out.println("Yes");
                out.flush();
                fs.close();
                return;
            }
        } while (nextPermutation(p));

        out.println("No");

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

/**
     * 順列の全探索をするプログラム
     * 前提条件としては
     * 要素の数は2より大きい
     * 配列はソート済みであること
     * @param arr 対象となる配列
     * @return
     */
    public static boolean nextPermutation(int[] arr) {
        //配列の長さ
        int len = arr.length;
        //arr[l] < arr[l + 1]を満たすlのうち最大のものを求める。?
        int left = len - 2;
        //arr[l] < arr[l + 1]を満たすlのうち最大のものを求める。?
        while (left >= 0 && arr[left] >= arr[left+1]) left--;
        //前提条件が崩れるからfalse
        if (left < 0) return false;
        //末尾から探索して初めて現れるarr[left]より大きい要素のインデックス
        int right = len - 1;
        //rightを探索する。
        while (arr[left] >= arr[right]) right--;
        //leftとrightを入れ替える。
        { int t = arr[left]; arr[left] = arr[right];  arr[right] = t; }
        left++;
        right = len - 1;
        //left + 1以降の順番を反転させる。
        while (left < right) {
          { int t = arr[left]; arr[left] = arr[right]; arr[right] = t; }
          left++;
          right--;
        }
        return true;
      }
}

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
        }
    }
}

​
順列全探索に関しては下記サイトを参考にしました。

参考文献

以上となります。
ありがとうございました。
​

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