競プロおぼえがき

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

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

        }
    }
}

yukicoder | No.52 よくある文字列の問題

  • 問題

No.52 よくある文字列の問題 - yukicoder

  • 概要

与えられた文字列の前後のどちらかから文字を取ることを文字列がなくなるまで続ける。
取り出した順につなげた文字列を新しい文字列とするときに、新しい文字列は何通り作ることができるか求める。

  • 考え方

普通に全探索。再帰的に関数を呼び出して前後どちらからも取り出す方法を試す。取り終わったらSetに入れておけば同じ文字列の重複はなくなる。
一通り終わったところでsetのサイズを表示して終わり。

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

public class Main {
    static Scanner in = new Scanner(System.in);
    static Set<String> set = new HashSet<>();

    public static void main(String[] args) {
        String s = in.next();
        f(s, "");
        System.out.println(set.size());
    }

    public static void f(String s1, String s2) {
        if (s1.length() == 1) {
            set.add(s2 + s1);
        } else {
            f(s1.substring(0, s1.length() - 1), s2 + s1.charAt(s1.length() - 1));
            f(s1.substring(1, s1.length()), s2 + s1.charAt(0));
        }
    }
}

yukicoder | No.49 算数の宿題

  • 問題

No.49 算数の宿題 - yukicoder

  • 概要

足し算と掛け算の問題が渡されるので計算をする。
ただし足し算の記号が"*"で掛け算の記号が"+"になっている。
計算の優先度はなく左から順番に計算をする。

  • 考え方

渡された文字列の"*"と"+"を"_*_"と"_+_"に置換して"_"で文字列の分割をする。
分割後の配列が数字と演算子の配列になるのであとは左から順番に計算していくだけ。

import java.util.Scanner;
public class Main {
    static Scanner in = new Scanner(System.in);
    public static void main(String[] args) {
        String[] s = in.nextLine().replaceAll("(\\+|\\*)", "_$1_").split("_");
        int sum = Integer.parseInt(s[0]);
        for(int i = 1; i < s.length; i += 2){
            if(s[i].equals("+")){
                sum *= Integer.parseInt(s[i + 1]);
            }else if(s[i].equals("*")){
                sum += Integer.parseInt(s[i + 1]);
            }
        }
        System.out.println(sum);
    }
}

yukicoder | No.527 ナップサック容量問題

  • 問題

No.527 ナップサック容量問題 - yukicoder

  • 概要

ナップサックに入れる荷物の情報 w_i, v_iと価値の最大値Vが与えられる。
ナップサックの容量として考えられる最小値と最大値を求める。
ただし最大値が定まらない場合は"inf"を出力する。

  • 考え方

とりあえずは普通にナップサック問題を解く。
荷物の情報入力時に全荷物の重さの合計 W_{sum}を求めておく。
 0 \leq V \leq 100000なので最大の100000までの価値の最大をとりあえず求める。
そのあと価値の最大が Vになっている容量 W_{min}, W_{max}を求めて出力。
ただし W_{max} > W_{sum}の場合はもっと入る可能性があるので容量の最大値は"inf"になる。

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 N = in.nextInt();
        int[] v = new int[N], w = new int[N];
        int sum = 0;
        for(int i = 0; i < N; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
            sum += w[i];
        }
        int V = in.nextInt();

        int[][] dp = new int[N + 1][100001];
        for(int i = 0; i < N; i++){
            Arrays.fill(dp[i], 0);
        }

        for(int i = 1; i < N + 1; i++){
            for(int j = 0; j < 100001; j++){
                if(j - w[i - 1] >= 0){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i -1]] + v[i - 1]);
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        int min = 0, max = 0;
        for(int i = 1; i < dp[N].length; i++){
            if(dp[N][i] == V){
                min = i;
                break;
            }
        }
        for(int i = dp[N].length - 1; i > 0; i--){
            if(dp[N][i] == V){
                max = i;
                break;
            }
        }
        System.out.println(min);
        System.out.println(max > sum ? "inf" : max);
    }
}

