D - Strange Mirroring

[hxrxchang]

https://atcoder.jp/contests/abc380/tasks/abc380_d

問題概要

アルファベット大文字小文字からなる文字列Sがある。
Sの大文字小文字を入れ替えた文字列をTとして、Sの末尾にTを連結するというのを10 ** 100回繰り返す。

Q回の以下の質問に答えよ。

• 操作完了後のSの先頭からi文字目が何か求めよ。

解き方

操作をシミュレーションすると、最初のSの長さの文字列を葉とした二分木ができることが分かる。
で、この木を観察すると、あるNodeから葉に向かうときに、右に移動した回数が偶数回のとき、最初のSと同じということが分かる。
二分探索の要領で指定されたindexがある葉に行く過程で、何回右に行ったかを計算する。

func solve() {
	s := strToSlice(getStr(), "")
	n := len(s)

	q := getInt()
	k := getInts()

	res := make([]string, q)
	for i, targetIdx := range k {
		targetIdx--
		si := targetIdx % n
		targetIdx /= n

		ans := s[si]
		cnt := calc(0, pow(2, 60), targetIdx)
		if cnt%2 != 0 {
			if unicode.IsUpper(rune(ans[0])) {
				ans = strings.ToLower(ans)
			} else {
				ans = strings.ToUpper(ans)
			}
		}
		res[i] = ans
	}

	printSlice(res)
}

func calc(l, r, k int) int {
	cnt := 0
	for l+1 < r {
		mid := (l + r) / 2
		if k < mid {
			r = mid
		} else {
			l = mid
			cnt++
		}
	}
	return cnt
}

https://atcoder.jp/contests/abc380/submissions/66599833