ABC334参加記 - Ang107kの日記

結果

ノーペナ5完＆自己最高パフォで年内での入緑を達成できました。

色変記事に関しては後日書く予定です。

苦手なDPが出なかったこと、比較的得意な貪欲的な考え方を要する問題が多かったのが勝因のような気もします。

考察に要した時間がB > C > E > D > Aとなっており、BC問題を解いている時は少なからず焦っていました。

各問題の解法、感想

A問題

これはそのまま条件分岐を実装するだけです。

以下コード

b,g = MII()

if b > g:

print("Bat")

else:

print("Glove")

B問題
中々に難しかったです。
制約の数字が大きいので、whileでaを移動させながら見るのは無理そう、上手いこと計算して答えだす感じかなーと思いながら具体的な実装はすぐに思いつけず...
結局、基準点をl,rの中に移動させて、基準点から左右に見たときのそれぞれのツリーの置ける数を調べることで対処しました。

以下コード

a,m,l,r = MII()

temp = r - l

if l <= a <= r:

st = a

elif a < l:

st = a + m*math.ceil((l-a) // m)

elif r < a:

st = a - m*math.ceil((a-r) // m)

ans = ((a-l)//m + (r-a)//m +1)

print(ans)

C問題

証明しないまま提出したので、ジャッジ中はお祈りしていました。
（通ってよかった）
解法としては、まず全ての存在する靴下を昇順に並べたものを用意します。
その中でペアを作っていくわけですが、存在する靴下の数が奇数の場合、少し面倒な処理が必要になります。
偶数の場合、頭から二個のペアを作っていき、その差の絶対値の和が答えです。
奇数の場合、靴下を0番目から数えたとき、偶数番目の靴下を使用しないことが、奇妙さを最低にするための条件となります。よって、全ての奇数番目の靴下を使用しないときの場合についての奇妙さを求めればよくなります。
しかし、それをそのまま実装すると、計算量がO(N^2)となりTLEします。それを防ぐために、奇妙さについての累積和を偶数始まり、奇数始まりそれぞれで取ることでO(N)の落とすことができ、無事ACできました。
以下コード
```
 
```
n,k = MII()

a = set(LMII())

s = []

for i in range(1,n+1):

s.append(i)

if i not in a:

s.append(i)

len_s = len(s)

ans = 0

if len(s) % 2 == 0:

for i in range(0,len_s,2):

ans += s[i+1] - s[i]

else:

g_r = [0]

k_r = [0]

temp = 0

for i in range(0,len_s-1,2):

temp += s[i+1] - s[i]

g_r.append(temp)

temp = 0

for i in range(1,len_s,2):

temp += s[i+1] - s[i]

k_r.append(temp)

ans = inf

for i in range(len_s):

if i % 2 == 0:

ans = min(g_r[i // 2] + k_r[-1] - k_r[i // 2],ans)
print(ans)

D問題
これは瞬殺できたので良かったです。
必要なトナカイが少ない順にソリを並べ、その順でソリを引けばよいです。
よって、ソートしたRの累積和を取り、後は二部探索で挿入位置を探せばそれが答えになります。
以下コード

n,Q = MII()

r = LMII()

q = [II() for _ in range(Q)]

r.sort()

temp = 0

rui = []

for i in r:

temp += i

rui.append(temp)

for i in q:

temp = bisect_right(rui,i)

print(temp)

E問題
それぞれの赤マスが緑になった場合の緑の連結成分数を高速に求めることができれば、答えは求まります。
赤マスを緑にすることで、増減する連結成分の数は、予め緑の連結成分をグループ分けしておくことで高速に求められます。よって、赤マスそれぞれの場合において、元の連結成分数とその増減を加味したものを求め、後は期待値のmodに変換すれば答えです。
発想自体はすぐ浮かんだのですが、実装ミスやバグの改修に苦戦し、時間がかかってしまったのが心残りです。
以下コード

h,w = MII()

s = [input() for _ in range(h)]

visited = set()

dd = defaultdict(set)

def dfs(x,y,g):

deq = deque([(x,y)])

visited.add*1

dd[(x,y)] = g

while deq:

x,y = deq.pop()

for i,j in around4:

if is_not_Index_Er(x+i,y+j,h,w):

if s[x+i][y+j] == "#" and (x+i,y+j) not in visited:

visited.add*2

dd[(x+i,y+j)] = g

deq.append*3

temp = 0

for i in range(h):

for j in range(w):

if s[i][j] =="#" and (i,j) not in visited:

temp += 1

dfs(i,j,temp)

ans = 0

ren = temp

num = 0

for i in range(h):

for j in range(w):

if s[i][j] ==".":

num += 1

l = set()

for x,y in around4:

if is_not_Index_Er(x+i,y+j,h,w):

if s[x+i][y+j] == "#":

l.add(dd[(x+i,y+j)])

if l:

ans += (ren - len(l) + 1)

else:

ans += ren + 1

denominator = pow(num, -1, mod)

print(ans * denominator % mod)

*1:x,y

*2:x+i,y+j

*3:x+i,y+j

結果

各問題の解法、感想