どうもこんにちは！
今週のコンテストはBまで完答。Cは多分考え方はわかったんですが実装できずギブアップ。
今回はBまで振り返りますが、Cも考えたことは一応書き残します。
問題
問題は以下のリンクから。
A - Streamer Takahashi -
基準となる2つの時間LとRが与えられます。続いて2つの時間XとYの組がN個与えられるので、X <= Lと Y >= Rを同時に満たす組が何個あるかを回答する問題。
問題の定義としてはL時からR時まで配信するとして、値の範囲は$0 <= L < R <= 23$、$0 <= X < Y <= 23$で、YやRが日をまたいだ時間となる入力はないです。
1組ずつ比較して条件を満たすものをカウントしました。
n,l,r = map(int,input().split())
ans = 0
for i in range(n):
x,y = map(int,input().split())
if x <= l and y >= r:
ans +=1
print(ans)
B - String Too Long -
与えられた文字cと整数lの組n個から、文字cをl個連続した文字列を順番につないで作った文字列を出力するという問題。例えば、(a,2)と(b,5)が与えられた場合、出力する文字列はaabbbbbとなります。ただし、作った文字列の文字数が100を超える場合はかわりにToo Longを出力します。
与えられる文字と整数の組は最大100組、lの値は最大$10^{18}$です。
組の最大が100個なのでTLEにはならないと判断して素直に文字列を作るようにしました。追加する文字列が100を超える場合と追加後の文字列が100を超えた場合はその時点でToo Longを出力する処理にしています。
n = int(input())
s = ''
for i in range(n):
c,l = map(str,input().split())
l = int(l)
if l > 100:
s = "Too Long"
break
s += c * l
if len(s) > 100:
s = "Too Long"
break
print(s)
C - Palindromic in Both Bases -
10進数で指定された1からnまでの値のうち、10進数でも指定された進数でも回文数(101のような最初から読んでも最後から読んでもでも同じになる数字)になる値を抽出し、10進数での合計を出力する問題。指定される進数は2~9、nの最大は$10^{12}$です。
nの最大が大きいので、1から全部確認したらTLEになるとは最初から考えてはいました。おそらく文字列操作でまず10進数の回文数をつくり、これを指定された進数に変換して回文数だったら足していけばいいんだろうとは思いました。
が、回文数の生成コードが作れず・・・時間なくなってきて悩むだけでもなぁということで一応1から全部確認するコードは作りましたが、入力例の時点でTLEでした。。
追記に伴い折り畳みにしておきます。
回文数かを範囲内の10進数全てで確認するプログラム
import numpy as np
a = int(input())
n = int(input())
ans = []
for i in range(1,n):
si = str(i)
if si == si[::-1]:
d = np.base_repr(i, a)
sd = str(d)
if sd == sd[::-1]:
ans.append(i)
print(sum(ans))
--- 追記 ---
解説放送を見たところ回文数の文字列を作るのは逆順の文字列を足すだけということで、作ってみたのが以下。
入力例はクリアできるんですが、提出するとまだTLE。スライスを使っているかnumpyを使ってのa進数への変換の計算量が多いとかかなと思いますが解決策はすぐに思いつかず、いったん記録。
import numpy as np
a = int(input())
n = int(input())
ans = 0
for i in range(1,10**6):
# 10進数で偶数桁の回文数を作成
# さらにこれの中央1文字を削って奇数桁の回文数を作成
si = str(i)
si_even = si + si[::-1]
si_odd = si_even[:len(si_even)//2] + si_even[len(si_even)//2+1:]
# 偶数桁の回文数がn以下かつa進数でも回文数なら加算
d = np.base_repr(int(si_even),a)
if int(si_even) <= n and d == d[::-1]:
ans += int(si_even)
# 偶数桁の回文数がn以下かつa進数でも回文数なら加算
d = np.base_repr(int(si_odd),a)
if int(si_odd) <= n and d == d[::-1]:
ans += int(si_odd)
print(ans)
さらに少し試して、10進数の回文数をa進数に変換しているところの計算量が多いようでした。そこでnumpyの使用をやめて計算で作るようにし、さらに生成した文字列が回文かのチェックでスライスを使わずチェックするとしました。
これでACは増えているのですがTLEも残っている状態です。
あとは進数の変換とそれが回文になっているかの関数の計算量削減しか残っていなさそうなんですが手詰まり。。
これまでずっとCPythonで提出してTLEだったんですが、ふと思い立ってPyPyで提出したらACとなりました！
PyPyの方が速度早い場合があるとは聞いていましたが、全然違うんですね・・・
def isPalindrome(x,a):
s = ''
while x:
s += str(x % a)
x //= a
b = True
for i in range(len(s)//2):
if s[i] != s[len(s)-1-i]:
b = False
break
return b
a = int(input())
n = int(input())
ans = 0
for i in range(1,10**6):
# 10進数で偶数桁の回文数を作成
# さらに1文字を削って奇数桁の回文数を作成
si = str(i)
si_even = si + si[::-1]
si_odd = si + si[-2::-1]
# 偶数桁の回文数がn以下かつa進数でも回文数なら加算
if int(si_even) <= n and isPalindrome(int(si_even),a):
ans += int(si_even)
# 偶数桁の回文数がn以下かつa進数でも回文数なら加算
if int(si_odd) <= n and isPalindrome(int(si_odd),a):
ans += int(si_odd)
print(ans)
--- ここまで ---
ではでは。