AtCoder AGC 037 参戦記

AtCoder AGC 037

atcoder.jp

に参戦しました。結果は A 問題のみでしたが 7:00 で正解と早解きに成功していてパフォーマンスは 1614 でレーティングを少し落とすだけで済みました。
体感難易度は B > C で実際 C はもうちょっとで AC だったのですがかなり悔しいです。

感想

A 問題

貪欲にいけるはず

• 部分文字は 1 or 2 文字しかない
  • 2 文字になるのは同じ文字が続くとき ex: "aaa"
    • この次に "a" がきたとしても 1 文字で分割できる
• 同じ文字が連続するまでは 1 文字づつ分割
• 同じ文字が連続するところで 1-2-1-2... と分割。
  • このとき 2 文字目が違う文字になることがある
    • この場合、2-1-2-1... と分割してもよいが、このシーケンスの後に同じ文字が続く ex: "aaaaabbb..." ときに 2 文字にする必要があるので得になることはない
• 文字列の最後の場合のみ、1-2-1-1 みたいな分割になるが、このときは 2-1-2 と組み替える。

と考えてこの通りに実装した。

B 問題

考えても考えても正解にたどり着けなかった。
最小値を構成すのは明らかに RGB を渡す人の順番を固定する手順だから、それと同じ手順を数えればいいはず...だが同じ手順になる条件を考察しきれず...

C 問題

しばらくの考察と WA, TLE を出したのち

• 最終状態から引くことを考える
• b[i] が引けるのは b[i - 1] + b[i + 1] < b[i] のときのみで引いた結果は b[i] - (b[i -1] + b[i + 1])
• つまり隣の数がその数より大きい場合は引けない
• b[i] が引けるときに最大限引いてしまったほうがよい
  • 最大限引いたあとは b[i-1] と b[i+1] が引けるようになるかもしれない (b[i-2] と b[i + 2] 次第)
  • ただし a[i] が b[i - 1] + b[i + 1] より大きい場合はそれより引けない

と考察して、b[i] が引けるかどうかのリストを維持しながら引けなくなるまで全探索してみたが最後のテストケースのみ WA が取れなかった...