taiPyのお悩み解決ブログ

日々の発見をまとめます！

学習記録：B28 - Fibonacci Easy (mod 1000000007) , 競技プログラミングの鉄則　演習問題集

はじめに

競技プログラミングの鉄則　演習問題集　の　B28 - Fibonacci Easy (mod 1000000007)　を解きました！いやー、余りの性質に関していい考察といいますか、トレーニングになりました。

この問題のポイント

  • 余りを出すことがポイント
  • nが9乗くらいあるので、フィボナッチ数列を出すことがまず困難
  • でも、余りって計算するどのタイミングでとっても余りって同じになるんですよね。

参考文献

「998244353 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 , https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a

目次

問題と公式解説

問題　B28 - Fibonacci Easy (mod 1000000007)

https://atcoder.jp/contests/tessoku-book/tasks/math_and_algorithm_ap

B28 - Fibonacci Easy (mod 1000000007) , 競技プログラミングの鉄則　演習問題集

公式解説

https://github.com/E869120/kyopro-tessoku

解答例（自作）

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.nextInt();

        List<Long> list = new ArrayList<Long>();
        
        long ans = 0;
        long tempTwo = 0;
        long tempOne = 0;
        long value = 1000000007;

        for (int i = 0; i < n; i++) {

            if (i == 0) {
                tempTwo = 1;
            }
            if (i == 1) {
                tempOne = 1;
            }

            ans = tempTwo + tempOne;
            ans %= value;
            tempTwo = tempOne;
            tempOne = ans;
        }

        System.out.println(ans);    
    }

}

解答例（公式をJavaに変換）

上記の例との違いは、配列を使っているか使っていないか。上記の自作解答例は配列を使わないバージョン。対して、公式のは配列を使うバージョン。どっちがいいとかじゃないとは思うけれども。公式の方がすっきりしているので、公式の方で自由自在に書けるようになりたい！

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int mod = 1000000007;

// +9はテキトーに。まあ、溢れないようにするため。index out of.. のエラーが出ないように。
        int[] a = new int[n + 9];

// 代入
        a[1] = 1;
        a[2] = 1;

        for (int i = 3; i <= n; i++) {
// 余りを計算しちゃって格納しちゃう！
            a[i] = (a[i - 2] + a[i - 1]) % mod;
        }

        System.out.println(a[n]);
    }

}

Javaの解答例：学習記録：A28 - Blackboard , 競技プログラミングの鉄則 演習問題集

はじめに

競技プログラミングの鉄則を読み進めているので、自分で解いた記録を残します。今回解いた問題はこちら。「A28 - Blackboard 」。それでは楽しんでいってください！

今回の問題のポイント

整数の性質がポイントでしたね。

足し算、引き算、掛け算では好きなタイミングで余りをとっても答え（余り）は変わらないっていうこと。これの競技プログラミングの鉄則、ぜひ買って読んでみてほしい。解説が分かりやすかったです。著者の米田さん。ありがとうございます。

自分がミスったポイント

  • 正しくコピペできていなかった。1000を10000だと思ってずっと苦戦していた。
  • Javaなので、Stringの値を比較するときはString.equals()にしないとですね。
  • 普通に一文字だけの時はcharactor使おう。そっちの方がめんどくさくなさそう。いや、Stringのメソッドたちも捨てにくい。
  • 無駄に長いコード。同じ意味のコードばかり繰り返している。だからまとめたよ！

目次

問題と公式の解説

問題

atcoder.jp

公式の解説

github.com

改良版　解答例

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        String[] t = new String[n];
        int[] a = new int[n];
        
        for (int i = 0; i < n; i++) {
            t[i] = sc.next();
            a[i] = sc.nextInt();
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Divisor(t[i], a[i], ans);
            System.out.println(ans);
        }


    }

    private static int Divisor(String x, int y, int answer) {
        int value =  10000;

        if (x.equals("+")) {
            answer += y;
        }

        if (x.equals("-")) {
            answer -= y;
        }

        if (x.equals("*")) {
            answer *= y;
        }

        if (answer < 0) {
            answer += value;
        }

        answer %= value;
        return answer;        
    }
}

解答例

