AGC049B
from AGC049
AGC049B
考えたこと
行われる操作は01→10か11→00かのどちらか
後ろから考える
ケース1の時、末尾の1どうしはベアになる
消えることができないから
ケース2の時、消して良いのか？
削除可能回数でDP？
N=10^5だから10^4くらい削除可能な時に辛い
ケース2の時、消して良いのか？→よくない
S: 110011
T: 001100
この時後ろを先に消してしまうと達成不能になる
前からやる？
前からやる
削除するパターンが最適解の中にあるとすると、削除する場所を交換してよりよい解が作れるので、最適解であるという前提に矛盾する、よって削除するパターンはない
AC
Tweet:
操作は1を一つ左に動かすか、2個を消すか。
最も左の1に注目しSの方が左である時、解があるとするならその1は消えなければならないので消すのにかかるコストを回答に足して、注目する1を2つ先のものにする。
逆の場合は先頭の1を消しても損であることから最適解では消されない。
Sの先頭の1をTの先頭の1まで動かすコストを回答に足して、それぞれ次の1に注目する。
最後までたどり着いたらそれは最適解なので回答を返す。
Sが足りなくなるなどの不整合が起きたら、解が存在しないとわかる。
僕の実装では先に1が立っている場所を列挙しているけど、これはやらなくても解けるかもしれない。
「次の1に注目」が添え字のインクリメントになるのでコードはわかりやすい。
pythondef solve(N, S, T):
spos = []
tpos = []
diff = 0
for i in range(N):
if S[i] == 1:
spos.append(i)
diff += 1
if T[i] == 1:
tpos.append(i)
diff -= 1
if diff % 2 == 1:
return -1
if diff < 0:
return -1
tpos += [N] * N
spos.append(-1)
i = 0
j = 0
ret = 0
while i < len(spos) - 1:
if spos[i] < tpos[j]:
# spos_i should be deleted
next = spos[i + 1]
if next == -1:
return -1
ret += (next - spos[i])
i += 2
continue
ret += (spos[i] - tpos[j])
i += 1
j += 1
if j != len(tpos) - N:
return -1
return retRelated Pages
- →帰着する力×計算量の見積もり×abc165c×agc048×思考の部品×abc034c×arc106d×貪欲法の証明パターン×abc146d×agc038a×agc036a×arc083a×arc026b×arc040c×arc024b×cf17_final_c×agc024b×soundhound2018_summer_qual_c×panasonic2020_d×arc091b×公式より小オーダー×abc147d×abc006c×abc070d×abc125c×agc014b×agc018a×abc132d×abc014c×aising2019c×code_festival_2017_quala_c×abc109d×abc112c×agc003b×arc062b×agc024c×indeednow_2015_quala_c×abc016d×abc121d×agc033a×arc054b×arc092a×arc052b×abc080c×tenka1_2017c×abc105c×abc032c×abc054c×diverta2019_2_c×indeednow_2015_qualc_c×abc089d×abc157d×abc012d×abc154e×arc032b×abc126d×arc081b×abc138e×tenka1_2018_c×nikkei2019_qual_c×abc019c×abc140d×arc042b×arc064a×arc034b×abc124d×arc037b×arc097b×arc097a×arc036b×abc096d×abc150d×doing×sumitb2019_e×nomura2020c×code_festival_qualb_c×m_solutions2019d×agc019b×abc103d×agc029b×arc087b×arc014c×abc165e×agc006b×codefestival_2016_final_c×agc031b×agc022b×agc032b→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]