Study

AtCorder 253

AtCorder 253に参加しました。

A, Bしか解けませんでした・・・orz

まるで成長していない・・・

6月まではあまり時間がとれず、参加するだけなので当たり前と言えば当たり前ですが・・・ 来月からはちゃんと競プロの勉強をやっていきたいですね。

参考にする回答はこちら
https://qiita.com/u2dayo/items/b8caf7bb051eff5097ce

【A】 Median?

提出したコードはこちら

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

if a <= b <= c or c <= b <= a:
    print("Yes")
else:
    print("No")

1回間違った回答を提出してしまいました。中央値って同値がある場合は無効だと思っていました。

まだペナルティや回答時間を気にするレベルではないので、別に問題ないのですが。。。

【B】 Distance Between Tokens

提出したコードはこちら

H, W = map(int, input().split())
S = [input() for _ in range(H)]

koma1 = []
koma2 = []
for i, v in enumerate(S):
    for j, vv in enumerate(v):
        if vv == 'o':
            if koma1 == []:
                koma1 = [i, j]
            else:
                koma2 = [i, j]
                break

print(abs(koma1[0] - koma2[0]) + abs(koma1 - koma2))

考え方自体は問題なさそうです。ちょっとコードが汚いですが。。。

誤答はありませんでしたが、問題の意味を理解するのにちょっと時間がかかりました。

A,B完了時点で15分ほど使っていました。

【C】 Max – Min Query

かなり時間をつかったのですが、正解にいたりませんでした。コードを1回も提出することができなかったです。

途中まで考えていたコードはこちら

import math

Q = int(input())
querys = [(input()) for i in range(Q)]

s_min = math.inf
s_max = 0
s_value_counts = {}  # key: s value, v: counts
for q in querys:
    q_type = int(q.split(' ')[0])
    if q_type == 1:
        new_value = int(q.split(' '))
        s_min = min(s_min, new_value)
        s_max = max(s_max, new_value)
    elif q_type == 2:
        x = int(q.split(' '))
        # xがs_min/s_maxと同値で全部消してしまった場合、s_min/s_maxの更新が必要
        # -> 次点の値をどうやってもってくる?
    else:
        print(s_max - s_min)

print(s_min)
print(s_max)

全探索だとTLEは明らかだったので、各数値の情報を別配列に持たせる方法を考えたのですが、手詰まりになりました。

解説によると、順序付き多重集合という概念があったんですね。知りませんでした。

とりあえず解説が用意してくれたライブラリをコピっておきました。後で使えるようにしておきます。

【D】FizzBuzz Sum Hard』

C問題が解ける気がしなかったので、22時過ぎからはD問題にトライしました。

こちらは何度も提出したのですが、WAまみれで結局、正解にはいたりませんでした。

提出していたコードはこちら

N, A, B = map(int, input().split())


def calc(n, a, b):
    total = n * (n + 1) / 2
    total_a = 0
    total_b = 0
    total_ab = 0
    for i in range(n // a + 1):
        total_a += i * a

    if a == b:
        total_b = 0
        total_ab = 0
    else:
        for i in range(n // b + 1):
            total_b += i * b

        for i in range(n // (a * b) + 1):
            total_ab += i * a * b

    ans = int(total - total_a - total_b + total_ab)
    if ans < 0:
        ans = 0
    return ans


print(calc(N, A, B))

# assert calc(10, 3, 5) == 22
# assert calc(1, 3, 5) == 1
# assert calc(1, 1, 1) == 0
# assert calc(1, 1, 2) == 0
# assert calc(10, 2, 3) == 13
# assert calc(10, 1, 1) == 0
# assert calc(10, 1, 10) == 0
# assert calc(10, 11, 12) == 55
# assert calc(10, 11, 10) == 45
# assert calc(10, 10, 1000) == 45
# print(calc(10,10,10))
# assert calc(10, 10, 10) == 45

何のアルゴリズムを使うべきなのかわかりませんでしたが、数学的アプローチでできそうなのでやってみましたが、ダメでした。
WAになるケースが思い浮かばず、時間切れとなりました。

で、今この文章を書いていていてわかりました。A, Bが互いに素か同値のケースしか想定していなかったですね・・・ 何か学生の時のテストが終わった後に答えがわかった!みたいな感じです。まあこれが分かったところで、コードに落とし込めていたかどうか、わかりませんが・・・

最小公倍数は、

lcm = (A * B) // gcd(A, B)

とやって、簡単に出せるんですね。知りませんでした。最小公倍数をLCM, 最大公約数をGCDというのも知りませんでした。

まとめ

最近はCまでできていたので、最低限はできてるいるからとりあえずいいかなと油断していました。またA,Bだけを解く参加するだけの人になってしまいました。

どこかでがっつり時間とって、AtCorderの過去問を解きまくるとかやりたいですね。でも、それは時間的にも脳の体力的にも無理なので、時間があるときにコツコツやっていこうと思います。