Educational Codeforces Round 75

A問題

bool関数で奇数回連続で出た文字はtrueにしていく。もう初心者じゃないので最後i=n-1の処理は忘れない。cout << 'a'+iとかすると数値が出力される仕様を忘れていたのでそこでタイムロスしたが特に問題なし。

B問題

任意の回数スワップできるやつは一度全部取り出してそれから当てはめていくと考えることができるので、文字列の長さ偶奇ごとにカウント、0と1の出た回数の偶奇を管理、いい感じに場合わけでいい感じに答えを出す。

C問題

ここからが地獄の始まりだった。バブルソートの最悪計算量はn^2なのでバブルソートごっこしたら通るわけないのですがそれ以外に何も思い浮かばなかったのでとりあえず書いて出す。TLEじゃなくてWAですって。目も当てられない。ここで順位表を見るとフレンドの強い方々はC、D両方通しているもしくは両方通していない状況で、参加者全体の正答数もそこまで大差ないのでD問題へ進む。

D問題

medianの金額について二分探索、median<rになる範囲について二分探索、priority_queでその範囲内からmedian以上にすれば良いのかを貪欲に選ぶ、という解法を書いたけど実行時エラーが消えない。そもそもこの方法で合ってるのかもわからないし・・・、という状態が続く中、残り40分ほどになったので順位表を再確認。正答がC問題＞＞D問題になってて順位が急落していたので焦ってC問題に戻る。

C問題（再）

戻るとすぐに解法が思い浮かんだ。C問題に戻るという選択は間違っていなかったらしい。偶数のかたまり、奇数のかたまりが繋がっている部分について頭から順に比較をしていき、小さい方を前にすれば良い（説明がしにくいけどマージソートのマージ部分のような感覚）。焦って書いていたせいかコードが100行を超え、さらに制限時間残り20分を切ったがなんとか書き終えた。ここでWA出ても流石にこの残り時間でこの量は間違いを見つけられないと感じ、これを最後の望みだと思いながら提出。ACが出て達成感と脱力感を覚えながらコンテスト終了を待つ。