🐢

[ABC347 C] Ideal Holidays

2024/03/31に公開

Ruby

なぜ WA になるのかわからない問題。

問題の要約

予定を休日に収められるか？

たとえば二日連続の予定がある場合は土日に割り当てれば収められる。

最小最大の幅が土日以内か？ (WA)

例1の D = 1 2 9 のケースで考える。折り返しを考慮して一週間に補正するのは間違っていない。すると 9 は 2 になる。カレンダーでは、

となるので、「記入がある部分の幅」が「土日幅」以内か？を判定する。

N, A, B = gets.split.collect(&:to_i)  # => [3, 2, 5]
D = gets.split.collect(&:to_i)        # => [1, 2, 9]
W = A + B                             # => 7
D = D.collect { |e| e.modulo(W) }     # => [1, 2, 2]
min, max = D.minmax                   # => [1, 2]
size = (min..max).size                # => 2
ans = size <= A                       # => true
puts ans ? "Yes" : "No"

これを提出すると1個だけ通らないテストがでる。試しに D = 6 7 13 だと失敗するのがわかった。カレンダーでは、

となり、

min, max = 0, 6
(min..max).size  # => 7

隣り合っているはずなのに幅が 2 にならないのだった。

そこで最小値を一週間ずらして 0..6 を 6..7 に補正する。

min, max = 0, 6
r = max..(min + W)  # => 6..7
r.size              # => 2

つまり min..max と max..(min + W) のどちらかの幅が 2 以下なら Yes とすればよいはずだ。

これで再提出すると WA が増えた。

解説の模範解答 (AC)

予定を順番に並べる
境界を考慮して二周する
予定と予定の間のどこかに平日が5日以上あるか？

とする方法がわかりやすかった。

D = 6 7 13 では、

0..6 または 7..13 の間で 5 日以上あるので Yes になる。

N, A, B = gets.split.collect(&:to_i)                 # => [3, 2, 5]
D = gets.split.collect(&:to_i)                       # => [6, 7, 13]
W = A + B                                            # => 7
D = D.collect { |e| e.modulo(W) }.uniq.sort          # => [0, 6]
D = D + D.collect { |e| e + W }                      # => [0, 6, 7, 13]
ans = D.each_cons(2).any? { |a, b| b - a - 1 >= B }  # => true
puts ans ? "Yes" : "No"

[疑問] 二周する必要なくない？

さきほど 0..6 または 7..13 の間で 5 日以上あるので Yes になる、としたが、最初の 0..6 の部分で 5 日以上あると判定できるので、

6 - 0 - 1 >= 5  # => true

二周する必要がないように思えるが、D = 1 2 にすると、

2 - 1 - 1 >= 5  # => false

失敗するので、やっぱり二周しないといけない。二周すると、

8 - 2 - 1 >= 5  # => true

2..8 の部分で正しく判定できる。

参考

https://www.youtube.com/watch?v=mRsawW3ow98&t=1658s

土	日	月	火	水	木	金
1	2
	2

月	火	水	木	金	土	日
					6	0
					6

月	火	水	木	金	土	日
						0
					6	7
					13

月	火	水	木	金	土	日
						0
					6

土	日	月	火	水	木	金
1	2
8	9