AtCoder Beginner Contest 234(Rated範囲外)

A - Weird Function
- 思考過程
B - Longest Segment
- 思考過程
C - Happy New Year!
- 思考過程
D - Prefix K-th Max
- 思考過程
E - Arithmetic Number
- 思考過程

コンテスト前のレート：2024
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：329位（2000点、47分33秒）

A - Weird Function

思考過程

同じ計算を何度も実装するには $f(x)$ が複雑すぎるので、素直に関数 $f$ をメソッド化する。
あとは問題文 $2$ 行目の通り。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        sc.close();

        int ans = f(f(f(t) + t) + f(f(t)));
        System.out.println(ans);
    }

    static int f(int x) {
        return x * x + 2 * x + 3;
    }
}

ここまで1分53秒＋0ペナ。901位。

B - Longest Segment

問題

思考過程

$_NC_2$ 通りの全組合せについて、 $2$ 点間の距離をhypotで計算し、その中の最大値を求める。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        sc.close();

        double ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                ans = Math.max(ans, Math.hypot(x[i] - x[j], y[i] - y[j]));
            }
        }
        System.out.println(ans);
    }
}

ここまで3分03秒＋0ペナ。140位。

C - Happy New Year!

問題

思考過程

例２を見て $11$ 番目までを実際に手動で列挙してみると、 $2$ 進数表現にして"1"を"2"に変えたものになっている。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long k = sc.nextLong();
        sc.close();

        StringBuilder sb = new StringBuilder();
        while (k > 0) {
            if (k % 2 == 1) {
                sb.append(2);
            } else {
                sb.append(0);
            }
            k /= 2;
        }
        sb.reverse();
        System.out.println(sb.toString());
    }
}

なお、 $2$ 進数変換をわざわざ自力実装してしまったが、以下のようにして楽ができた。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long k = sc.nextLong();
        sc.close();

        System.out.println(Long.toBinaryString(k).replace('1', '2'));
    }
}

ここまで6分33秒＋0ペナ。328位。

D - Prefix K-th Max

問題

思考過程

$P$ を前から見ていって、常に大きい方から $K$ 個までを保持するようにTreeSetもしくはPriorityQueueで管理する。
そのためには、 $K+1$ 個目を追加したら最小値を削除する、ということを繰り返す。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int k = Integer.parseInt(sa[1]);
        sa = br.readLine().split(" ");
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < k - 1; i++) {
            set.add(p[i]);
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = k - 1; i < n; i++) {
            set.add(p[i]);
            if (i >= k) {
                set.pollFirst();
            }
            pw.println(set.first());
        }
        pw.flush();
    }
}

ここまで10分18秒＋0ペナ。160位。

E - Arithmetic Number

問題
例３を見て、11桁以上は不可能では？と数分悩んでしまったが、全桁同じ値の場合に条件を満たす。

思考過程

$X$ が途中まで等差数になっている場合、後ろの方の桁だけ書き換えるようにすれば $X$ 以上で最小というのが満たせそうな気がする。
の先頭文字を取った部分文字列について、下記を満たすかどうかを、が長い順に調べてみる。
- $Y$ が等差数になっていて、かつ $X$ と同じ文字数まで伸ばした時に途中で $0$ 未満や $10$ 以上の桁が現れないか。
- 差が負の場合は書き換えることによって小さくなることもあるので、最終的に作れた値が $X$ 以上か。
  　
$X$ が $1$ 桁だと差を取ることができず不都合なので最初に除いておく。
$2$ 桁の場合も $X$ 自身が答えになるので、ついでに除いておく。
　
$Y$ が $3$ 桁以上の場合は差を保って伸ばすしかないが、 $2$ 桁の場合はそもそも $2$ 桁目から変える余地がある。
元の $2$ 桁目の値～'9'を調べれば十分だが、'0'～'9'を全部調べても問題はない。
　
これだけだとまだ例３が駄目で、元の $1$ 桁目を $+1$ して $2$ 桁目'0'～'9'も調べる必要がある。

後から思えば結局 $1$ 桁目と $2$ 桁目の組合せを $9 \times 10$ 通り試すだけだった。

import java.util.Scanner;

public class Main {
	static int n;
	static long lx;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		String x = sc.next();
		sc.close();

		n = x.length();
		// 3, 4
		if (n < 3) {
			System.out.println(x);
			return;
		}
		lx = Long.parseLong(x);

		// 2 ここはいらなかった
//		for (int i = n; i > 1; i--) {
//			char[] y = x.substring(0, i).toCharArray();
//			if (exec(y)) {
//				return;
//			}
//		}

		char[] y = new char[2];
		// 5, 6
		y[0] = x.charAt(0);
		for (char i = '0'; i <= '9'; i++) {
			y[1] = i;
			if (exec(y)) {
				return;
			}
		}
		// 7
		y[0]++;
		for (char i = '0'; i <= '9'; i++) {
			y[1] = i;
			if (exec(y)) {
				return;
			}
		}
	}

	// 思考過程2の判定部分
	static boolean exec(char[] y) {
		int d = y[1] - y[0];
		for (int j = 1; j < y.length; j++) {
			if (y[j] - y[j - 1] != d) {
				return false;
			}
		}

		StringBuilder sb = new StringBuilder(String.valueOf(y));
		while (sb.length() < n) {
			int nx = sb.charAt(sb.length() - 1) - '0' + d;
			if (nx < 0 || 9 < nx) {
				return false;
			}
			sb.append(nx);
		}

		long ans = Long.parseLong(sb.toString());
		if (ans >= lx) {
			System.out.println(ans);
			return true;
		}
		return false;
	}
}

ここまで30分19秒＋0ペナ。500位。

残りの3問は解けず。
Fが30分経っても解けなかった後は、3問並行して考えていた。
Fを解いても順位の上昇があまり見込めなくなってきてからは、後ろの2問により注力して考えていたが、どちらも2乗から落とす方法が全くわからず。

最終結果：ABCDEの5完1500点、30分19秒、908位、パフォーマンス1521相当
レート変動：2024（Unrated）

新年早々PASTバチャ76点で上級にも届かず凹んでいたが、ABCでも相変わらず800～900位台を連発しているし、ちょっと下振れすれば普通にこの程度の実力しかないのかもしれない。

今年の目標はとりあえず黄色維持かなというところ。