AtCoder Beginner Contest 131の感想

今回は比較的簡単だったような気がした(E,Fは相変わらずだったけど)

A問題(1WA, 1分56秒)

方針

1と2, 2と3, 3と4文字目を見比べる。

コード

n = input()

flag = 0
for i in range(3):
  if(n[i] == n[i+1]):
    flag = 1
  if(flag == 1):
    print("Bad")
    break
if(flag == 0):
  print("Good")

最初n=int(input())ってテンプレをそのままコピってREになった。マジでもったいない

B問題(6分9秒)

方針

Lの正負で場合分け。Lが正ならmin(i+l-1 for i in range(n))、Lが負ならもしも最大が0超えるなら0、超えないならmax(i+l-1 for i in range(n))をひく

コード

n, l = [int(i) for i in input().split()]
num = 0
a = []
for i in range(n):
  num += i + l
  a.append(i+l)
if(l >= 0):
  ans = num - min(a)
  print(ans)
else:
  if(max(a) >= 0):
    print(num)
  else:
    ans = num - max(a)
    print(ans)
    

問題文の意味がわからなくて3分くらいロスしたので悲しい。日本語の読解力衰えたなあって思ってしまう。

C問題(13分24秒)

方針

最近算数の問題を出すのが好きですね。n以下のaとbの約数以外の個数はn - n//a - n//b + n // lcm(a, b)と表されます。

コード

a, b, c, d = [int(i) for i in input().split()]

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

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

def count(a, b, c):
    d = a // b
    e = a // c
    f = a // lcm(b, c)
    return a - d - e + f
ans = count(b, c, d) - count(a, c, d)
if(a % c != 0 and a % d != 0):
    ans += 1
print(ans)

備考

aがcまたはdの約数でないときはその分も足さなければいけないことに注意。

D問題(35分42秒)

方針

bで昇順ソート→同じだったらaで降順ソートしたのちに1つずつ加算し、b[i]と比較。O(n)で実行可能。

コード

n = int(input())
task = []
amount = 0
for i in range(n):
    a, b = [int(i) for i in input().split()]
    amount += a
    task.append([a, b])
task_1 = sorted(task, key=lambda x:(x[1], -x[0]))
limit = task_1[n-1][1]
frag = 0
now = 0
if(amount > limit):
    frag = 1
else:
    for i in range(n):
        now += task_1[i][0]
        if(task_1[i][1] < now):
            frag = 1
        if(frag == 1):
            break
if(frag == 1):
    print("No")
else:
    print("Yes")

反省

sortedって非破壊的ソートを使ったけど競プロだったらsortで破壊したほうが紛らわしくなくていいのかなあと。実際そのせいで一回間違えたりしたので。

まとめ

4完(1WA, 57分11秒)。順位は1981位でレートは493→563でした。E,Fの問題は知識量が少なく方針が立てられなかったのでこれからはE, Fを解くことを目標として蟻本で引き続いて勉強をしていきます。