【今日の精進】ABC253G - Swap Many Times

毎日格上の問題を倒すやつの82日目です。

問題リンク

atcoder.jp

問題概要

があるよ。

を満たす の組のうち、辞書順で 番目のものをこの順に見ていって、以下のようにするよ。

• の 番目を入れ替える

最終的な を求めてね。

解法

番目からキリのいいところまでを観察してみると、末尾の数列を反転させたものを先頭に写していると見れます。

そのため、この形で処理できるものは一気に処理します。

余ったものは、素直にシミュレーションすれば良いです。

提出コード

N,L,R=map(int,input().split())
lf=0
for i in range(N):
    lf+=1
    if L<=N-lf:
        lf=[lf,lf+L]
        break
    else:
        L-=N-lf
ri=0
for i in range(N):
    ri+=1
    if R<=N-ri:
        ri=[ri,ri+R]
        break
    else:
        R-=N-ri
A=list(range(1,N+1))
while lf[1]<=N:
    A[lf[0]-1],A[lf[1]-1]=A[lf[1]-1],A[lf[0]-1]
    if lf==ri:
        print(*A)
        exit()
    lf[1]+=1
if lf[0]+1!=ri[0]:
    A=A[:lf[0]]+A[-(ri[0]-lf[0]-1):][::-1]+A[lf[0]:-(ri[0]-lf[0]-1)]
for i in range(ri[0]+1,ri[1]+1):
    A[ri[0]-1],A[i-1]=A[i-1],A[ri[0]-1]
print(*A)

Submission #48415276 - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

感想

めっちゃARCっぽいんだけど？

空いた日にやってたこと*1

80日目

【今日の精進】
Codeforces Round 658 (Div. 1)

A...後ろから決める。
先頭の文字を適当に変えてから、最後尾に移すことを繰り返す。
B...ギャグ。
いくつか必ず一斉に追加される塊があるから、それでDP。

— はるく@0完 (@halc_kyopro) 2023年12月9日

x.com

*1:81日目忘れてたけど二次予選あったから許して…