AtCoder ABC202
ABC202参加しました。
A - Three Dice
サイコロの表面と裏面を足すと7になるので、裏面は7-表面で計算可能です。
解説 - エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）
B - 180°
文字列を後ろから探索し、反転する文字6,9が出たら9,6を追加していけばいいです。
解説 - エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）
C - Made Up
最初は、
Made Up [エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202） C] - はまやんはまやんはまやん
に近くなりました。配列Dを考えて、D[i] = B[C[i]]とすれば、ややこしい部分は普通の配列になります。
ここからは公式解答がわかりやすいのですが、以下のように考えることも可能です。
例として
D:1,2,2,2,3,3,4...
となっているとき、A[i]が2であるなら
LowerBound(D, A[i]) = 1 UpperBound(D, A[i]) = 4
であるので、ans+= UpperBoundの結果 - LowerBoundの結果とすれば、あるA[i]に対してfor(j=0~N)を回す必要がなくなります。LowerBound, UpperBoundはC++のリファレンスがわかりやすいです。二分探索なので、計算量がO(logN)だったはずで、A[i]を順に回している中に加えても時間的には問題ありません。これを使うなら、ちゃんと事前にDはソートしてあげましょう。
lower_bound - cpprefjp C++日本語リファレンス
upper_bound - cpprefjp C++日本語リファレンス
結局公式解答とやっていることは同じです。詳しくは以下。
Submission #22828066 - AISing Programming Contest 2021（AtCoder Beginner Contest 202）
解説 - エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）
D - aab aba baa
辞書式順なので、next_permutation()で回せばokと思ってしまいましたが、Kが存外に大きい数なので、最初から辞書式に回すとTLEします。
aab aba baa [エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202） D] - はまやんはまやんはまやん
わからなかったのでここを見ました。
なるほど、前から順番に文字を決めていって、どんどん残りの部分文字列を考えていけばいいですね。
Kは最初の、何も部分文字列が決まっていない状態での辞書式順で何番目か、なので、どんどん先頭が決まっていったらKも「この部分文字列での何番目なのか」を考える必要があります。
このときに部分文字列の先頭がbに決まったら、Kを補正してあげる必要があります。
解説 - エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）
まとめ
全然スコアが伸びない...
Cで躓くことが増えたので、下がる一方...
