さまざまなしゃくとり - 早稲田大学チームvivid_turtle 知見共有@ ウィキ

蟻本に乗ってない、さまざまなしゃくとりのやり方を載せる

二つの配列間のしゃくとり

しゃくとりは一つの配列で、要素の単調性があるものかつ区間間の単調性(長い区間であればよりベストな結果になる)
という条件をものをO(n)で計算できるものである。
しかし、この条件を満たすものならば、一つの配列のみならず、二つの配列でもしゃくとりが可能である。
たとえば、配列１では[0, l)、配列２では[0, r)でしゃくとりしてもよい。

AOJ1161　Verbal Arithmetic　(AOJICPC400)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1161&lang=jp

同類項の妙技、半分全列挙の各パターンを参照。

この問題は、前半の列挙列と後半の列挙列(いずれもソート済み)の中で、同じ数字を見つける問題である。
前半の列のi番目に相当する値が後半の列のj番目だとすると、前半列のi + 1番目の値に相当するものは、後半列の0 ~ j - 1番目には必ずないので、しゃくとりを応用できる。