AtCoder ABC3週目参戦日記

スポンサーリンク
日記
スポンサーリンク

AtCoderのABCも3回目(AtCoder Beginner Contest 259)の挑戦になりました。前回、3問正解できたので、今回も3問、できれば、4問正解したいと思って臨んだ今回ですが、、、結果は2問しかで正解できませんでした。3問目はそもそもの考え方が間違っていて、WA二つを時間内に解消することができませんでした。翌日、リフレッシュな頭で考えたら、大きな思い違いをしていることに気づいたのですが、なかなか競技時間中は気づけないものです。Ratingについては、早くも100台の前半に収束しそうな様相を見せています(;^_^A参加にも慣れてきたし、来週は頑張って、3問は安定して正解したいところです。

A – Growth Record

場合分けと算数の問題でした。でも、この問題でも7分もかかっているんですね。A問題はサクッと早く答えが出せるようになりたいものです。

n, m, x, nt, d = [int(i) for i in input().split()]
 
if m > x :
    mt = nt
else:
    mt = nt - (x - m)*d
print(mt)

B – Counterclockwise Rotation

回転の問題でしたが、こちらは高校数学の問題でした。sin, cos, tanなんて久しく使うことがなかったのですが、頭の片隅にnumpyで三角関数が使えたような記憶があったので、それをネット検索で引っ張り出して使ってみました。あとから調べたら、numpyを使わなくても、標準のmathでも同様の計算ができるみたいですね。最初、PyPy3で提出したら、RE(実行時エラー)で不正解。そういえば、numpyはPyPy3では使えないという話も聞いたような気がするので、再度、Python3で提出したら問題なくACをいただけました。

今回は入力例がたくさんあって助かりました。arctan2(x, y)かと思ったら、arctan2(y, x)が正解だというのをチェックで確認出来て、間違いは未然に防ぐことができました。

import numpy as np
# np.radians()
# np.sin()
# np.cos()
# np.arctan2()

a, b, d = [int(i) for i in input().split()]
alpha = np.arctan2(b, a)
kaku = alpha + np.radians(d)
r = (a**2 + b**2)**(1/2)

print(r*np.cos(kaku), r*np.sin(kaku))

C – XX to XXX

間違いを直せず、時間切れでアウトでした。冷静に考えれば、簡単だったんですが。提出した結果、AC30個でWA2個でした。何か自分のアルゴリズムで例外となっているものがあるのかもしれないと思って考えましたが、結局分かりませんでした。翌日考えたらSの方が文字の連続が長い場合も、「Yes」になってしまう間違ったアルゴリズムになっていました。問題文に忠実な方向からやっていけば良かった、問題でした。

正答

def answer(s, t):
    if (len(s) == 1) or (len(t)== 1):
        if s == t:
            return True
        else:
            return False
    sc = s[0]+s[1]
    
    j = 2
    for i in range(2, len(t)):
        if (j < len(s)) and (s[j] == t[i]):
            sc += t[i]
            j += 1
        elif (s[j-2] == t[i]) and (s[j-1] == t[i]):
            sc += t[i]
        else:
            return False
 
    add_end = len(t) - len(sc)
    if add_end > 0:
        sc = sc + s[-1]*add_end
 
    if sc == t:
        return True
    else:
        return False
 
s = input()
t = input()
 
if answer(s, t):
    print('Yes')
else:
    print('No')

誤答

def answer(s, t):
    if (len(s) == 1) or (len(t)== 1):
        if s == t:
            return True
        else:
            return False
    sc = s[0]+s[1]
    tc = t[0]+t[1]
    
    for i in range(2, len(s)):
        if (s[i-1]==s[i]) and (s[i-2]==s[i]):
            a = 1
        else:
            sc += s[i]
    for j in range(2, len(t)):
        if (t[j-1]==t[j]) and (t[j-2]==t[j]):
            a = 1
        else:
            tc += t[j]
    # print(sc)
    # print(tc)
 
    if sc == tc:
        return True
    else:
        return False
 
s = input()
t = input()
 
if answer(s, t):
    print('Yes')
else:
    print('No')

最後に

D問題を見たのですが、解けるような気がしない問題でした。経路探索のアルゴリズムが必要なのかも。そういったアルゴリズムの勉強をしないと、先の難しい問題は解けそうにありません。少しずつでも上にいきたいと思います。

日記
スポンサーリンク
鷹の目週末プログラマー

コメント