競プロおぼえがき

おぼえがきのためのブログ

蟻本を真面目に勉強する話

タイトルの通りです。

さすがにアルゴリズムの知識が乏しすぎるので、蟻本を真面目に進めて記事にまとめます。

当分の間はJavaで書くけどもしかしたら途中で言語のシフトをするかも?

本の詳細はこれ↓

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

アルゴリズムのまとめをしつつよさそうな問題を見つけたらリンクを張ります。

yukicoder | No.414 衝動

  • 問題

No.414 衝動 - yukicoder

  • 概要

整数 Mが与えられるので x * y = Mとなる整数の組 \{x, y\}を求めて出力する。
ただし求める整数の組は \{1, M\}と\{M, 1\}以外のものでなければならない。
ただし \{1, M\}と\{M, 1\}以外の整数の組み合わせが見つからない場合は \{1, M\}と\{M, 1\}のどちらかを出力する。

  • 考え方

エラトステネスの篩を使って 2 ~ \sqrt{M}までの素数のリストを求める。
リストの要素 iでMが割り切れる \{i, M / i\}を出力する。
割り切れるものがなければ \{1, M\}を出力する。

import java.util.ArrayList;
import java.util.Scanner;

class Main {
    static Scanner in = new Scanner(System.in);

    public static void main(String[] args) {
       long n = in.nextLong();
       boolean[] pr = new boolean[(int)Math.sqrt(n) + 1];
       ArrayList<Integer> list = new ArrayList<>();
       for(int i = 2; i < pr.length; i++){
           if(pr[i]) continue;
           for(int j = 2 * i; j < pr.length; j += i){
               pr[i] = true;
           }
           list.add(i);
       }
       for(int i : list){
           if(n % i == 0){
               System.out.println(i + " " + n / i);
               return;
           }
       }
       System.out.println("1 " + n);
    }
}

yukicoder | No.488 四角関係

  • 問題

No.488 四角関係 - yukicoder

  • 概要

 N個のノードと各ノード関係がM個渡される。
ノードの中で四角の関係(4点の閉路グラフになっているもの。3点で作れる場合は不可)になっているものの数を出力する。

  • 考え方

全探索をする。4つのノードa, b, c, dを選んで、選んだノードすべてが選ばれたノードの中で2つのノードだけと関係を持っている場合は四角の関係になっていると判定する。

import java.util.Scanner;

class Main {
    static Scanner in = new Scanner(System.in);
    static boolean[][] r;

    public static void main(String[] args) {
        int N = in.nextInt(), M = in.nextInt();
        r = new boolean[N][N];
        for (int i = 0; i < M; i++) {
            int a = in.nextInt(), b = in.nextInt();
            r[a][b] = r[b][a] = true;
        }
        int sum = 0;
        for (int a = 0; a < N - 3; a++) {
            for (int b = a + 1; b < N - 2; b++) {
                for (int c = b + 1; c < N - 1; c++) {
                    for (int d = c + 1; d < N; d++) {
                        sum += rect(new int[] { a, b, c, d });
                    }
                }
            }
        }
        System.out.println(sum);
    }

    public static int rect(int[] n) {
        boolean b = true;
        for(int i = 0; i < 4; i++){
            int a = 0;
            for(int j = 0; j < 4; j++){
                if(i == j) continue;
                if(r[n[i]][n[j]]) a++;
            }
            if(a != 2) b = false;
        }
        return b ? 1 : 0;
    }
}

yukicoder | No.92 逃走経路

  • 問題

No.92 逃走経路 - yukicoder

  • 概要

 N個の町があり。 M個の道の情報が渡される。
 i番目の道の情報  a_{i}, b_{i}, c_{i}は、 町a_{i}と町b_{i}をコストc_{i}で移動できる事を示している。
ここでK個の移動コスト履歴 d_{1} ... d_{K}が与えられたときに、移動完了後の町の位置としてあり得るものを列挙する。

  • 考え方

 n[K + 1][N + 1]の配列を使う。
最初の状態ではすべての町 iにいる可能性があるので n[0][i] = trueにする。
 k番目の移動をするとき、 k - 1番目までの移動でその町にいる可能性がある(n[k - 1][i] == true)かつ k番目の移動コストで移動できる道 mがあるときにその町のフラグを更新する。
