AtCoderRegularContest134 B問題400点「Reserve or Reverse」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ N \leq 10^5
解法・お気持ち
$ i番目の文字$ S_iより小さな文字がいくつか複数$ iより右側ににあるとします。
ここで、どの文字を選んで交換すべきかですが、$ iより右側にある最も小さい文字(aなど)を選択すべきです。
かつ極力右側にある文字を選択すべきです。
以下のように極力右側にある最も a に近い文字を選ばないと、$ i + 1以降の文字の交換で不利になります。
https://gyazo.com/8775ba69ca66e6323e5ba3bd0eb4ba9f
よって、$ i = 0から$ Nまで走査を行います。
$ iのとき、$ i + 1以降で最も小さい文字かつ右側の文字と交換します。
ただし、これまで使った右側の文字よりは左側の文字と交換しなければなりません。
これはしゃくとり法の要領で、使用できる右側の文字のインデックスを左にずらしていけばいいです。 計算量
$ O(N)
新たな学び
Go で string における文字を交換したいときは rune の配列にすればよい
rune は Unicode のコードポイント
反省点
コード
code: go
func solve() {
const C = 26
N := io.NextInt()
S := io.NextLine()
cnt := make([]int, 26)
for i := 0; i < N; i++ {
}
T := []rune(S)
r := N - 1
for i := 0; i < N; i++ {
k := -1
for j := 0; j < c; j++ {
k = j
break
}
}
if k == -1 {
continue
}
for int(Tr-'a') != k && i < r { r--
}
r--
}
io.PrintLn(string(T))
}
// ------------------------------------------------------------
// ------------------------------------------------------------
func main() {
solve()
defer io.Flush()
}