AtCoder Beginners Contest 336 (ABC336) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - Long Loong
問題
レベル $X$ の 龍文字列 を、 $1$ 個の L, $X$ 個の o, $1$ 個の n, $1$ 個のg をこの順に並べた長さ $X+3$ の文字列とします。
レベル $N$ の龍文字列を出力してください。
考察
$2$ つの文字列をくっつけた新しい文字列を取得したいとき、Pythonでは次のように書けます。
"""文字列結合の例"""
S = "AtC"
T = "oder"
ans = S + T
print(ans) # 出力結果: AtCoder
また、同じ文字列を複数個くっつけた文字列を取得したいとき、Pythonでは次のように書けます。
"""同じ文字列をいくつかくっつける例"""
A = "niwa"
B = "tori_ga_iru"
ans = A * 4 + B
print(ans) # 出力結果: niwaniwaniwaniwatori_ga_iru
この $2$ つをつかうと、解答コードは次のように書けます。
コード
N = int(input())
ans = 'L' + 'o' * N + 'ng'
print(ans)
B - CTZ
問題
正整数 $X$ について、 $X$ を $2$ 進表記したときに末尾に連続する 0 の個数を $\text{ctz} (X)$ とします。
$\text{ctz} (N)$ を求めてください。
考察
bit演算で解きます。
$1$ とのand演算をすれば、 $2$ 進表記したときの末尾の数字が分かります。
下のコードでは、末尾の数字が 0 だったとき、変数 $ans$ を $1$ だけ増やした後、その末尾の 0 を消すために $N$ を $1$ つだけ右シフトしています。
コード
N = int(input())
ans = 0
while N & 1 == 0:
ans += 1
N >>= 1
print(ans)
別解
bin()関数をつかった解法
$10$ 進数から $2$ 進数に変換してくれる関数 `bin(x)` があります。"""bin()関数の使用例"""
s = bin(17) # 0b10001
t = bin(62) # 0b111110
この $s, t$ は文字列で、先頭に 0b がついていることに注意してください。
これを用いると、次のコードでACできます。
N = int(input())
S = bin(N)
ans = 0
for x in reversed(S):
if x == '0':
ans += 1
else:
break
print(ans)
C - Even Digits
問題
$10$ 進数で見たときに $0,2,4,6,8$ のみが登場する整数を 良い整数 と呼ぶことにします。
小さい方から $N$ 番目の良い整数を求めてください。
考察
$0,2,4,6,8$ のみが登場する整数について聞かれていますが、これを $0,1,2,3,4$ のみが登場する整数について聞かれていると考えれば、これは「5進数」について聞かれていることになります。
つまり、以下の小問題が解ければokです。
$N$ が入力で与えられます。 $N-1$ を $5$ 進数で表記して出力してください。
$5$ 進数に限らず、任意の整数 $p$ に対して $10$ 進数の数字を $p$ 進数に変換する問題は良く出題されています。
この小問題に対するコードは次のように書けます。
"""小問題の解答コード"""
from collections import deque
N = int(input()) - 1
que = deque()
while True:
que.appendleft(N % 5)
N //= 5
if N == 0:
break
print(*que, sep='')
元々の問題では $0,2,4,6,8$ のみをつかった整数について聞かれていたので、あとは各桁の数を $2$ 倍すればokです。
まとめると、次のコードでACできます。
コード
from collections import deque
N = int(input()) - 1
que = deque()
while True:
que.appendleft(N % 5 * 2)
N //= 5
if N == 0:
break
print(*que, sep='')
D - Pyramid
問題
ピラミッド数列のサイズの最大値はいくつでしょうか？
考察1 リストAの要素を変更する
$A_0$ について考えてみると、 $A_0=5$ でも、 $A_0=100$ でも、$A_0=1$ でも、できるピラミッドのサイズの最大値は変わらないことが分かります。
$A_1$ についても、$A_1 \geq 2$ であればできるピラミッドのサイズの最大値は変わらないです。
$i=0, 1, \cdots , N-1$ について、
$$A_i \leftarrow \min (A_i, i+1, N-i)$$
としてもokです。
この先の議論を簡単にするために、この変形をしておきます。
ここまでをコードにするとこんな感じになります。
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
A[i] = min(A[i], i + 1, N - i)
考察2 ピラミッドの分解
たとえば $A=(3, 2, 3, 2, 1)$ のとき、真ん中の $3$ を中心としてサイズ $3$ のピラミッドをつくれます。
$(1, 2, 3, 2, 1)$ みたいなピラミッドの形について問われることはあまりないですが、これを $(1, 2, 3)$ と $(3, 2, 1)$ に分解してあげると、これなら今まで何度も扱ってきたような数列になっていると思います。
左側の $(1, 2, 3)$ の部分について考えてみます。
数列 $A$ の $i$ 番目 $A_i$ を中心にしてサイズ $3$ のピラミッドができるとき、$A_{i-2} \geq 1 ,\enspace A_{i-1}\geq 2 , \enspace A_i \geq 3$ が成り立ちます。
少し変形すると、 $A_{i-2}+2 \geq 3, \enspace A_{i-1}+1\geq 3, \enspace A_i \geq 3$ です。
逆に言えば、 $A_0+i\geq X_i,\enspace A_1+(i-1)\geq X_i,\enspace \cdots ,\enspace A_i\geq X_i$ を満たすような最大の $X_i$ が分かると、左側だけを見てできるピラミッドの最大サイズが分かります。
この $X_i$ は、 $X_i=\min(A_0+i, \enspace A_1+(i-1), \enspace \cdots , \enspace A_i)$ と書けます。
$X_{i+1}$ について考えてみます。
$$
\begin{aligned}
X_{i+1} &= \min (A_0+(i+1), \enspace A_1+i, \enspace \cdots , \enspace A_i+1, \enspace A_{i+1})
\\ &= \min (X_i + 1 ,\enspace A_{i+1})
\end{aligned}
$$
となります。
$X_i$ が分かっていれば、 $O(1)$ で $X_{i+1}$ も求められることになります。
$X_0=A_0$ なので、$X_0, X_1, \cdots , X_{N-1}$ 全体を $O(N)$ で求められます。
ピラミッドの左半分だけを考えてきましたが、右半分に関しても同様に求めることができて、全体で $O(N)$ でこの問題を解くことができます。
コード
def f(lst):
result = [0] * len(lst)
min_num = 0
for i, x in enumerate(lst):
min_num = min(min_num + 1, x)
result[i] = min_num
return result
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
A[i] = min(A[i], i + 1, N - i)
left = f(A)
right = f(A[::-1])[::-1]
ans = -1
for i in range(N):
pyramid_size = min(left[i], right[i])
ans = max(ans, pyramid_size)
print(ans)