AtCoder Regular Contest 130 反省

かなしい

結果を鑑みて

700 8:27

471位。Cで1ケースWA、WAを取りに行くとTLEでぼろぼろにされた。きちんと考察してから書くこと。

A - Remove One Character

ランレングス圧縮して二項係数をとってみると解ける。サンプルも優しいし、今回は300点っぽい300点だった。

B - Colorful Lines

ふつうにやろうとするとHやWがでかすぎて嫌な気持ちになりながらやることになりそうだが、後ろから見ると行や列の上書きは行や列の削除に対応づけられて、解けた。

ここまでは勘が冴えてた。

C - Digit Sum Minimization

本当に辛い。

こんなもの貪欲するしかないから貪欲を考える。和が9になるペアをマッチしてあげると、和が10以上になるペアを使った後に和が9になるやつを使い続けてあとは適当にやれば良いことがわかる。これで１WAまで進められたが、マッチの結果ぜんぶ9になるペアにしてしまうと良くない。

どれか一個のマッチを破壊しなくてはならないが、55通りくらいあってヤバい。しかもその都度digitsumをとっていてこれが一番ヤバい。TLEラッシュになり敗北。

digitsumの部分を最適化するか、もうちょっと問題を整理するしかない。

総括

Bまで良かったんだけど、Cで破滅。青パフォで済んだからまだよかったけど、泥沼実装に突っ込む前に落ち着いて考えられるようになりたいな。落ち着くのが一番難しい。