AtCorder|(復習)AtCoder Beginner Contest 146

昨日はAtCoder Beginner Contest 146に参戦してきました。(コンテスト参戦は9回目)

結果はA,Bの2完で、ratignが少しさがりました。

A - Can't Wait for Holiday

s = input()
if s == 'SUN':
  print(7)
elif s == 'MON':
  print(6)
elif s == 'TUE':
  print(5)
elif s == 'WED':
  print(4)
elif s == 'THU':
  print(3)
elif s == 'FRI':
  print(2)
else:
  print(1)

曜日の情報から次の日曜日までの日数を算出する問題でした。入力パターンは7通りしかないので、条件分岐でAC獲得しました。

B - ROT N

n = int(input())
s = input()
 
ans = []
 
# いったんリストにする
str_list = list(s)
 
for j in range(len(str_list)):
  temp = ord(str_list[j])+n
  if temp >= 91:
    temp = temp-26
  ans.append(chr(temp))
 
# またリストから文字列へ戻す
str_changed = "".join(ans)
print(str_changed)

pythonの組み込み関数ordを用いて文字列を整数化した値に、入力nを足し再度文字列に戻してACを獲得しました。 ord関数/chr関数は知らなかったので、コンテスト中にググって仕様確認して利用しました。

python.civic-apps.com

文字列を整数化したときに91(Z)を超えた場合にAに戻るようにする点が少しコーデテストで時間食いました。

C - Buy an Integer

今回解けなかった問題です。 参考解答例

# coding:utf-8
 
def get_val(A, B, n):
    return A * n + B * len(str(n))
 
 
def main():
    A, B, X = map(int, input().split(' '))
 
    s = 0
    e = 10**9+1
 
    while e - s > 1:
        n = (e + s) // 2
        val = get_val(A, B, n)
        if val <= X:
            s = n
        else:
            e = n
 
    print(s)
 
if __name__ == '__main__':
    main()
# coding:utf-8

def get_val(A, B, n):
    return A * n + B * len(str(n))


def main():
    A, B, X = map(int, input().split(' '))

    s = 0
    e = 10**9+1

    while e - s > 1:
        n = (e + s) // 2
        val = get_val(A, B, n)
        if val <= X:
            s = n
        else:
            e = n

    print(s)

if __name__ == '__main__':
    main()

atcoder.jp 単純に1~で購入値とXを比較するコードだとTLEになります。

2分探索で検索する範囲を絞りながら購入できるNを求めていけばAC獲得となる問題でした。 kawakeee.hatenablog.com

2分探索は以前に記事にもまとめていました。参考ACコードが少し長いので復習がてらコード実装してみました。 (復習)改めて自分の解答

a,b,x = map(int,input().split())

left = 0
right = (10**9)+1

while left+1 < right:
  mid = (left+right)//2
  v = a*mid + b*len(str(mid))
  if v <= x:
    left = mid
  else:
    right = mid
print(left)

参考ACよりかはスッキリして見える(はず)。 2分探索は学びましたが、まだ実践で使えてないですね。今回は実践するチャンスでしたが気づきませんでした。また次回がんばります。