ARC110C
from ARC110
ARC110C
貪欲にやる
「1を先頭に持ってくるには」を考える
今いる位置から先頭まで持ってくる置換が必要不可欠
順番に先頭に持ってくる過程をやって、過不足が有ればNG
関連: 貪欲法の証明パターン
pythondef solve(N, PS):
ret = []
used = [False] * (N - 1)
def swap(x):
PS[x - 1], PS[x] = PS[x], PS[x - 1]
used[x - 1] = True
ret.append(x)
for target in range(1, N):
x = PS.index(target, target - 1)
for i in range(x, target - 1, -1):
if used[i - 1]:
return [-1]
swap(i)
if False in used:
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→
- →ホッケースティック恒等式×二項係数の公式×vandermondeの恒等式×巨大なnについての二項係数×形式的べき級数×arc110d_fps×oeis×重複組合せの畳み込み×arc110d_nonfps×ARC110→
"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]