たいちっち

競技プログラミングをしています

【Java】鉄則本_A06

読んでいる本

問題と提出した回答A06

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Q = sc.nextInt();
        Map sum = new HashMap<>();
        sum.put(0, 0);//初期値
        for (int i = 1; i <= N; i++) {
            int tmp = sc.nextInt();
            sum.put(i, (int) sum.get(i-1)+tmp);
        }
        for (int i = 0; i < Q; i++) {
            int Lq = sc.nextInt();
            int Rq = sc.nextInt();
            System.out.println((int) sum.get(Rq) - (int) sum.get(Lq-1));
        }
        sc.close();
    }
}

累積和の問題。何度も同じ計算をするのは計算量が多くなるから、累積和を計算しておいて、都度回答に必要な値を取り出す。

 

公式の回答:kyopro-tessoku/codes/java/chap02/answer_A06.java

 

問題と提出した回答B06

考え中

 

TODO

  • 本の続きを読む
  • 全bit探索を理解する

 

おわり。。

 

 

【Java】鉄則本_A05

読んでいる本

問題と提出した回答A05

import java.util.Scanner;

public class A05 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        int counter = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                int l = K-i-j;
                if (1 <= l && l <= N) {
                        counter += 1;
                    }
            }
        }
        System.out.println(counter);
    }
}

公式の回答と同じ方法だった。

公式の回答:kyopro-tessoku/codes/java/chap01/answer_A05.java

for文を3回使って全探索する方法でも答えは出るが、時間が掛かり過ぎる。
3つの値の合計が分かっていて(K)、2つの値が分かっているなら、もう1つの値も分かるという考え方で、for文を2回に抑える。

この問題はAtCoderの「C - Otoshidama」

の類題だった。

TODO

  • 他のA,B,C問題を解く
  • 本の続きを読む

 

おわり。。

【Java】鉄則本_A04_B04

読んでいる本

問題と提出した回答A04

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String N_binary = Integer.toBinaryString(N);
        String pre_0 = "";//先頭につける0
        //10桁に足りない分だけ0を先頭に付ける
        for (int i = 0; i < (10 - N_binary.length()); i++) {
            pre_0 += "0";
        }
        System.out.println(pre_0 + N_binary);
    }
}

取得した数値を2進数の文字列に変換して、10桁に足りない分だけ、文字列の先頭に「0」を付け足す回答をした。

10進数→2進数の変換は、Integerクラスの

toBinaryString(int i)

整数引数の文字列表現を、基数2の符号なし整数として返します。

を使用した。

 

公式の回答はシフト演算子を使っている。

// 上の桁から順番に「2 進法に変換した値」を求める
        for (int x = 9; x >= 0; x--) {
            int wari = (1 << x); // 2 の x 乗
            System.out.print((N / wari) % 2); // 割り算の結果に応じて 0 または 1 の出力
        }

シフト演算子は使用したことがないので、この機会に使い方をマスターしたい。
「1<<x」はxだけ、数値を左にシフトさせるということらしい。

試すとずらした数値を2乗する形になっていた。

System.out.println(1 << 0); //1       1
System.out.println(1 << 1); //2      10
System.out.println(1 << 2); //4     100
System.out.println(1 << 3); //8    1000
System.out.println(1 << 4); //16  10000
System.out.println(1 << 5); //32 100000

ずらす数だけ2乗している(例:1<<3なら2の3乗)。

公式の回答:kyopro-tessoku/codes/java/chap01/answer_A04.java

問題と提出した回答B04

回答1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String N = String.valueOf(sc.nextInt());
        int N_10 = Integer.parseInt(N, 2);
        System.out.println(N_10);
    }
}

IntegerクラスのparseIntを使った。

parseInt(String s)
文字列の引数を符号付き10進数の整数型として構文解析します。

回答2

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String N = String.valueOf(sc.nextInt());
        int N_10 = 0;
        for (int i = 0 ; i < N.length(); i++) {
            int tmp = Character.getNumericValue(N.charAt(i));
            if (tmp == 0) {//2の0乗は1になるのでスキップさせる
                continue;
            }
            N_10 += Math.pow(2, tmp * (N.length() -1 -i));
        }
        System.out.println(N_10);
    }
}

入力を文字列で受け取り、for文の中で各桁ごとに10進数に変換して足し合わせた。
文字を数値に変換するのはCharacterクラスのgetNumericValueを使用した。

getNumericValue(char ch)
指定されたUnicode文字が表すint値を返します。

 この変換作業をしないと、値が「49」になってしまう。下の記事を参考にしました。

TODO

  • 他のA,B,C問題を解く
  • 本の続きを読む

 

おわり。。

 

 

【Java】鉄則本_A03_B03

読んでいる本

