Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Regular Contest 133

2完。

各問題

A - Erase by Value

辞書順最小といういことで、前に大きい数字があったら損ですから、前から順番に単調減少しているところを探していって、見つかったらそれの大きい方の数を抜けばよいです。

広義単調増加列だった場合は一番うしろの数を抜きましょう。

B - Dividing Subsequence

LISっぽいことをすればよいというのはわかったのですが、そもそもLISがちゃんと理解できていないというあれ・・・。

というわけで最後までTLE解しか書けず。

C - Row Column Sums

ありえる最大の数は、(K-1) * H * Wから、(K-1) * W % KとAとの差分(行について)と(K-1) * H % KとBとの差分(列について)の大きい方を引いたものになります。

また解が存在するかどうかは、上記の行についての差分のmod Kと列についての差分のmod Kが一致するかどうかでわかります。

というわけで、この問題が解けました。

とかいって、実戦中は全く証明せずに勘で投げました・・・。

まとめ

Bで粘りすぎてからのCが10分で通せたのはパフォ的にもったいなかったですが、まあCもちゃんと証明できたわけじゃないのでむしろもうかったといえるかも。

レートは一応連続でHighest更新です。

f:id:mdstoy:20220122233235p:plain