ganmo::cout

競技プログラミング始めました

AtCoder Beginner Contest 124

こどふぉの肩慣らしにと思いましたが意外に時間があいてしまいました
参加者4500人超えてるしC問題のACも3800人近くいるのでAtCoderも参加者もすごい

A - Buttons (100点)

問題: A - Buttons
取れる行動は、「ボタンAを2回押す」「ボタンBを2回押す」「ボタンAとボタンBを1回ずつ押す」の3つなので、それぞれの場合の得られるコインの枚数\{ 2A-1, 2B-1, A+B\}の最大値を出力してAC。O(1)。

拙解 (C++14): Submission #4938133 - AtCoder Beginner Contest 124

B - Great Ocean View (200点)

問題: B - Great Ocean View
中学校の数学の授業を思い出すとA\le B\le CのときA\le Cが成り立つことがわかるので、西側から見ていって、見ていった標高の最高値を更新するか最高値と同じ標高だった回数を数えて出力すればAC。O(N)。

拙解 (C++14): Submission #4939723 - AtCoder Beginner Contest 124

C - Coloring Colorfully (300点)

問題: C - Coloring Colorfully
タイルの色は黒と白の2種類しかないので、どの隣り合うタイルも色が違うようにするには、黒と白のしましまにするほかにない。このしましまも、「一番左が黒いパターン」と「一番左が白いパターン」の2種類しかない。したがって、この2つのパターンと違う色をそれぞれ数えるとそのパターンにするのに必要な塗り替えの回数になるので、小さいほうを出力してAC。O(|S|)。

拙解 (C++14): Submission #4941208 - AtCoder Beginner Contest 124

D - Handstand (400点)

問題: D - Handstand
まず、状態反転(≈XOR操作)は2回やったら元に戻るので、区間を（一部）共有するような操作をやっても回数は同じになる。例えば、10101―1[010]1→11011―11[0]11→11111とするのと、10101―1[0]101→11101―111[0]1→11111とするのとで必要な回数は変わらない。
加えて、1が連続する区間をできるだけ一つにつなげるのが最適になる。例を挙げれば、1010101→1110111(max3連続)としても意味がない。1010101→1111101(max5連続)とすると最大になる。
したがって、隙間が空かないように、0の連続する区間をK個反転すれば連続する1の数が最大になる。なので、文字列をランレングス圧縮する。実装を簡単にするために番兵を置いて(連続する1の個数,連続する0の個数,連続する1の個数,\cdots ,連続する1の個数)といった配列を用意する。例えば、

000011000111110011011

→ [0, 4, 2, 3, 5, 2, 2, 1, 2]
という風に配列を作っておいて、この累積和を取っておく（O(N)）。0-indexedで考えると、元の配列の1の区間は偶数のところで、K個0の区間をつぶせば長さは2K+1個になる。元の配列の[2i, 2i+2K+1)の範囲の和を、すべてのiで試して最大値を求めて出力すればAC。O(N)。

拙解 (C++14): Submission #4948322 - AtCoder Beginner Contest 124

まとめ

全体39位、A問題4位、大学内1位でした
どうやら強い人たちはCS Academyの方に出てたらしいです
でも気持ちがいいもんは気持ちがいいですね