Pile The Integer Game

この問題では主に二分探索、ゲームのシミュレーションを問います。

最初に見るとあまり求める答えのヒントがないように思えますが、もう一度問題をじっくりと注意深く見てみましょう。ゲームのルールより、

• プレイヤー $i$ はゲームを続ける度に $a\le b$ が成り立つような $b$ が書かれたカードを必ず場に出さなくてはならない

と書かれています。
このことから求める答え(ゲームを続けることのできる回数)を最大化するためには、場に出すカードに書かれた数値 $b$ が " $a$ より大きい数値の中で最小の値である" ようなカードを場に出すことが必要十分です。これを $O(N)$ で求めると時間制限に間に合わないので、これを高速に計算するために二分探索を用いてそのような $b$ を $O(\log_{}N)$ で求めることで間に合うようになります。

またプレイヤーごとにカードを場に出す動作ですが、単調増加性により配列内から削除する必要はありません。さらに、最初にプレイヤー $1$ が出すカードの数値は先ほどの同様の性質から $A_{1,1}$ を場に出すことが適切です。

以上で全体で $O(NL\log_{}L)$ でこの問題に正解することができます。以下は解答例(C++)です。

追記:
制約上、$O(NL)$ が間に合います。なので必ずしも二分探索を用いて実装する必要はありませんが、それを用いるとより高速に動作することだけ伝えておきます。$O(NL)$ の実装方法ではここでは省略します。