ABC349備忘録【C~D】

C - Airport Code

問題

考えたこと

まず、$T$を小文字にします。次に$T[0]$を$S$で探索ヒットしたインデックスを$fst$に格納、fstの次からをループを再開し$T[1]$を探索、インデックスを$sec$に格納、最後に$thd$を格納とインデックスを保持していく。
この時、

• $fst, sec, thd$全てに数値が格納されていれば、一つ目の条件に該当し、"Yes"
• $fst, sec$にのみ数値が格納されていて、$t[2]==x$なら二つ目の条件に該当し、"Yes"
• それ以外で"No"
  となる。

ACコード

c.py

s = input()
t = input()
t = t.lower()

fst, sec, thd = -1, -1, -1
for i in range(len(s)):
    if s[i] == t[0]:
        fst = i
        break
for i in range(fst + 1, len(s)):
    if s[i] == t[1]:
        sec = i
        break
for i in range(sec + 1, len(s)):
    if s[i] == t[2]:
        thd = i
        break

if fst != -1 and sec != -1 and thd != -1:
    exit(print("Yes"))
elif fst != -1 and sec != -1 and thd == -1 and t[2] == "x":
    exit(print("Yes"))
else:
    exit(print("No"))

D - Divide Interval

問題

考えたこと

初期値を$L, R$、各状態を$l,r$で表します。
考え方としては、初期値の$L$が$R$になるように各状態の$l$を$R$にどんどん近づけていくことを考えました。また、各処理は$l$の偶奇で違うため処理を分けています。
まず、$l$が奇数の時、$2^0$と入れるしかなく解答に$(l,\ l+1)$を追加、$l = l + 1$と動きます。
次に、$l$が偶数の時、

\begin{align}
&l = 2^i j, \ r = 2^i(j+1) \\ 
&\therefore \ r =2^i\bigg(\frac{l}{2^i} + 1\bigg)
\end{align}

より、$i$を$60$から減らしていったとき$l \ \% \ 2^i = 0$と$r \leq R$を満たす、最初の$(l,\ r)$を解答に追加します。最後に出力して終わりです。

ACコード

d.py

# lは常に動かすので初期値からlとしてしまっています。
l, R = map(int, input().split())
cnt = 0
S = []

while l != R:
    if l % 2 == 0:
        for i in range(60, -1, -1):
            if l % (2**i) == 0 and (r := (2**i) * (l // (2**i) + 1)) <= R:
                S.append((l, r))
                l = r
                break
    else:
        S.append((l, l + 1))
        l += 1

print(len(S))
for s in S:
    print(*s)