もう少し短くできますね。重複は削除しないとですよね^^.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        String[] t = new String[n];
        int[] a = new int[n];
        
        for (int i = 0; i < n; i++) {
            t[i] = sc.next();
            a[i] = sc.nextInt();
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            // System.out.println(t[i]);
            // System.out.println(a[i]);
            // System.err.println(ans);
            ans = Divisor(t[i], a[i], ans);
            System.out.println(ans);
        }


    }

    private static int Divisor(String x, int y, int answer) {

// 改良ポイント。tempに代入しようがしまいが、正味変わらない。上記の例（改良版 解答例）を参考にしてね。
        String tempX = x;
        int tempY = y;
        int tempAns = answer;
        int value =  10000;

        if (tempX.equals("+")) {
            tempAns += tempY;
        }

        if (tempX.equals("-")) {
            tempAns -= tempY;
        }

        if (tempX.equals("*")) {
            tempAns *= tempY;
        }

        if (tempAns < 0) {
            tempAns += value;
        }

        tempAns %= value;
        return tempAns;        
    }
}

Javaの解答例：学習記録：A27 - Calculate GCD , 競技プログラミングの鉄則 演習問題集

はじめに

競技プログラミングの鉄則　演習問題集の

問題のポイント

  • ユークリッドの互除法を使うこと
  • ユークリッドの互除法では大きい方を割り、余りを格納
  • 終了条件がどっちかが０になる。＝両方が0でない。と同じ意味。

目次

問題と解説

問題

atcoder.jp

解説

github.com

解答例

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(GCD(a, b));
// 下記に関数を作って、そこで最大公約数を出しています！
    }

    private static int GCD(int x, int y) {
        int tempX = x;
        int tempY = y;
// 領邦とも0以上、どっちかが0になったらやめてほしいからこう書いています。
        while (tempX > 0 && tempY > 0) {
            if (tempX > tempY) {
                tempX %= tempY;
            } else {
                tempY %= tempX;
            }
        }
        

        if (tempX == 0) {
            return tempY;
        } else {
            return tempX;
        }
    }
}

ちなみに公式の解答例

import java.util.*;

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(GCD(A, B));
    }

    // 正の整数 A と B の最大公約数を返す関数
    // GCD は Greatest Common Divisor（最大公約数）の略
    static int GCD(int A, int B) {
        while (A >= 1 && B >= 1) {
            if (A >= B) {
                A %= B; // A の値を変更する場合
            }
            else {
                B %= A; // B の値を変更する場合
            }
        }
        if (A >= 1) {
            return A;
        }
        return B;
    }
};

Javaの解答例：学習記録：A26 - Prime Check , 競技プログラミングの鉄則 演習問題集

はじめに

競技プログラミングの鉄則　演習問題集の「A26 - Prime Check 」という問題です！

今回のポイント

ポイントは素数かどうかを判定するときに、整数の性質を使うのがポイントです！素数とは1とその数以外の約数を持たない数の事でしたよね。逆に言えば、普通の約数を持つ場合は、素数ではないということ。

18が素数かどうかを判定したいとします。平方根を取ってあげるといい。素数じゃないときは、平方根以下の約数が絶対に存在するから。18の平方根は9。他の数でもやってみてください。素数と素数じゃないバージョン両方試すと分かりやすいかと。

目次

問題と解説へのリンク

問題

atcoder.jp

解説

github.com

解答例

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int q = sc.nextInt();
        int[] list = new int[q];

        for (int i = 0; i < q; i++) {
            list[i] = sc.nextInt();
        }

        for (int i = 0; i < q; i++) {
// 下記にisPrime() という関数を作成している
            if (isPrime(list[i])) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    private static boolean isPrime (int x) {
// 2以上っていうのがみそ
// 平方根を　i * i　で表している
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                return false;   
            }
        }

        return true;
    }
}

Javaの解答例：学習記録：B - Minesweeper , AtCoder Beginner Contest 075

はじめに

作りかけです。2024年4月10日 21時10分。おやすみなさい。明日の自分よ、頑張れ！

今回のポイント

目次

問題と解説

問題

atcoder.jp

YouTube解説

www.youtube.com

解答例

import java.util.Scanner;

public class Main {
    static int H, W;
    static String[] B = new String[101];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        H = scanner.nextInt();
        W = scanner.nextInt();
        for (int y = 0; y < H; y++) {
            B[y] = scanner.next();
        }

