Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02936 (python)

Fixed submission:
# 木全体の根が決まっているのでふつうにbfsでいい気がするが...
# 毎回探索するんじゃなくて、各枝にポイントをつけておいて、探索するときに1回だけ渡して更新していく
# 考え方は累積和
# なんかafter_contestってテストケースでハネられるんだが。。。。。なんだこれ
# i<jのときiのほうが根に近い、というのを決め打ちしても通ってしまう防止らしい
# 回避するべく
# 両方のノードからエッジを貼り(graph[b].append(a))、
# 探索のときに訪問済みの場所は抜くことにした(if node not in used:)

n, q = map(int, input().split())
graph = [[] for _ in range(n)]
points = [0 for _ in range(n)]

for _ in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)

for _ in range(q):
    p, x = map(int, input().split())
    points[p - 1] += x

path = [0]
used = set()
used.add(0)
while len(path) > 0:
    cur_node = path.pop()
    cur_point = points[cur_node]
    for node in graph[cur_node]:
        if node not in used:
            used.add(node)
            points[node] += cur_point
            path.append(node)
print(" ".join(list(map(str, points))))

Buggy submission (verdict: Runtime Error):
# クエリはまとめてしまえ

n, q = map(int, input().split())
ki = [[] for i in range(n)]

def union(a, b):
  # aの子供
  ki[a].append(b)

for i in range(n-1):
  a, b = map(int, input().split())
  union(a-1, b-1)

table = {}
for _ in range(q):
  p, x = map(int, input().split())
  if p-1 not in table:
    table[p-1] = x
  else:
    table[p-1] += x
ans = [0 for _ in range(n)]


def f(k, v, b):
  if len(ki[k])>0:
    # 自分自身
    if b == False:
      ans[k] += v
    for x in ki[k]:
      ans[x] += v
    for x in ki[k]:
      # 再起するときのマーク
      f(x, v, True)
  else:
    if b == False:
      ans[k] += v
for k, v in table.items():
  f(k, v, False)

print(" ".join(list(map(str, ans))))
Problem p02947 (python)

Fixed submission:
# じゃあ全部保存していってやるよ
# atcoderのpython3のバージョンが古すぎて(3.4.3)TypeError: unhashable type: 'list'なるのでため息つきながら直した

n = int(input())
d = {}
arr = []
for _ in range(n):
    x = "".join(list(map(str, list(sorted(input())))))
    arr.append(x)
    if x not in d:
        d[x] = 1
    else:
        d[x] += 1

c = 0
for a in arr[:0:-1]:
    if d[a] > 0:
        c += d[a] - 1
        d[a] -= 1

print(c)

Buggy submission (verdict: Runtime Error):
# じゃあ全部保存していってやるよ
n = int(input())
d = {}
arr = []
for _ in range(n):
    x = list(sorted(input()))
    arr.append(x)
    if x not in d:
        d[x] = 1
    else:
        d[x] += 1

c = 0
for a in arr[:0:-1]:
    if d[a] > 0:
        c += d[a] - 1
        d[a] -= 1

print(c)

Buggy submission (verdict: Runtime Error):
# じゃあ全部保存していってやるよ
n = int(input())
d = {}
arr = []
for _ in range(n):
    x = list(sorted(input()))
    arr.append(x)
    if x not in d:
        d[x] = 1
    else:
        d[x] += 1

c = 0
for a in arr[:0:-1]:
    if d[a] > 0:
        c += d[a] - 1
        d[a] -= 1

print(c)

Buggy submission (verdict: Runtime Error):
# 前の提出だとTLEなっちゃった
# じゃあ全部保存していってやるよ
n = int(input())
d = {}
arr = []
for _ in range(n):
    x = list(sorted(input()))
    arr.append(x)
    if x not in d:
        d[x] = 1
    else:
        d[x] += 1

c = 0
for a in arr[:0:-1]:
    if d[a] > 0:
        c += d[a] - 1
        d[a] -= 1