問題と提出した回答A03

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] P = new int[N];
        int[] Q = new int[N];

        for (int i = 0; i < N; i++) {
            P[i] = sc.nextInt();
        }
        for (int i = 0; i < N; i++) {
            Q[i] = sc.nextInt();
        }
        boolean flag = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (P[i] + Q[j] == K) {
                    flag = true;
                    break;
                }
            }
        }
        if (flag) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
        sc.close();
    }
}

2重のfor文を回す。

公式の回答:kyopro-tessoku/codes/java/chap01/answer_A03.java

問題と提出した回答B03

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N ; i++) {
            A[i] = sc.nextInt();
        }
        boolean flag = false;
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                for (int k = j+1; k < N; k++) {
                    if (A[i] + A[j] + A[k] == 1000) {
                        flag = true;
                        break;
                    }
                }
            }
        }
        if (flag) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

3重のfor文。Nが100なので、多くとも100の3乗の100万回なので計算しきれる。
同じ商品を選択することは出来ないので、2重目(j)、3重目(k)のfor文の開始を工夫する必要があった。

  • i
  • j = i+1
  • k = j + 1

として、同じ商品を選ばないようにしている。

TODO

  • 他のA,B,C問題を解く
  • 本の続きを読む

 

おわり。。

 

 

【Java】鉄則本_A02_B02

読んでいる本

問題と提出した回答A02

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int X = sc.nextInt();
        Set set = new HashSet<>();
        for (int i = 0; i < N; i++) {
          set.add(sc.nextInt());
        }
        if (set.contains(X)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

含まれるかどうか?をチェックする問題。
Setを使って重複せずに値を格納して、含まれているかどうかで出力を分けた。

公式の回答:kyopro-tessoku/codes/java/chap01/answer_A02.java 

問題と提出した回答B02

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        boolean flag = false;
        for (int i = A; i <= B; i++) {
            if (100 % i == 0) {
                flag = true;
                break;
            }
        }
        if (flag) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

100をA~Bで割ったときの余りが0になる値はあるか?をチェックした。

TODO
  • 他のA,B,C問題を解く
  • 本の続きを読む

 

おわり。。

 

【Java】鉄則本_A01_B01

読んでいる本

読み始めました。
オススメにあったように、1周目は★4までの問題を解いていきます。

問題と提出した回答A01

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(N*N);
        sc.close();
    }
}

単純に出力するだけ。

公式の回答:kyopro-tessoku/codes/java/chap01/answer_A01.java

問題と提出した回答B01

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        System.out.println(A+B);
    }
}

単純に出力するだけ。

TODO
  • 他のA,B,C問題を解く
  • 本の続きを読む

 

おわり。。

UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)

参加したコンテスト

提出した回答A
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        System.out.println((a+b) * (c-d));
        System.out.println("Takahashi");
        sc.close();
    }
}
提出した回答B
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Map map = new HashMap<>();
        for (int i = 1; i <= 10; i++) {
            String tmp = sc.next();
            if (tmp.contains("#")) {
                map.put(i, tmp);
            }
        }
        int A = (int) Collections.min(map.keySet());
        int B = (int) Collections.max(map.keySet());

        String tmp2 = map.get(A).toString();
        List list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            if (tmp2.charAt(i) == '#') {
                list.add(i);
            }
        }
        int C = (int) Collections.min(list) + 1;
        int D = (int) Collections.max(list) + 1;

        System.out.println(A + " " + B);
        System.out.println(C + " " + D);
        sc.close();
    }
}
提出しようとした回答C(解けていない状態のコードです)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        String N_2 = Long.toBinaryString(N);//文字列で扱わないとエラーが発生する

        //2の○乗の位の値が1ならその数を格納する
        List list = new ArrayList<>();
        int counter = 0;
        for (int i = N_2.length()-1; 0 <= i; i--) {
            if (N_2.charAt(i) == '1') {
                list.add(counter);
            }
            counter += 1;
        }

        //出力する値は2のlistのサイズ数ある
        //11→1011なら[0,1,3]で2の3乗=8個、答えがある
        List list_N_10 = new ArrayList<>();
        for (int i = 0; i < Math.pow(2, list.size()); i++) {
            if (i == 0) {
                System.out.println(0);
            } else {
                //listの中からフラグ立てをしたい
            }
        }
    }
}
感想

コンテスト初参加!参加することに意義がある!!
A、B問題は必ず正解して、うまくいけばC問題も回答したいと思って臨んだ。
A問題は2分30秒程度で正解した。
B問題は25分程度で正解した。
意外といけるかと思ったが、C問題が解けず、そこで終了。解きたい方向性はあったものの、それを実装する力がなかった。まだまだ修行が必要。

最近発売された米田先生の本を購入したので、体系的に勉強する。

何れにせよ良い経験になった。C問題を確実に解き切る実力をつけることを当面の目標に頑張りたい。

TODO
  • 他のA,B,C問題を解く
  • アルゴリズムの本を読む
  • タイミング合う回のコンテストに参加する

 

おわり。。