        for (int y = 0; y < H; y++) {
            for (int x = 0; x < W; x++) {
                if (B[y].charAt(x) == '.') {
                    int c = 0;
                    for (int dx = -1; dx <= 1; dx++) {
                        for (int dy = -1; dy <= 1; dy++) {
                            if (dx == 0 && dy == 0) continue;
                            int xx = x + dx;
                            int yy = y + dy;
                            if (0 <= xx && xx < W && 0 <= yy && yy < H) {
                                if (B[yy].charAt(xx) == '#') c++;
                            }
                        }
                    }
                    char[] temp = B[y].toCharArray();
                    temp[x] = (char) ('0' + c);
                    B[y] = new String(temp);
                }
            }
        }

        for (int y = 0; y < H; y++) {
            System.out.println(B[y]);
        }
    }
}

Javaの解答例：学習記録：B - Foreign Exchange , トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341）

はじめに

トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341）のB - Foreign Exchange という問題の学習記録です。Javaで書いています。

メモ

この問題のポイント

  • 例から考えること
  • 手を動かして考えること
  • Long型を使うこと。intで書いていた部分を全部longに変えるとAC（要するに正解）しました！

目次

問題と解説

問題

atcoder.jp

解説

www.youtube.com

YouTube解説

atcoder.jp

解答例

ステップ

  • インプットを格納する
  • 1つ目の国から取れるだけお金を交換する
  • これを最後までする。

はい、以上！

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        long[] s = new long[n - 1];
        long[] t = new long[n - 1];

        for (int i = 0; i < n - 1; i++) {
            s[i] = sc.nextInt();
            t[i] = sc.nextInt();
        }

        for (int i = 0; i < n - 1; i++) {
            long temp = a[i];
            // System.out.println(temp);

            long order = s[i];
            // System.out.println(order);
            
            long quotient = temp / order;

            a[i + 1] += quotient * t[i];
            // System.out.println(a[i + 1]);
        }

        System.out.println(a[n - 1]);

        sc.close();
    }
}

公式の回答をJavaに！

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long[] a = new long[200001];
        long[] s = new long[200001];
        long[] t = new long[200001];

        for(int i = 1; i <= n; i++) a[i] = scanner.nextLong();
        for(int i = 1; i <= n-1; i++) {
            s[i] = scanner.nextLong();
            t[i] = scanner.nextLong();
        }

        for(int i = 1; i <= n-1; i++) a[i+1] += a[i]/s[i] * t[i];
        System.out.println(a[(int)n]);
    }
}

短く1行で収まりますね！

Javaの解答例：学習記録：C - One Time Swap , モノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345）

はじめに

備忘録として。

この問題のポイント

あんまりよくわかっていないので、これはしっかりと理解したい！！

  • 考察をしっかりとすること！
  • 文字を入れ替えた時に①入れ替えようが入れ替えまいが同じ文字になること、②違う文字列ができること。
  • ②違う文字列ができる。でもかぶる文字列があるんじゃない？なら、単純にはできない。
  • 今回求めたいのはちょうど 1 回 ある場所の文字とある場所の文字を交換した後の文字列としてあり得るものがいくつあるか求めてください。要するに、あの操作したら、何通りくらい文字作れる？って感じ。
  • 例から問題の性質を考察する。考える！そういうテクニックが競プロでは有効！まあ、現実世界でも有効な気がします！

同じ文字になるを考察

  • 同じ文字になる。同じ文字を選ぶ選び方は何通りありますか？ということ。だから、

目次

問題と解説まとめ

問題 atcoder.jp

Javaの解答例

このコードをJavaへ変換しました！

提出コード Submission #51356715 - Monoxer Programming Contest 2024（AtCoder Beginner Contest 345）

解説YouTube www.youtube.com

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int n = s.length();

        long same = 0;
        Map<Character, Integer> cnt = new HashMap<>();
        for (char c : s.toCharArray()) {
            cnt.put(c, cnt.getOrDefault(c, 0) + 1);
        }

        for (int m : cnt.values()) {
            same += c2(m);
        }

        long diff = c2(n) - same;

        long ans = diff;
        if (same > 0) ans++;

        System.out.println(ans);
    }

    private static long c2(long n) {
        return n * (n - 1) / 2;
    }
}