1完、12:11。AGCではベストリザルトでした。
各問題
A - Dividing a String
違う文字が並んでいるところは、もちろん分割できます。
同じ文字が並んでいる場合、もう一文字取ってくれば、文字数が1と2になり文字種にかかわらず違う文字列になるので分割できます。 ここでポイントなのが、一度そのように2文字にした場合、その後ろは「どの文字が来ても」1文字で分割できます。
2文字で切る位置を工夫して、分割数を増やせる可能性も少し考えてみましたが、2文字で切った後の「どの文字が来ても」1文字で分割できるという条件が強いので多分大丈夫だろうと思い、前から貪欲に分割していく実装をして投げると通りました。
(解説を読むと、漸化式とか動的計画法とか書いてあるので、もしかしてこれ嘘貪欲だったかもしれない??)
まったくの余談ですが、上記の文章を読み直していて、「文字」という文字がゲシュタルト崩壊を起こしました・・・。
B - RGB Balls
さっぱり見当がつかなかったので、パス。
C - Numbers on a Circle
嘘貪欲しか思いつかず・・・。(大きいもの優先で後ろから引き算していく)
最後に記念提出してみましたが(おい)、案の定TLE->WAでした。
D - Sorting a Grid
制約がゆるいので、ごりごり実装したらなんとかなったりしない?と思って挑んでみるも、サンプルは通っても後はWAだらけでした。 そりゃ1100がそんなに簡単に解けるわけはないですよね。
E, F
見てません。
まとめ
Aが嘘貪欲だったのかどうかが気になります・・・。
だがしかし、嘘でも何でもAGCのベストリザルト更新で、レートもHighest更新しました。次回水パフォ中位で昇級なので、次回何度めかの昇級戦です。明日のABCで決めてしまいたい。