(n[k][a[m]] or n[k][b[m]] = true)
 K番目までの移動が完了したときに行ける可能性のある町n[K][i]を数えて列挙する。

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

class Main {
    static Scanner in = new Scanner(System.in);

    public static void main(String[] args) {
        int N = in.nextInt(), M = in.nextInt(), K = in.nextInt();
        int[] a = new int[M + 1], b = new int[M + 1], c = new int[M + 1];
        for (int i = 1; i < M + 1; i++) {
            a[i] = in.nextInt();
            b[i] = in.nextInt();
            c[i] = in.nextInt();
        }
        int[] d = new int[K + 1];
        for(int i = 1; i < K + 1; i++){
            d[i] = in.nextInt();
        }
        boolean[][] n = new boolean[K + 1][N + 1];
        Arrays.fill(n[0], true);
        for(int i = 1; i < K + 1; i++){
            Arrays.fill(n[i], false);
        }
        
        for(int x = 1; x < K + 1; x++){
            for(int y = 1; y < N + 1; y++){
                for(int z = 1; z < M + 1; z++){
                    if(n[x - 1][y]){
                        if(a[z] == y && c[z] == d[x]){
                            n[x][b[z]] = true;
                        }
                        if(b[z] == y && c[z] == d[x]){
                            n[x][a[z]] = true;
                        }
                    }
                }
            }
        }
        int sum = 0;
        for(int i = 1; i < N + 1; i++){
            if(n[K][i]){
                sum++;
            }
        }
        System.out.println(sum);
        boolean t = true;
        for(int i = 1; i < N + 1; i++){
            if(t && n[K][i]){
                System.out.print(i);
                t = false;
            }else if(n[K][i]){
                System.out.print(" " + i);
            }
        }
        System.out.println();
    }
}

yukicoder | No.496 ワープクリスタル (給料日前編)

  • 問題

No.496 ワープクリスタル (給料日前編) - yukicoder

  • 概要

座標 (0, 0)から与えられた座標(G_{x}, G_{y})まで移動する最小のコストを求める。
移動は徒歩またはワープを使用することができ、ワープを使用する場合は、(X_{1}, Y_{1})から(X_{1} + x, Y_{1} + y)までコスト cで移動することができる。
隣の座標に移動する際には通行料 Fを支払うことで移動することができる。
また、移動の際は戻る方向への移動は行わない。

  • 考え方

動的計画法を使う。まず、3次元配列の配列 dp[N + 1][G_{x} + 1][G_{y} + 1]で初期化する。
 dp[0][j][k]にはそこまで徒歩で移動した場合のコストを計算して入れる。
あとは i 番目までのワープクリスタルを使用したときの移動コストの最小を求めれば答えが出る。

import java.util.Scanner;

public class Main {
    static Scanner in = new Scanner(System.in);

    public static void main(String[] args) {
        int Gx = in.nextInt(), Gy = in.nextInt(), N = in.nextInt(), F = in.nextInt();
        int[] x = new int[N], y = new int[N], c = new int[N];
        for (int i = 0; i < N; i++) {
            x[i] = in.nextInt();
            y[i] = in.nextInt();
            c[i] = in.nextInt();
        }
        int[][][] dp = new int[N + 1][Gx + 1][Gy + 1];
        for(int i = 0; i < Gx + 1; i++){
            for(int j = 0; j < Gy + 1; j++){
                dp[0][i][j] = (i + j) * F;
            }
        }
        for(int i = 1; i < N + 1; i++){
            for(int j = 0; j < Gx + 1; j++){
                for(int k = 0; k < Gy + 1; k++){
                    if(j == 0 && k == 0){
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                    if(j != 0){
                        dp[i][j][k] = Math.min(dp[i - 1][j][k], dp[i - 1][j - 1][k] + F);
                    }
                    if(k != 0){
                        dp[i][j][k] = Math.min(dp[i - 1][j][k], dp[i - 1][j][k - 1] + F);
                    }
                    if(j - x[i - 1] >= 0 && k - y[i - 1] >= 0){
                        dp[i][j][k] = Math.min(dp[i - 1][j][k], dp[i - 1][j - x[i - 1]][k - y[i - 1]] + c[i - 1]);
                    }
                }
            }
        }
        System.out.println(dp[N][Gx][Gy]);
    }
}

まずワープクリスタルがない場合を忘れていた。
あとこれだと1度使用したワープクリスタルが再度使用できてしまっている。

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

public class Main {
    static Scanner in = new Scanner(System.in);

