Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 153 A問題 AABCDDEFE

AtCoder ARC153 ARC A問題 300 pts

問題

提出解答

問題の概要

以下の条件を満たす正の整数 $x$ を美しい整数という.

は桁の整数であり, その進表記における上から桁目をとしたとき, 以下が成り立つ.
- $S_1 \neq 0$
- $S_1=S_2$
- $S_5=S_6$
- $S_7=S_9$

小さい方から数えて $N$ 番目の美しい整数を求めよ.

制約

美しい整数は $N$ 個以上存在する.

解法

$6$ 桁の正の整数全体の集合を $X$ , 美しい整数全体の集合を $Y$ とする. このとき, 写像 $\varphi: X \to Y$ を次のように定める.

$x \in X$ の $10$ 進表記における数字を上の桁から順に $A,B,C,D,E,F$ としたとき, $\varphi(x)$ は $AABCDDEFE$ と表記される整数.

このとき, $\varphi$ は単調増加な全単射である.

よって, $N$ 番目に小さい美しい整数は $N$ 番目に小さい $6$ 桁の整数を $t$ としたとき, $\varphi(t)$ であるが,

$t=10^6+(N-1)$

であるから, $\varphi(10^6+(N-1))$ を求めれば良い.

計算量は $O(1)$ 時間である.