甲子園決勝マジで智弁対決になってしまった。
August Lunchtime 2021 Division 1
Bunny Hops
$A_i$ の降順に見る。部分木sum と 祖先sum がDPの遷移に必要で、前者は 1点更新&区間sum のセグ木で出来る。後者は遷移を部分木に配るようにして考えると、区間加算&1点取得 が出来るデータ構造で対応できて、1点加算のBITで書くと楽に出来た。
区間加算&1点取得のverify
Chef and Deque
右端の長さを固定して、左端の部分集合を全て試す解法で十分高速。
$O(3^{n})$ において、数列長 $N$ として $n = \log{N}$ に置き換わったと考えるのが分かりやすい。累積和を $ M $ で割った余りを予め計算しておき、それらが等しいかどうかで判定。
Longest Spanning Substrings
全ての文字列を区切り文字で連結させ、Suffix Array によって、高さ配列を求めておく。用いる辺の候補として、接尾辞配列で隣接している箇所同士だけを見れば良いので、これらを列挙し後はクラスカル法と同様に全域木を求めれば良い。区切り文字に同じ文字を使うとバグるので、それぞれ異なる区切り文字を用いるか、数列を渡すかの対策をしておく。
技術室奥プログラミングコンテスト#6 Day2
B. Replace to the Other
奇数(偶数)番目の文字を反転させておく。すると可能な操作は隣接する A と B のswap操作になる。A または B の個数が異なっていたら変換不可能で、そうでないならば変換可能であり、必要なコストも簡単に求めることができる。
Deltix Round, Summer 2021
E. Equilibrium
区間 $[l,r]$ における $B _ {i} - A _ {i}$ の累積和が、0を下回る、もしくは終点と始点が等しく無い場合は、明らかに -1 である。
可能な場合は累積和の最大値が答えに一致する。
つまり、累積和の配列の RMQ に答えられるならば、この問題を解くことができる。
以前整備したBIT2本で Static RMQ を解くライブラリを用いたのだが、
関数部分でオーバーフローを起こしていることにまるで気がつかなかった。反省。
