AtCoder Beginner Contest 083

更新日時:

AtCoder Beginner Contest 083

ソースコード

解法のメモ

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$ が伸ばせることになる。

その他

これは VSCode でかいた初めての C++ と markdown であった。

コメントする