AtCorder 253｜タムタムのアウトプット

AtCorder 253に参加しました。

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

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

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

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

Contents

【A】 Median?
【B】 Distance Between Tokens
【C】 Max – Min Query
【D】FizzBuzz Sum Hard』
まとめ

【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が互いに素か同値のケースしか想定していなかったですね・・・何か学生の時のテストが終わった後に答えがわかった！みたいな感じです。まあこれが分かったところで、コードに落とし込めていたかどうか、わかりませんが・・・

最小公倍数は、