コンテスト
A問題
感想
3回バグらせて、割とすぐにACできた。
DFS,BFSの亜種。
した。
最終のバグコード。
bを前回値として、単調増加の検査をしようと思ったが、bの値を検査できていないことに気づき、条件式をコピペしてきた。なんとも見栄えが悪い感じになり、どこでWAになっているのか分からず。条件式もYesの逆を判定することになり、複雑に。
def main():
S = list(map(int, input().split()))
b = S[0]
if 100 > b and b > 675:
実装していないので、机上のクーロン。
print("No")
exit()
if b % 25 != 0:
print("No")
exit()
for si in S[1:]:
if b > si:
print("No")
exit()
if 100 > si and si > 675:
print("No")
exit()
if si % 25 != 0:
print("No")
exit()
b = si
print("Yes")
main()
問題文を見ると、Sは8個しかないのでいくらでもfor文を回せる。なので、それぞれの条件ごとに別のfor文を回す。条件式は素直に問題文通りに書いた。こちらの方が認知的負荷が低い。
def main():
S = list(map(int, input().split()))
for si in S:
if 100 <= si <= 675:
pass
else:
print("No")
exit()
if si % 25 == 0:
pass
else:
print("No")
exit()
for i in range(len(S)-1):
if S[i] <= S[i+1]:
pass
else:
print("No")
exit()
print("Yes")
反省点
- 問題文の条件式はできるだけそのままの形で書く。変に逆を取ろうとしない。
- 計算量に余裕があるときは、性質の違うfor文は別で回す。今回は、「それぞれの値に関する条件」と「値の前後関係」という2つの性質のもその同時に判定しようとしてた。
B問題
感想
辞書を使って皿の色と値段を一致させた。
値段を計算する時、keyの中に辞書に登録した文字列があれば、その値段を使い、なければP0を使う。
import sys
import itertools
import math
import collections
import bisecet
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**18
def main():
N, M = list(map(int, input().split()))
C = list(input().split())
D = list(input().split())
P = list(map(int, input().split()))
P0 = P[0]
del P[0]
price = collections.defaultdict(int)
for d, p in zip(D, P):
price[d] = p
co = collections.Counter(C)
s = 0
for ci, n in co.items():
if ci in price.keys():
s += price[ci]*n
else:
s += P0*n
print(s)
main()
C問題
感想
ACできなかった。
書いたコードは以下のような感じ。
a/(a+b)がfloatになるので、比較の時に誤差が出て大小をうまく判定できてないのかな〜と思いつつ、打開案を出せなかった。
そもそもfloatで誤差が出るのはどんな時なのか正確に認識できていないというのもある。
pythonでACしたコードを見てみると、functoolsのcmp_to_keyを使って分母を払いつつ、整数で比較する方法とDecimal型を使う方法があるみたいだった。
import sys
import itertools
import math
import collections
import bisectで探索する分には4\*\*
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**18
def main():
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
t = []
for i, (a, b) in enumerate(AB):
t.append([a/(a+b), N-i, i])
t.sort(reverse=True)
for ti in t:
print(ti[2]+1)
main()
反省点
- float型で出る誤差を理解する
- functoolsのcmp_to_keyを使えるようにする
- Decimal型を理解する
D問題
感想
割とすぐにACできた。
DFS,BFSの亜種。
普通に現在の距離がわかるようにBFSする。但し、探索する条件として、”snuke”の順番に辿れているかを確認する必要がある。
現在の距離をdist、現在の座標を(h,w)とすると、”snuke”[dist%5] == S[h][w]である必要がある。
import sys
import itertools
import math
import collections
import bisect
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**18
def main():
H, W = list(map(int, input().split()))
S = [list(input().strip()) for _ in range(H)]
if S[0][0] != "s":
print("No")
exit()
snuke = "snuke"
todo = []
todo.append([0, 0, 0])
done = [[False] * W for _ in range(H)]
while todo:
cw, ch, dist = todo.pop()
if done[ch][cw] is True:
continue
for dw, dh in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
nw = dw + cw
nh = dh + ch
if 0 <= nw < W and 0 <= nh < H:
if done[nh][nw] is True:
continue
if S[nh][nw] == snuke[(dist+1) % 5]:
if nw == W-1 and nh == H-1:
print("Yes")
exit()
todo.append([nw, nh, dist+1])
done[ch][cw] = True
print("No")
main()
E問題
感想
実装中に時間切れ。
S配列中のM,E,Xが現れるindexをそれぞれ保存しておいて、Mのindexで全探索する(=i)。j,kはbisectで探索すると、log2(10**5)くらいでは探索できると思う。なのでそれぞれ20回程度になるので、bisectで探索する分には40回くらいになる。iの全探索は10**5くらいなので、合わせて4*10**6くらいの計算量になる。
MEXの計算は累積和を使って、O(1)くらいにできそう。Aの配列で今まで出てきた0,1,2の個数を累積和していくと、あるindex以降に出てくる0,1,2の個数がO(1)で分かる。
あとはMEXの計算ができれば、累積和で分かった個数を掛けて、総和を計算できる。
実装していないので、机上のクーロン。
コメント