    public static void main(String[] args) {
        int Gx = in.nextInt(), Gy = in.nextInt(), N = in.nextInt(), F = in.nextInt();
        
        int[] x = new int[N], y = new int[N], c = new int[N];
        for (int i = 0; i < N; i++) {
            x[i] = in.nextInt();
            y[i] = in.nextInt();
            c[i] = in.nextInt();
        }
        int[][] dp = new int[Gx + 1][Gy + 1];
        for (int i = 0; i < Gx + 1; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < Gx + 1; j++) {
                for (int k = 0; k < Gy + 1; k++) {
                    if (j != 0) {
                        dp[j][k] = Math.min(dp[j][k], dp[j - 1][k] + F);
                    }
                    if (k != 0) {
                        dp[j][k] = Math.min(dp[j][k], dp[j][k - 1] + F);
                    }
                    if (j - x[i] >= 0 && k - y[i] >= 0) {
                        dp[j][k] = Math.min(dp[j][k], dp[j - x[i]][k - y[i]] + c[i]);
                    }
                }
            }
        }
        System.out.println(dp[Gx][Gy]);
    }
}

yukicoder | No.490 yukiソート

  • 問題

No.490 yukiソート - yukicoder

  • 概要

以下の手順に沿って与えられた数列をソートする。
1. 各 i (0 < i < 2n - 3)に対してiの小さい順に2.を行う
2. p + q = i(1 \leq p < q \leq n - 1)を満たす整数の組(p, q)に対してa_{p} > a{_q}ならばa_{p}とa{_q}を交換する。

  • 考え方

問題文に書かれている通りに実装するだけ。

import java.util.Scanner;

public class Main {
    static Scanner in = new Scanner(System.in);

    public static void main(String[] args) {
       int n = in.nextInt();
       int[] a = new int[n];
       for(int i = 0; i < n; i++){
           a[i] = in.nextInt();
       }

       for(int i = 0; i < 2 * n - 3; i++){
           for(int j = (i + 1) / 2; j <= i; j++){
               int q = j;
               int p = i - q;
               if(q <= n - 1 && a[p] > a[q]){
                   int t = a[p];
                   a[p] = a[q];
                   a[q] = t;
               }
           }
       }
       for(int i = 0; i < a.length; i++){
           if(i != 0){
               System.out.print(" ");
           }
           System.out.print(a[i]);
       }
       System.out.println();
    }
}

yukicoder | No.491 10^9+1と回文

  • 問題

No.491 10^9+1と回文 - yukicoder

  • 概要

1から整数Nまでの数字で 10^{9} + 1の倍数かつ回文になっている数字の個数を求める。

  • 考え方

1から N / (10^{9} + 1)までの数値で回文を求めれば、 10^{9} + 1を掛けたときに 10^{9} + 1の倍数の回文になる。
回文を求めるときは数字を逆にしてくっつけたもの(12 → 1221)みたいな感じでやれば半分の桁の数値までのループで求めれる。

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

public class Main {
    static Scanner in = new Scanner(System.in);
    static Set<Integer> list = new HashSet<>();
    static int max;

    public static void main(String[] args) {
        max = (int) (in.nextLong() / ((long) 1e9 + 1));
        for (int i = 1; i < 10; i++) {
            f(1, i);
        }
        int ans = 0;

        for (int i : list) {
            if (max >= i) {
                ans++;
            }
        }
        System.out.println(ans);
    }

    public static void f(int s, int n) {
        if (s > String.valueOf(max).length()) {
            return;
        }
        if (s == 1) {
            list.add(n);
            f(s + 1, n);
        } else if (s % 2 == 0) {
            String l = String.valueOf(n);
            String r = (new StringBuilder(String.valueOf(n))).reverse().toString();
            list.add(Integer.parseInt(l + r));
            f(s + 1, n);
        } else if (s % 2 == 1) {
            String l = String.valueOf(n);
            String r = (new StringBuilder(String.valueOf(n))).reverse().toString();
            for (int i = 0; i < 10; i++) {
                list.add(Integer.parseInt(l + i + r));
                f(s + 1, n * 10 + i);
            }

        }
    }
}