ABC178F

https://gyazo.com/2f42a5744a2fdfabc0c5a486a12710fd

ABC178F

リアルタイム

最も余ってる数から使っていけばいいだろ、と実装

24 WA

方針がダメだったのか後で確認

公式解説

範囲が重ならないようにずらすことで解が得られる

時を置いて考えたこと

たくさんある解の中から構築しやすいものを見つけることが必要

「解があるならこの形の解がある」

まず一番出現回数が多い数に注目する

https://gyazo.com/5e927d1680578778fb5d07f47a5bc7a3

A: 出現回数CがNを超えてたら明らかに不可能

B: ちょうどNの時、重ならないように入れるしかない

この時、残りのマスの並びはどうであっても関係ない

C: それ以外の場合、N-Cマスを被らないように並べれば良い

N個出現する数がない限り配置できる

「出現頻度最大の数を選ぶ」の条件から、そのようなものはないことがわかる

実装

20分で実装、25分で手元バグ修正、提出して20WA

うーん、どういうパターンを見落としてるのだろう？

→for文なのにポインタをインクリメントした時にcontinue

ランダムテストでおかしな出力を見つけ、修正して53分で提出、6WA

code:python

assert Counter(BS) == Counter(ret)

return ret

6WA

code:python

む？6WA??

code:python

assert len(ret) == N

むむ？これも6WA？

あ、そうか、

code:python

assert 1 == 2

print("No")

16RE

つまり本当はNoを返すべきでないのに返してるケースがある

code:python

assert 1 == 2

return

6RE

つまりこれが間違い

→AC

code:python

def solve(N, AS, BS):

from collections import Counter

a_count = Counter(AS)

b_count = Counter(BS)

max_occur = 0

when_max = None

for i in range(N + 10):

if t > N:

return

if t > max_occur:

max_occur = t

when_max = i

ret = []

a_keys = list(a_count.keys())

b_keys = list(b_count.keys())

a_pointer = 0

b_pointer = 0

a_len = len(a_keys)

b_len = len(b_keys)

for _i in range(N - max_occur):

if a == when_max:

a_pointer = (a_pointer + 1) % a_len

if c == 0:

a_pointer = (a_pointer + 1) % a_len

b_pointer = (b_pointer + 1) % b_len

ret.append((a, b))

for b in b_count:

ret.append((when_max, b))

for a in a_count:

ret.append((a, when_max))

ret.sort()

return ret