print(c)
Problem p03047 (python)

Fixed submission:
# 最初にKとるとすると残りはN-K個ぶん進める

n, k = map(int, input().split())
print(n-k+1)

Buggy submission (verdict: Runtime Error):
# 1. 両端にaもbも含まれないもしくは「先頭がaで末尾がb」は分けて考える 最後にテキトーに加えてやる
# 2. 「先頭がb」「末尾がa」「先頭がbで末尾がa」
# cca
# caa
# bac
# bbc
# bccca < -これは連結したほうがよさそう連結したあとに左にooa右にbooを加える
# あまったooaとbooで適当にくっつける
n = int(input())
ans = 0
both = 0
a, b = 0, 0
for _ in range(n):
    s = input()
    if s[0] != "B" and s[-1] != "A":
        ans += s.count("AB")
    else:
        if s[0] == "B" and s[-1] == "A":
            both += 1
            ans += s.count("AB")
        elif s[0] == "B":
            b += 1
            ans += s.count("AB")
        elif s[-1] == "A":
            a += 1
            ans += s.count("AB")
# 両脇にあるやつを連結
if both > 0:
    ans += both - 1
    # 連結したやつの先頭に加えられたら加える
    if a > 0:
        ans += 1
        a -= 1
    # 同じく末尾
    if b > 0:
        ans += 1
        b -= 1
# 余ったやつで作成
ans += min(a, b)
print(ans)

Buggy submission (verdict: Runtime Error):
# R*r + G*g + B*b == N の数
R, G, B, N = map(int, input().split())
R, G, B = list(sorted([R, G, B], reverse=True))
ans = 0
for r in range(N + 1):
    for g in range(N + 1):
        if (N - (r * R + g * G)) % B != 0:
            continue
        b = (N - (r * R + g * G))/B
        if b < 0:
            break
        if r * R + g * G + b * B == N:
            ans += 1
        elif r * R + g * G + b * B > N:
            break

print(ans)
Problem p03087 (python)

Fixed submission:
n, m = map(int, input().split())
s = input()
imos = [0 for _ in range(n)]
for i in range(1, n):
    if s[i-1] == "A" and s[i] == "C":
        imos[i] = imos[i-1]+1
    else:
        imos[i] = imos[i - 1]
for _ in range(m):
    l, r = map(int, input().split())
    if l > 1:
        print(imos[r-1]-imos[l-1])
    else:
        print(imos[r-1])

Buggy submission (verdict: Runtime Error):
# 累積和
n, q = map(int, input().split())
s = input()
arr = [0] * (2 * 10**5 + 10)
idx = 1
while idx <= len(s):
    if s[idx - 1] == "A" and s[idx] == "C":
        arr[idx] += 1
    idx += 1
for i in range(1, len(arr)):
    arr[i] += arr[i - 1]
for _ in range(q):
    l, r = map(int, input().split())
    print(arr[r - 1] - arr[l - 1])

Buggy submission (verdict: Runtime Error):
# 累積和
n, q = map(int, input().split())
s = input()
arr = [0] * (len(s) + 1)
idx = 1
while idx <= len(s):
    if s[idx - 1] == "A" and s[idx] == "C":
        arr[idx] += 1
    idx += 1
for i in range(1, len(arr)):
    arr[i] += arr[i - 1]
for _ in range(q):
    l, r = map(int, input().split())
    print(arr[r - 1] - arr[l - 1])
Problem p03160 (python)

Fixed submission:
n = int(input())
arr = list(map(int, input().split()))
if n == 2:
    print(abs(arr[0] - arr[1]))
    exit()
dp = [10 ** 9 for _ in range(n)]
dp[0] = abs(arr[0] - arr[1])
dp[1] = min(abs(arr[2] - arr[0]), abs(arr[2] - arr[1]) + dp[0])

for i in range(3, n):
    dp[i - 1] = min(
        abs(arr[i] - arr[i - 1]) + dp[i - 2], abs(arr[i] - arr[i - 2]) + dp[i - 3]
    )

