AtCoder Regular Contest 155 反省

あまりに久々

冷え

500: 120:56(2)

ついぞわからなかった！！

S に対して、条件を満たす T は一意に決められて、その手順もわかった。だが K がでかすぎる。

絵を描いてみると、T は S の降順、昇順、降順…… になることがわかる。あとは T の後ろらへんの一致判定をやっていたが、判定すべき範囲がわかっていなかった。なんか K がでかいときのやつが小さいときのやつに帰着されないかなあと思っていたが、具体的な方法論まで進めることができなかった。

KMP 法に途中浮気しかけたけど戻ってこれた。えらい。

えらくない部分は、A に 90 分使ってやっと B に行ったこと。

li-chao tree か？やめてくれよ。。。とか思ったりもしたが、絵を描いてみたらすんなりわかった。W 字の関数になるが、これを V 字 2 つと考えても最適解の都合上問題がないのだった。

BIT にぶたんでもいいんだが、面倒なので sorted set を借りてきた。

if set.ge(b): res = min(res, abs(set.ge(b) - b))

みたいなのをかいていて、set.ge(b) == None のときをケアしていたが、このコードは set.ge(b) が 0 の時も弾いてしまってペナ。

A = B の入力を入れてみて気付けたが、sorted set を使う時の注意点としておこう。

まず、30 分以上詰まるとか、泥沼に嵌り出したら他の問題も見てみよう。極端に難易度の離れたものでなければ解ける可能性がある。本当は「解ける問題から解く」が最適なんだけど、考察を始めないと解けるかどうかはわからないから難しいよね。

詰まったら腕立てするとかしてリフレッシュする、みたいのはまあ一般的に使えそうだ。

良くはないが、0 完しかけたところから 1 個取れたのはよかった。B を見に行くのが残り 10 分とかだったら冷静に考察できなかったかも。

ところで、レートが 1900 を割ってしまったのですが。。。ABC バチャを走りまくって速解き力をつけようね。

perarduaadastra