ABC329

6完1ペナ。早解き回で成功。Bまで2分を切っていて、Dまで10分強、EFも早解き、Gが難しい。Eのペナは痛いけど、実力通り。この順位(久しぶりに200位以内)も実力通りかと言われると、まあどれも簡単だったし得意セットで実力通りという感じ。前半が簡単なのは本当にありがたい。

A - Spread

スペース区切りで出力するパターンを使うだけだった。

B - Next

難しそうだけど、ソートして後ろから見て最初のa.back()と異なる要素を出力するだけ。

Bまでで2分切ってるよ。ありがてえ。

C - Count xxx

1種類の文字なのでパターン数が少ない。文字毎に考えることができる。最大でK文字連続してたら、1文字からK文字までの条件を満たす部分文字列がある。最大で何文字連続しているかという問題を26回解く。

ランレングスでよかったのかあ。

D - Election Quick Report

priority_queueを使う(pairにして番号は符号逆にしてsecondに入れる)。過去のものも入っているが、過去の自分には必ず勝つので結果は変わらない。出力するとき番号の符号を直し忘れてサンプル通らなかった。

解説天才だな。ただ、実装は自分のやつのが楽そう。

Dまで10分ちょい。恐ろしい速さ。

E - Stamp

以前のAtCoderでコンテスト中に知ったけどこれは難しいように見えて逆から考えればいい。具体的には、最後に押したスタンプの場所としてありえるものを探してそこを'#'に変える、'#'の後ろにスタンプを押すと未来に塗り潰されるのでそこは考えなくていい。貪欲にやっていいか?'#'に変わることで得しかしないし、全部'#'になれば実際にその手順でできているので、OK。あとは計算量だが、だんだん最大塗り潰し個数が減っていくから何回か繰り返せば大丈夫でしょと未証明で提出したらTLE。TLE出すやつはゴミ。AAAAAABCみたいなのを見落としていたので後ろからもやることにして(forを逆にするだけなのでコピペですぐ書ける)(その前にM-1歩戻ることも考えたがfor文でこれやるとバグらせやすいので回避)、また未証明で提出、AC。

解説、ちゃんとこういう証明できる方法を使いたいよね。正しそうでも証明できないなら証明できる効率の悪い方法に飛びつくのはいい動きだ(時間的に損することはあるが)。

F - Colored Ball

unordered_setのvectorで管理すればまんまマージテク。個数は関係なくなる。a,bをswapしたけど、st[a]とst[b]をswapしたほうが楽だったか。

G - Delivery on Tree

読むのが大変。経路を決めたら遅く取って早く置くでいいか?子が2つある頂点に注目すると、どちらに行くか2通りがある。LCAに注目すると、そこからまずどちらに行くかが片方に制限されたりする。問題はカゴの容量Kで、考えたくないくらいもやもやというか繊細というか。必ず使う個数はまだしも、経路によって変わるのがなんかわからん。