Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

https://t.co/Irf6A7phAy Scholarship Contest 2023-2024 (Div. 1 + Div. 2) pretestはEまで
A 後ろから作る
B k%2で場合分け
C 最も大きい2ベキを引く
D 累積和を頑張るDP
E 最上位bitが同じとき、"I don't know"と言うと、最上位bitがない問題へ帰着される
F Moを疑っていたが、差分計算が分からず

— titia (@titia_til) August 26, 2023

F. Exotic Queries

　Mo’s algorithmを使うのかと思ったが、違っていてびっくりした。これっぽい、と思った解法が違っていることは少ないので。

　解説AC。

　えー、解法を理解するのも、それを平面走査に持ち込むところも非常に苦しんだ。

　a=A[i]となる隣接するindexがxとyだった（つまり、A[x]=a, A[y]=aで(x, y)にA[i]=aとなるものはない）とき、xとyの間に、aより小さいものがあれば答えが一つ増える、というのが発想の元なのは分かるが、ここまで分かってもどう定式化すれば良いかが難しい。

　その後、この問題が平面走査で解けるということを理解するのも難しかった。

　典型の組み合わせだということは分かるが、あまりコンテスト中に解けるビジョンが見えない……。

　また、PyPyだとTLEが取れず、chatGPTを利用してC++に直してACした。