ABC279のA,B,C,D,問題をpythonで解説していきます。
A問題
問題: wwwvvvvvv
考察
今回、入力される文字は、 v or w です。
vの場合：下に尖っている箇所は、1箇所
wの場合：下に尖っている箇所は、2箇所
なので、Sという文字列のうち、vの個数*1 + wの個数*2が答えになります。
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
letter = S()
cnt = 0
for i in letter:
if i == "v":
cnt += 1
else:
cnt += 2
print(cnt)B問題
考察
今回は、Tという文字列がSという文字列の中に連続する文字列として含まれているかを判断すればよいです。
上記内容は、if文で実装できます。
(連続する文字列でなくても良い場合はもっと面倒ですが・・・)
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
s = S()
t = S()
if t in s:
print("Yes")
else:
print("No")C問題
考察
まず、今回面倒なのは、入力は行ごとなのに、判別するのは列ごとである点です。
そのため、まず最初に入力された2次元リストを転置します(2次元リストの転置の仕方)
転置後に、Sを並び替えてTにできるかについて考えます。
これがもし1次元なら
もしこれが一次元であれば、簡単に問題を解くことができます。
ex) letter_S = atcoder, letter_T = acdeort
なぜなら、letter_Sだけではなく、letter_Tも昇順 or 降順に並び替えて、文字列が全一致したら良いからです。
今回は、2次元配列ですが、入れ替え可能なのは、列ごと(転置後であれば行ごと)であるので、転置後の2つの配列をそれぞれソートし、
- SとTが一致したら、Yes
- SとTが不一致なら、No
を出力します。
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
H,W = MI()
s_box = []
t_box = []
for i in range(H):
s = S()
s_box.append(s)
for i in range(H):
t = S()
t_box.append(t)
l_2d_s = list(zip(*s_box))#転置された2次元配列s
l_2d_t = list(zip(*t_box))#転置された2次元配列t
l_2d_s.sort()
l_2d_t.sort()
for i in range(W):#転置後なので、行数はw
if l_2d_t[i] != l_2d_s[i]:#行ごとに見ていき、一致していなかったら
print("No")
exit()
#すべて一致していたら
print("Yes")D問題
考察
今回の問題は三分探索法を使う問題です。(時間内に解けなかった・・・くやしい)
Q 三分探索法とは？
凸型の関数の最小値を求める際に使用できる解法です。
※注意※
f(x)というxの取りうる範囲を[left,right]とした場合の凸型の関数において、最小値をとるf(m)までにleftからmにかけて単調減少し、mからrightまで単調増加する場合のみ使用できる。
三分探索法のアルゴリズム
- f(x)という関数のうち、xの取りうる範囲を[left,right]とした場合、l→rの範囲を三分割するような、c1,c2という値を取ります。
c1 = (left*2 + right)//3
c2 = (left+right*2)//3
2. f(c1)とf(c2)の大小関係を比べ、
- もし、f(c1)の方が大きければlの値をc1に変更し
- もし、f(c2)の方が大きければlの値をc2に変更します
なぜこれで範囲を絞り込みできるのか？
なぜ、これで良いかというと、leftとrightは、そこが最小値でない限り、
f(left)>f(c1), f(right) > f(c2)が必ず成り立ちます。
- そこで、f(c1)> f(c2)の場合
f(left)>f(c1)>f(c2)となりますので、leftからc1の間には最小値が存在しないことがわかります。 - 同様に、f(c1) < f(c2)の場合は
f(right)>f(c2)>f(c1)となり、rからc2の間には最小値が存在しないことがわかります。
これにより、1回の操作で探索しなきゃいけない範囲を、2/3倍にすることができます。これにより、10**18であっても探索できます。
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
A,B = MI()
def check(c1,c2):
c1_time = A/((c1+1)**0.5) + B*(c1)#c1回操作をしたときの到着時間
c2_time = A/((c2+1)**0.5) + B*(c2)#c2回操作をしたときの到着時間
if c1_time - c2_time > 0:#f(c1) > f(c2)の場合は
return True
elif c2_time - c1_time >= 0:#f(c2) > f(c1)の場合は
return False
#操作回数(x)の最小の操作回数は0回、最大で10**18回
left, right = 0, 10**18
while right - left > 3:#三分探索法の場合、範囲が3以上じゃないと三分割できないので、範囲が3よりも大きければ
c1 = (left*2 + right)//3#三分割するためのc1
c2 = (left+right*2)//3#三分割するためのc2
if check(c1,c2):#f(c1) > f(c2)の場合
left = c1
else:#f(c1) < f(c2)の場合
right = c2
ans = 10**18
for i in range(left,right+1):#leftからrightの範囲が3以下になったら、leftからrightの範囲を全探索
arrive_time = A/((i+1)**0.5) + B*(i)
ans = min(arrive_time,ans)
print(ans)
コメント