yukicoder | No.45 回転寿司

No.45 回転寿司 - yukicoderを解きました。

 

  • 問題概要

N皿の寿司が流れてきてそれぞれのお寿司の美味しさがvである。

一度流れてしまった皿はとることができず、連続で皿をとることもできない。

以上の条件のときの美味しさの合計の最大を求める。

 

  • 考え方

配列を用意して動的計画法を使う。

i皿目のときにdp[i] = max(dp[i - 1], dp[i - 2] + v[i])で更新する。

 


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 N = in.nextInt();
        int[] v = new int[N + 1];
        for(int i = 0; i < N; i++){
            v[i] = in.nextInt();
        }
        int[] y = new int[N + 1];
        Arrays.fill(y, Integer.MAX_VALUE);
        y[0] = 0;
        y[1] = v[0];
        
        for(int i = 2; i < v.length; i++){
            y[i] = Math.max(y[i - 1], y[i - 2] + v[i - 1]);
        }
        System.out.println(y[N]);
    }
}
    

yukicoder | No.4 おもりと天秤(動的計画法)

No.4 おもりと天秤 - yukicoderを解きました。

  • 問題概要

重りの個数Nと各おもりの重さwが与えられる。

重りを天秤に乗せたときに、左右水平にすることができるか判定する。

 

  • 考え方

そもそも合計が奇数だったら水平にならないから最初に合計を求める。

合計が偶数だったら、合計の半分の重さとなるようなおもりのを選ぶことができるかのナップサック問題として解ける。

 


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 N = in.nextInt();
        int[] w = new int[N];
        int sum = 0;

        for (int i = 0; i < N; i++) {
            w[i] = in.nextInt();
            sum += w[i];
        }

        if (sum % 2 == 1) {
            System.out.println("impossible");
            return;
        }
        int h = sum / 2;
        boolean[][] dp = new boolean[N + 1][h + 1];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], false);
        }
        dp[0][0] = true;
        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < h + 1; j++) {
                if(0 <= j - w[i - 1] && dp[i - 1][j - w[i - 1]]){
                    dp[i][j] = true;
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        if (dp[N][h]) {
            System.out.println("possible");
        } else {
            System.out.println("impossible");
        }
    }
}
    

yukicoder | No.3 ビットすごろく(幅優先探索)

No.3 ビットすごろく - yukicoderを解きました。


1からスタートして立っている地点の2進数表記の1のビットが立っている数だけ左右どちらかに動ける。
動ける範囲は1からNまで。
Nにピッタリ到着したらゴール。


幅優先探索で、初めていくところなら距離を更新して座標をキューに入れる。

ゴールの座標に到着またはキューに何もない(到着不可能)なら終了。


import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;

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

    public static void main(String[] args) {
        int n = in.nextInt();
        if (n == 1) {
            System.out.println(1);
            return;
        }
        int[] d = new int[n + 1];
        Arrays.fill(d, Integer.MAX_VALUE);
        d[1] = 1;
        Deque q = new ArrayDeque<>();
        q.add(1);
        while (q.size() > 0) {
            int a = q.poll(), b = bit(a);
            if (a + b == n) {
                System.out.println(d[a] + 1);
                return;
            }
            if (0 < a - b && d[a - b] == Integer.MAX_VALUE) {
                d[a - b] = d[a] + 1;
                q.add(a - b);
            }
            if (a + b < n && d[a + b] == Integer.MAX_VALUE) {
                d[a + b] = d[a] + 1;
                q.add(a + b);
            }
        }
        System.out.println(-1);
    }

    public static int bit(int n) {
        int s = 0;
        while (n > 0) {
            if (n % 2 == 1) {
                s++;
            }
            n /= 2;
        }
        return s;
    }
}