競プロ日記

順位: 1394
パフォーマンス: 1152
新レーティング: 281
差分: +225


まだ灰色。
次あたり茶色になれそう。

前回に続いて4完。
EをやめてFから解いてたら解けてそうかもしれない。
前回もそんなこと言って実際解いてみたら時間内は無理そうだったので今回もそれかもしれない。
別の問題でRMQの実装に戸惑ってEもFもまだ解いていない。

A問題

かんたん。

B問題

問題文がややこしい・・・。
理解と実装のスピードを高めないといけない。

C問題

書いたら添字も関係性がすぐ分かるやつ。

D問題

問題文読み間違えた！
やってしまった！
その結果飛ばしてE問題を考えて時間を浪費した。
RR,LLが幸福じゃなくて、RLみたいに向き合ってるのが幸福かと思ってしまった。
普通の人は前の人が同じ向き向いていても幸福だと思わない・・・。
E問題から帰ってきてもう1回考え直したら条件違うじゃん！ってなって5分か10分くらいで解けた気がする。
最後の処理ちょっとミスって1WA。
この間違った条件でも似たような感じで解けそうではある。

E問題

結構考えたけど解ける気がしなかった。
ABC128 E Roadworkを思い出してO(NQ)のどちらかを二部探索でlogにできるのではと考えたのだが、どっちもnじゃあどうしようも・・・という感じ。
何を考えればO(n^2)から片方のnを二部探索に持っていけるのか全く分からなかった。

解説を見るとシグマを外してある数との掛け算の形に直していて驚くしかない。
新しいパターン。
こういう考え方もあるのか。

F問題二部平衡木では？となぜか直感。
二部平衡木がどんなものかあまり詳しく知らないし、関連アルゴリズムも全く知らない。
セグメントツリーくらいか。
ということで深く考えるのをやめてEを解くことにしてFはあまり考えていない。

コンテストが終わってから軽く考えたら普通に解けそうだなぁと思ってきた。
コンテスト中は焦っているのでかなり時間を費やしたEを解こうと頑張っていたが、Eに時間を費やし始める前にFに取り組めば良かったかもしれない。
前回もしかり、EFは難易度が逆転することも結構ありそう？