脳log[20220508]

2022年05月08日 (日) [AtCoder] 今日は ABC250 があった。自分の提出一覧。それぞれの問題にかかった時間が、A=３分強、B=10分、C=６分強、D=５分、E=17分、F=49分。B 問題難しすぎ。■E 問題「Prefix Equality」が面白かった。こういう手触りの問題好き。特別な道具や知識を必要としないところ(あと解法が２つ３つはあるらしいのもポイント高い)。最近の精進では 20211112 で解いた「Connected?」が似た感じ。集合の同一性を考えるのに、集合のサイズをキーにした。考えるべき集合は必ず先頭から始まる X 項から重複を除いたものになるので、X が増えるにしたがって集合のサイズも増える一方。集合のサイズごとに、２つの集合が一致するかしないかが決まる。それを予め調べておけば、クエリに対して２つの集合のサイズがそれぞれいくつになるかを調べ、サイズが一致していればそのサイズの集合が同一かどうかはすでに調べてあるので答えが出せる。制限時間が４秒だったけど 568 ms で十分だった。■F 問題「One Fourth」は典型90問で似たのをやった。「009 - Three Point Angle（★6）」かな。それとも他にもっと似た問題があったかも。やることは尺取り(もしくは累積和を二分探索)なんだけど、図形がからむと diff が高くなりがち(ギリギリ黄 diff だったもよう。もちろんほとんど青という意味でギリギリ)。図形要素はコンテスト中に検索したよ「多角形の面積」。