# dp[2] = min(abs(arr[3] - arr[2]) + dp[1], abs(arr[3] - arr[1]) + dp[0])
# dp[3] = min(abs(arr[4] - arr[3]) + dp[2], abs(arr[4] - arr[2]) + dp[1])
# dp[4] = min(abs(arr[5] - arr[4]) + dp[3], abs(arr[5] - arr[3]) + dp[2])

print(dp[-2])

Buggy submission (verdict: Runtime Error):
n = int(input())
f = list(map(int, input().split()))

def dp(i, cur):
  if i==n-1:
    return cur
  if i == n-2:
    cur += abs(f[i] - f[i+1])
    return dp(i+1, cur)
  else:
    return min(dp(i+1, cur + abs(f[i] - f[i+1])), dp(i+2, cur + abs(f[i] - f[i+2])))
print(dp(0, 0))
Problem p03162 (python)

Fixed submission:
# dp[i日目][i-1日目にどれを選んだか] = i日目までの最大の幸福度
import sys
sys.setrecursionlimit(10 ** 8)

n = int(input())
a, b, c = [0 for _ in range(n)], [0 for _ in range(n)], [0 for _ in range(n)]
for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())

dp = [[-1 for _ in range(3)] for _ in range(n + 1)]
for i in range(3):
    dp[0][i] = 0


def rec(i, choice):
    if dp[i][choice] > 0:
        return dp[i][choice]
    if i == n:
        return 0
    ret = 0  # ループじゃなくてifでやってるのでそれぞれ確実に大きい値が入る（ので更新する必要がない）
    if choice == 0:
        ret = a[i] + max(rec(i + 1, 1), rec(i + 1, 2))
    elif choice == 1:
        ret = b[i] + max(rec(i + 1, 0), rec(i + 1, 2))
    elif choice == 2:
        ret = c[i] + max(rec(i + 1, 0), rec(i + 1, 1))
    dp[i][choice] = ret
    return ret


print(max(rec(0, 0), rec(0, 1), rec(0, 2)))

Buggy submission (verdict: Runtime Error):
# dp[i日目][i-1日目にどれを選んだか] = i日目までの最大の幸福度
n = int(input())
a, b, c = [0 for _ in range(n)], [0 for _ in range(n)], [0 for _ in range(n)]
for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())

dp = [[-1 for _ in range(3)] for _ in range(n + 1)]
for i in range(3):
    dp[0][i] = 0


def rec(i, choice):
    if dp[i][choice] > 0:
        return dp[i][choice]
    if i == n:
        return 0
    ret = 0  # ループじゃなくてifでやってるのでそれぞれ確実に大きい値が入る（ので更新する必要がない）
    if choice == 0:
        ret = a[i] + max(rec(i + 1, 1), rec(i + 1, 2))
    elif choice == 1:
        ret = b[i] + max(rec(i + 1, 0), rec(i + 1, 2))
    elif choice == 2:
        ret = c[i] + max(rec(i + 1, 0), rec(i + 1, 1))
    dp[i][choice] = ret
    return ret


print(max(rec(0, 0), rec(0, 1), rec(0, 2)))
Problem p03231 (python)

Fixed submission:
# たぶん最小の値は最小公倍数になりそう
# 内包表記 -> TLE
# [0]*l -> RE

n, m = map(int, input().split())
s, t = input(), input()


def gcd(a, b):
    if b > a:
        return gcd(b, a)
    while a > 0:
        a, b = b % a, a
    return b


def lcm(a, b):
    return (a * b) // gcd(a, b)


l = lcm(n, m)
arr = {}

