【競プロ精進日記】Codeforces Round #629 (Div. 3)

2020.03.27
競プロ

1. はじめに
2. A
3. B
4. C
5. D
6. E
7. F

はじめに

当ブログは問題の解説がメインではなく、筆者の解法やアイデアの保存がメインです。
したがって、読者の期待に沿えないことがあると思いますがご了承ください。

A

A – Divisibility Problem
$$ \left\lceil \frac{a}{b} \right\rceil \cdot b \ – a $$
https://codeforces.com/contest/1328/submission/74398280

B

B – K-th Beautiful String
法則性が必ずあると思い、色々紙にかいて考えました。私にはとても難しいです。
まず、2つのbのうち先頭のbについて考えました。
k=1で先頭のbは後ろから2番目、k=2,3で後ろから3番目、k=4,5,6で後ろから4番目となっていきます。
つまり、後ろからm番目になるようなkは{1},{2,3},{4,5,6},{7,8,9,10}…と要素も数も増加していく数列の何番目（実際は+1）に属するかによって決まることに気づきました。
このm番目を求めるのですが、計算式が思いつかなかったので実際に数列の先頭の要素を持つ配列（1,2,4,7…）を作成し、何番目に属するかをupper_boundで調べました。
例えば、k=6の場合upper_bound(配列,k)-1すればどの数列に属するか（3番目の数列に属するので後ろから4番目）がわかります。
後は、後ろのbの位置ですが、文字列の最後尾から順番に先頭に移動していくので（k-属する数列の先頭の要素）番目が後ろのbの位置になります。
実際に例を示すと、n=10,k=14のときは、k=14が{1},{2,3},{4,5,6},{7,8,9,10},{11,12,13,14,15}…のうち5番目に属するので後ろから5+1番目に先頭のbが位置します。
後ろのbは(k=14)-(属する先頭の要素=11)なので3+1番目に後ろのbが位置します。
したがって、n=10,k=14の場合はaaaababaaaが答えになります。
回りくどいですが私はこのようにして導きました。
https://codeforces.com/contest/1328/submission/74430779

C

C – Ternary XOR
x[i]の値によってa[i],b[i]がどのような値を取るのかを考えます。
x[i]=0のときa[i]=0,b[i]=0 or a[i]=1,b[i]=2 or a[i]=2,b[i]=1
x[i]=1のときa[i]=0,b[i]=1 or a[i]=1,b[i]=0 or a[i]=2,b[i]=2
x[i]=2のときa[i]=0,b[i]=2 or a[i]=1,b[i]=1 or a[i]=2,b[i]=0
このうち明らかに最適でないものはa[i]=1,b[i]=2、a[i]=2,b[i]=1、a[i]=2,b[i]=2のときです。
注意すべきなのはa[i]=0,b[i]=2などはmax=2ですが選択次第で最適になる場合があります。
どのように選択するかですが、aとbの差が小さくなるように選択します。
つまり、aとbの大小が確定していないときはx[i]=2の場合、a[i]=0,b[i]=2ではなく、aとbを同じに保てるa[i]=1,b[i]=1を選択します。
aとbの大小が決まった後は、大きい方に小さい数を、小さい方に大きい数を選択するのが差が最小になり最適です。
これを適切に実装すればACです。a[i]=1,b[i]=1を選ぶ場合が最適でないことに気づくのに時間がかかりました…
https://codeforces.com/contest/1328/submission/74468588