AtCoder Beginner Contest 083
Updated:
Source codes
Solutions
A - Libra
やるだけ。
B - Some Sums
真面目にやるだけ。
C - Multiple Gift
$X$ からスタートして $2$ 倍ずつしていくのが最善である。
D - Wide Flip
まず、 $i \geq K$ に対し、 $[0, i-1]$ と $[0, i]$ を指定することで、 $i$ 番目の文字だけ裏返すことができる。同様のことは逆側からもできる。だから $K \leq \lvert S \rvert/2$ では必ず目標は達成される。
ではそうでない場合はどうか。 $K > \lvert S \rvert / 2$ とする。部分文字列 $[\lvert S \rvert - K - 1, K]$ は上記のトリックが使えない。さらにいうと、どのように区間を選んだとしても、この区間は入る。ゆえに、これらはそもそも 0/1 が揃っていないと達成不可能であるとわかる。
だから真ん中から両端へ見ていって、同じ文字になっているところまでは $K$ が伸ばせることになる。
Others
これは VSCode でかいた初めての C++ と markdown であった。