hotpepsiの練習帳

SRM 678

12:45

https://competitiveprogramming.info/topcoder/srm/round/16648/div/1

Div1 Easy (250) ANewHope

問題

• はるかな銀河の彼方で...一週間はN日からなる
• ルークはN種類のシャツを1枚ずつ持っている
• 各週において、毎日違うシャツを着る
• シャツは洗濯する必要があり、同じシャツはD日後以降にしか着られない
• 最初の週のシャツを着る順番と、最後の週のシャツを着る順番が与えられる
• 条件を満たすための週の総数の最小値を求める

方針

• 最初と最後が同じなら答えは1
• 各シャツの最初の週の位置a[i]、最終週の位置b[i]を求める
• 各シャツの位置の差d[i]=b[i] + N - a[i]で、最短でd[i]日後に着ることになる
• d[i]の最小値mがD未満のときは、毎日r=N-Dずつ差を広げていく必要がある
• D以上にするのに必要な日数はx=ceil(D - m) / r日
• 最初と最終週が必要なのでx+2が答え
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_678/ANewHope.cpp

結果

o-- 168th/296 125.86pt rating 1380 -> 1407 (+27)

スターウオーズ回。

単純に差を縮めていけばいいようだが、合っているかあまり自信なし。

http://togetter.com/li/925031