for i in range(n):
    x = i * (l // n)
    arr[x] = s[i]

for i in range(m):
    x = i * (l // m)
    if x in arr and arr[x] != t[i]:
        print(-1)
        exit()
print(l)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
s, t = list(input()), list(input())


def gcd(a, b):
    if a > b:
        return gcd(b, a)
    while a > 0:
        a, b = b % a, a
    return b


def lcm(a, b):
    return a * b // gcd(a, b)


l = lcm(len(s), len(t))
x = ["無"] * l
for i in range(0, len(s)):
    x[i * (l // len(s))] = s[i]
for i in range(0, len(t)):
    if x[i * (l // len(t))] == "無":
        continue
    else:
        if x[i * (l // len(t))] != t[i]:
            print(-1)
            exit()
print(l)

Buggy submission (verdict: Runtime Error):
# たぶん最小の値は最小公倍数になりそう

n, m = map(int, input().split())
s, t = input(), input()


def gcd(a, b):
    if b > a:
        return gcd(b, a)
    while a > 0:
        a, b = b % a, a
    return b


def lcm(a, b):
    return (a * b) // gcd(a, b)


l = lcm(n, m)
arr = [0] * l

for i in range(n):
    x = i * (l // n)
    arr[x] = s[i]

for i in range(m):
    x = i * (l // m)
    if arr[x] != 0 and arr[x] != t[i]:
        print(-1)
        exit()
print(l)
Problem p03241 (python)

Fixed submission:
# これはエスパーですがMが素数ならNが何であってもできなさそう？未証明
# で 合成数のみっぽいので定石的に素因数分解すると
# 各項に因数をどれだけ割り振れるかみたいになる？
# -> サンプル1をみるとならなそう
# 最大公約数をgcdとすると、a*gcd*(N-1)+b*gcd = M となるのが都合よさそう こうなると右辺もgcdで割れるのでやはり約数のどれかになりそう
n, m = map(int, input().split())


def make_divisors(n):
    lower_divisors = []
    upper_divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)

    upper_divisors.reverse()
    return lower_divisors + upper_divisors


if m % n == 0:
    print(m // n)
    exit()
else:
    x = m // n
    divisors = make_divisors(m)[::-1]
    for d in divisors:
        if d <= x:
            print(d)
            exit()

Buggy submission (verdict: Runtime Error):
# これはエスパーですがMが素数ならNが何であってもできなさそう？未証明
# で 合成数のみっぽいので定石的に素因数分解すると
# 各項に因数をどれだけ割り振れるかみたいになる？
# -> サンプル1をみるとならなそう
# 最大公約数をgcdとすると、a*gcd*(N-1)+b*gcd = M となるのが都合よさそう こうなると右辺もgcdで割れるのでやはり約数のどれかになりそう
n, m = map(int, input().split())


def enum_divisor(n):
    ret = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            ret.append(i)
    return ret


if m % n == 0:
    print(m // n)
    exit()
else:
    x = m // n
    # 要はx以下で最大のmの約数
    lis = sorted(enum_divisor(x), reverse=true)
    for l in lis:
        if l <= x:
            print(l)
            exit()

Buggy submission (verdict: Runtime Error):
# これはエスパーですがMが素数ならNが何であってもできなさそう？未証明
# で 合成数のみっぽいので定石的に素因数分解すると
# 各項に因数をどれだけ割り振れるかみたいになる？
# -> サンプル1をみるとならなそう
# 最大公約数をgcdとすると、a*gcd*(N-1)+b*gcd = M となるのが都合よさそう こうなると右辺もgcdで割れるのでやはり約数のどれかになりそう
n, m = map(int, input().split())


def enum_divisor(n):
    ret = []
    for i in range(1, int(n**0.5)):
        if n % i == 0:
            ret.append(i)
    return ret


if m % n == 0:
    print(m // n)
    exit()
else:
    x = m // n
    # 要はx以下で最大のmの約数
    lis = enum_divisor(x)
    print(lis[-1])
Problem p03251 (python)

Fixed submission:
# max min
n, m, x, y = map(int, input().split())
xs = max(list(map(int, input().split())))
ys = min(list(map(int, input().split())))

print("No War" if xs < ys and x <= xs and ys <= y else "War")

Buggy submission (verdict: Runtime Error):
# max min
n, m, x, y = map(int, input().split())
xs = max(list(map(int, input().split())))
ys = min(list(map(int, input().split())))
print("No War" if xs + 1 < ys else "War")
# max min
n, m, x, y = map(int, input().split())
xs = max(list(map(int, input().split())))
ys = min(list(map(int, input().split())))
print("No War" if xs + 1 <= ys else "War")
Problem p03316 (python)

Fixed submission:
# Nは最大9桁
n = input()
sn = 0
for ni in n:
    sn += int(ni)
if int(n) % sn == 0:
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
# Nは最大9桁
n = input()
sn = 0
for ni in n:
    sn += int(ni)
if n % sn == 0:
    print("Yes")
else:
    print("No")
Problem p03355 (python)

Fixed submission:
# 最小かつ最長はzzzzzなので各文字+4まで調べてみるか（27^5-1で全探索もできると思うがやり方がわからん
s = input()
k = int(input())
d = set()
for i in range(len(s)):
    for j in range(1, 6):
        if i + j <= len(s):
            d.add(s[i : i + j])
print(sorted(list(d))[k-1])

Buggy submission (verdict: Runtime Error):
,# 最大で5文字になりそうなので上位K個を保持しつつ全探索
s = input() + " "
k = int(input())
ans = []
for i in range(len(s)):
    for j in range(i + 1, min(len(s), i + 5 + 1)):
        t = "".join(s[i:j])
        if t not in ans:
            ans.append(t)
            ans = sorted(ans)[:6]
print(ans[k - 1])

Buggy submission (verdict: Runtime Error):
# 最大で5文字になりそうなので上位K個を保持しつつ全探索
s = input()
k = int(input())
ans = []
for i in range(len(s)):
    for j in range(i + 1, min(len(s), i + 5 + 1)):
        t = "".join(s[i:j])
        if t not in ans:
            ans.append("".join(s[i:j]))
            ans = sorted(ans)[:5]
print(ans[k - 1])
Problem p03380 (python)

Fixed submission:
# nCr的にn//2に近いほうがいいに決まっている
# まあnCrは計算しなくていい

n = int(input())
arr = sorted(list(map(int, input().split())))


def lower_bound(arr, t):
    l, r = 0, len(arr)
    while l < r:
        mid = (l + r) // 2
        if arr[mid] < t:
            l = mid + 1
        else:
            r = mid
    return l


lb = lower_bound(arr[:-2], round(arr[-1] / 2))
lb_left = max(0, lb - 1)
if abs(round(arr[-1] / 2) - arr[lb]) >= abs(round(arr[-1] / 2) - arr[lb_left]):
    print(arr[-1], arr[lb_left])
else:
    print(arr[-1], arr[lb])

Buggy submission (verdict: Runtime Error):
# nCr的にn//2に近いほうがいいに決まっている
# まあnCrは計算しなくていい

n = int(input())
arr = sorted(list(map(int, input().split())))


def lower_bound(arr, t):
    l, r = 0, len(arr)
    while l < r:
        mid = (l + r) // 2
        if arr[mid] < t:
            l = mid + 1
        else:
            r = mid
    return l


lb = lower_bound(arr[:-2], arr[-1] // 2)
lb_left = max(0, lb - 1)
if lb == lb_left:
    raise ValueError("omg")
if arr[lb] <= arr[lb_left]:
    print(arr[-1], arr[lb_left])
else:
    print(arr[-1], arr[lb])
Problem p03393 (python)

Fixed submission:
from string import ascii_lowercase
alphabets = ascii_lowercase
s = input()
if len(s) < len(alphabets):
    for c in alphabets:
        if c not in s:
            print(s + c)
            exit()
if s == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
    exit()

# 14253 next 143,  54213 next 5423, 35421 next 4, 43521 next 45
# 右端からみてi-1, iを比較して減少(S[i]>S[i-1])してたらi-1を基準に切り替える
# 切り替えるのは勘だけどi-1より右側でi-1より大きい最小のやつ？
for i in range(len(s) - 1, 0, -1):
    if s[i] > s[i - 1]:
        t = []
        for j in range(i, len(s)):
            if s[i - 1] < s[j]:
                t.append(s[j])
        x = min(t)
        print(s[:i - 1] + x)
        exit()

Buggy submission (verdict: Runtime Error):
from string import ascii_lowercase

s = input()
d = dict(zip(ascii_lowercase, [0 for _ in range(len(ascii_lowercase))]))

for c in s:
    d[c] += 1

if len(s) < 26:
    for k, v in d.items():
        if v == 0:
            print(s + k)
            exit()
elif s == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
    exit()

idx = -1
for i in range(1, len(s)):
    if s[i] > s[i + 1]:
        idx = i
        break
check = dict(zip(ascii_lowercase, [False for _ in range(len(ascii_lowercase))]))
for i in range(idx):
    check[s[i]] = True
i = 0
for c, v in check.items():
    if v == False:
        print(s[: i - 1] + c)
        exit()
    i += 1

Buggy submission (verdict: Runtime Error):
from string import ascii_lowercase

s = input()
d = dict(zip(ascii_lowercase, [0 for _ in range(len(ascii_lowercase))]))
nex = ""
for c in s:
    d[c] += 1

if len(s) < 26:
    for k, v in d.items():
        if v == 0:
            print(s + k)
            exit()
elif s == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
    exit()

idx = -1
for i in range(1, len(s)):
    if s[i] > s[i + 1]:
        idx = i
        break
check = dict(zip(ascii_lowercase, [False for _ in range(len(ascii_lowercase))]))
for i in range(idx):
    check[s[i]] = True
i = 0
for c, v in check.items():
    if v == False:
        print(s[: i - 1] + c)
        exit()
    i += 1

Buggy submission (verdict: Runtime Error):
from string import ascii_lowercase

s = input()
d = dict(zip(ascii_lowercase, [0 for _ in range(len(ascii_lowercase))]))
nex = ""
for c in s:
    d[c] += 1

if len(s) < 26:
    for k, v in d.items():
        if v == 0:
            print(s + k)
            exit()
elif s == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
    exit()

idx = -1
for i in range(1, len(s)):
    if s[i] > s[i + 1]:
        idx = i
        break
check = dict(zip(ascii_lowercase, [False for _ in range(len(ascii_lowercase))]))
for i in range(idx):
    check[s[i]] = True
i = 0
for c, v in check.items():
    if v == False:
        print(s[: i - 1] + c)
        exit()
    i += 1
Problem p03427 (python)

Fixed submission:
# 9or8で埋めたやつが強い あるいはオリジナル
# 桁を一つ落として（1なら9999...）残りを9で埋める
# オリジナルはたとえば199とかのとき19が最大になる

s = input()
tmp = 0
for i in s:
    tmp += int(i)
if s[0] == "1":
    print(max(9 * (len(s) - 1), tmp))
else:
    print(max(int(s[0]) - 1 + 9 * (len(s) - 1), tmp))

Buggy submission (verdict: Runtime Error):
# 9or8で埋めたやつが強い あるいはオリジナル
# 桁を一つ落として（1なら9999...）残りを9で埋める
# オリジナルはたとえば199とかのとき19が最大になる

s = input()
tmp = 0
for i in s:
    tmp += int(i)
if s[0] == "1":
    print(max(9 * (len(s) - 1), tmp))
else:
    print(int(max(s[0]) - 1 + 9 * (len(s) - 1), tmp))
Problem p03436 (python)

Fixed submission:
# #の数を数えておいて、最初の.の数-最短距離
# 最短経路なので幅優先でやる
from collections import deque

h, w = map(int, input().split())
table =[]
default_dot = 0
for _ in range(h):
  line = list(input())
  default_dot+=line.count(".")
  table.append(line)

default_dot-=2  # スタートとゴール
table[0][0] = 0

cur = [0, 0]   # x, y
queue = deque()
queue.append(cur)
steps = [0, 1, 0, -1, 0]

minimum_step = 0

while True:
  if len(queue)==0:
    print(-1)
    exit()
  now = queue.popleft()
  if now[0] == w-1 and now[1] == h-1:
    minimum_step = table[now[1]][now[0]]-1
    break
  for i in range(4):
    next_y, next_x = now[1]+steps[i], now[0]+steps[i+1]
    if 0<=next_y<h and 0<=next_x<w and table[next_y][next_x] == ".":
      table[next_y][next_x] = table[now[1]][now[0]]+1
      queue.append([next_x, next_y])


print(default_dot-minimum_step)

Buggy submission (verdict: Runtime Error):
# 最短でゴールして残った黒をぜんぶ白に変えれば最大のポイントをもらえそう
# ってなふうに雑に考えてたけど、探索・最短経路復元・解答それぞれで1度ずつBFSをしなきゃならんのか？？？？

h, w = map(int, input().split())
table = [[] for _ in range(h)]
for y in range(h):
    table[y] = list(input())
# ステップ更新用
my_table = [[-1 for _ in range(w)] for _ in range(h)]
my_table[0][0] = 0
yo = [(0, 0)]
steps = [0, -1, 0, 1, 0]
while len(yo) > 0:
    p = yo[0]
    yo = yo[1:]
    for i in range(4):
        next_x, next_y = steps[i + 1] + p[1], steps[i] + p[0]
        if next_x < 0 or w <= next_x or next_y < 0 or h <= next_y:
            continue
        if table[next_y][next_x] == "#":
            continue
        if my_table[next_y][next_x] >= 0:
            continue
        my_table[next_y][next_x] = my_table[p[0]][p[1]] + 1
        yo.append((next_y, next_x))

# 経路を逆からたどって最短経路復元
restore_table = [["o" for _ in range(w)] for _ in range(h)]
restore_table[h - 1][w - 1] = "x"
now = my_table[h - 1][w - 1]
cur = (h - 1, w - 1)
while now != 0:
    for i in range(4):
        next_y, next_x = steps[i] + cur[0], steps[i + 1] + cur[1]
        if next_x < 0 or w <= next_x or next_y < 0 or h < next_y:
            continue
        if my_table[next_y][next_x] == now - 1:
            restore_table[next_y][next_x] = "x"
            cur = (next_y, next_x)
            now -= 1
            break

# やっと答え
ans = 0
for y in range(h):
    for x in range(w):
        if restore_table[y][x] == "o" and table[y][x] == ".":
            ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
# #の数を数えておいて、x*y-(最短距離+最初の#の数）
# 最短経路なので幅優先でやる
from collections import deque

h, w = map(int, input().split())
table =[]
default_dot = 0
for _ in range(h):
  line = list(input())
  default_dot+=line.count(".")
  table.append(line)

default_dot-=2  # スタートとゴール
table[0][0] = 0

cur = [0, 0]   # x, y
queue = deque()
queue.append(cur)
steps = [0, 1, 0, -1, 0]

minimum_step = 0

while True:
  now = queue.popleft()
  if now[0] == w-1 and now[1] == h-1:
    minimum_step = table[now[1]][now[0]]-1
    break
  for i in range(4):
    next_y, next_x = now[1]+steps[i], now[0]+steps[i+1]
    if 0<=next_y<h and 0<=next_x<w and table[next_y][next_x] == ".":
      table[next_y][next_x] = table[now[1]][now[0]]+1
      queue.append([next_x, next_y])


print(default_dot-minimum_step)
Problem p03447 (python)

Fixed submission:
x, a, b = int(input()), int(input()), int(input())
x-=a

print(x%b)

Buggy submission (verdict: Runtime Error):
n, m = list(map(int, input().split()))
par = list(range(n+1))
dis = [0] * (n+1)

def root(x):
  if x == par[x]:
    return x
  r = root(par[x])
  dis[x] += dis[par[x]]
  par[x] = r
  return r

def cost(x):
  # xからxの根までのコスト
  if x == par[x]:
    return 0
  return dis[x] + cost(par[x])

for _ in range(m):
  l, r, d = list(map(int, input().split()))
  # 根が違ってればマージ
  # 同じなら入力されたdistanceがこれまでの入力データからなる
  # 現在の木の構造から計算した数値とあっているか判断
  rootl, rootr = root(l), root(r)
  if rootl != rootr:
    # lをrにマージする
    if r == rootr:
      dis[rootl] = d - cost(l)
    else:
      dis[rootl] = d - (dist[x] - dist[y]) # (cost(l) - cost(r))
    par[rootl] = r
  else:
    # コストが同じかどうか
    if d == cost(l) - cost(r):
      continue
    else:
      print("No")
      exit()
print("Yes")
Problem p03479 (python)

Fixed submission:
x, y = map(int, input().split())
ans = 0 if x>y else 1
while x*2<=y:
    ans+=1
    x=x*2
print(ans)

Buggy submission (verdict: Runtime Error):
x, y = map(in
t, input().split())
ans = 0 if x>y else 1
while x*2<=y:
    ans+=1
    x=x*2
print(ans)
Problem p03504 (python)

Fixed submission:
# N個のimosなので二次元でやる 0.5がうざいので*2する( (2*10^5) * C )

# なぜか2WAが取れない

# これ嘘解法ぽい気がする

N, C = map(int, input().split())
x = 2 * (10**5)
# x = 30  # test
imos = [[0 for _ in range(x)] for _ in range(C)]
for _ in range(N):
    s, t, c = map(int, input().split())
    s, t, c = s * 2 - 1, t * 2 - 1, c - 1
    imos[c][s - 1] += 1
    imos[c][t] -= 1
    # imos[c][s - 1] = min(1, imos[c][s - 1])  # test

for i in range(C):
    for j in range(1, x):
        imos[i][j] += imos[i][j - 1]
        # imos[i][j] = min(1, imos[i][j])  # test

ans = 0
for j in range(x):
    tmp = 0
    for i in range(C):
        tmp += min(1, imos[i][j])
    ans = max(ans, tmp)
# print("-----------")
# for x in imos:
#     print(x)
print(ans)

# 1 3
# 3 4 2

Buggy submission (verdict: Runtime Error):
# N個のimosなので二次元でやる 0.5がうざいので*2する( (2*10^5) * C )

N, C = map(int, input().split())
x = 2 * (10 ** 5)

imos = [[0 for _ in range(x)] for _ in range(C)]
for _ in range(N):
    s, t, c = map(int, input().split())
    s, t, c = s * 2, t * 2, c - 1
    imos[c][s - 1] += 1
    imos[c][t] -= 1


for i in range(C):
    for j in range(1, x):
        imos[i][j] += imos[i][j - 1]

ans = 0
for j in range(x):
    tmp = 0
    for i in range(C):
        tmp += imos[i][j]
    ans = max(ans, tmp)

print(ans)

Buggy submission (verdict: Runtime Error):
# N個のimosなので二次元でやる 0.5がうざいので*2する( (2*10^5) * C )

N, C = map(int, input().split())
x = 2 * (10 ** 5)

imos = [[0 for _ in range(x)] for _ in range(C)]
for _ in range(N):
    s, t, c = map(int, input().split())
    s, t, c = s * 2, t * 2, c - 1
    imos[c][s - 1] += 1
    imos[c][t] -= 1


for i in range(C):
    for j in range(1, x):
        imos[i][j] += imos[i][j - 1]

ans = 0
for j in range(x):
    tmp = 0
    for i in range(C):
        tmp += imos[i][j]
    ans = max(ans, tmp)

print(ans)