\(\displaystyle \max_{1\leq i \leq N}D_i=M\) とします。\(\sum_{i=1}^{N}D_i < 2M\) のとき、\(N\) 回の行動後に原点に戻ることが不可能なのが三角不等式からわかります。以下では \(2M \leq \sum_{i=1}^{N}D_i\) が成り立つものとします。

[1] 移動による原点からの距離の変化の考察

実数 \(D,R,R'\ (R' \leq R)\) 、および \(|a|+|b|=R\) をみたす\((a,b)\ (0 \leq a,b)\) に対し

• \(|a'|+|b'|=R'\)
• \(|a-a'|+|b-b'|=D\)

を満たす \((a',b')\) が存在する条件を考えます。三角不等式から \(R-R' \leq D \leq R+R'\) が必要です。

\(D=R-R'\) に対して、\(0 \leq a \leq R'\) のとき、\((a',b')=(a,b-(R-R'))\) 、\(R' \leq a \leq R\) のとき \((a',b')=(a-(R-R'),b)\) とすると \((a',b')\) は \(2\) 条件を満たします（上図の \(A,B\)）。

また、\(D=R+R'\) に対して、\(0 \leq a \leq R'\) のとき、\((a',b')=(-a,(R-R')-b)\) 、\(R' \leq a \leq R\) のとき \((a',b')=((R-R')-a,-b)\) とすると \((a',b')\) は \(2\) 条件を満たします（上図の \(A,C\)）。

以上より任意の \((a,b)\) に対して \(D=R-R',R+R'\) のときは条件を満たす \((a',b')\) が存在し、\((a',b')\) を \(|x|+|y|=R'\) 上で動かすと \(|a-a'|+|b-b'|\) が連続的に変化することから、 \(R-R' \leq D \leq R+R'\) のときはかならず存在することがわかります。

\(R < R'\) の場合も逆向きに考えれば同様の結論が得られます。

ここまでの考察で特に重要なものは以下の \(2\) 点にまとめられます。

• \(|R'-R| \leq D \leq|R+R'|, |a|+|b|=R\) をみたす任意の \((a,b),D\) に対して上記の \((a,'b')\) が存在する
• \(0 \leq D \leq 2R, |a|+|b|=R\) をみたす任意の \((a,b),D\) に対し、 \(|a'|+|b'|=R, |a-b'|+|a-b'|=D\) を満たす \((a',b')\) が存在する

[2] 順番が固定された場合の判定問題

\(i\) 回目の行動での移動距離が \(D_i\) と決まっているとき、\(|x_i|+|y_i| \leq K\) が成り立つように \(N\) 回の行動を終えられるか、という判定問題を考えます。まず明らかに \(D_i \leq 2K\) が必要です。

\(S_i=D_1+D_2+\dots+D_i\) 、 \(T_i=D_i+D_{i+1}+\dots+D_N\) とします。

\(K \leq S_i\) を満たす最小の \(i\) を \(L\) とします。三角不等式から \(D_L \leq S_{L-1}+K\) が必要です。これが満たされる場合、\(L\) 回の行動後には外周上( \(|x|+|y|=K\) )の任意の点にいることができるのが [1] での考察からわかります。同様に \(K \leq T_i\) を満たす最大の \(i\) を \(R\) とすると、\(D_{R} \leq T_{R+1}+K\) が必要で、これが満たされる場合、\(R-1\) 回目の行動で外周上にいればそれがどこであろうと原点に戻ってこれます。

すると \(L+1\) 回目から \(R-1\) 回目の行動を外周上から始めて外周上で終えることができれば \(N\) 回の行動を条件を満たすように終えることができます。これは [1] での最後の考察からわかるように、常に外周上に居続けることができるので可能です。

よって \(L,R\) が存在し、\(L < R\) であれば

• \(D_i \leq 2K\)
• \(D_L \leq S_{L-1}+K\)
• \(D_R \leq T_{R+1}+K\)

が必要十分条件です。

それ以外の場合について考えます。

まず \(D_i\) の総和が \(2K\) 以下の場合、常に可能です。

証明

\(\frac{S_N}{2} \leq S_i\) を満たす最小の \(i\) を \(k\) とし、\(a=\frac{S_N}{2} - S_{k-1}, b = S_k - a\) とおきます。

以下のような \(S_N\) 回の移動を考えます。

• \(1\) 回目から \(b\) 回目：\((x,y)\) から \((x,y+1)\) へ移動する
• \(b+1\) 回目から \(\frac{S_N}{2}\) 回目：\((x,y)\) から \((x+1,y)\) へ移動する
• \(\frac{S_N}{2}+1\) 回目から \(\frac{S_N}{2}+b\) 回目：\((x,y)\) から \((x,y-1)\) へ移動する
• \(\frac{S_N}{2}+b+1\) 回目から \(S_N\) 回目：\((x,y)\) から \((x-1,y)\) へ移動する

このような移動を \(D_i\) 回ずつで区切ってまとめて行うことができます（ \(1\) 番目と \(3\) 番目の移動がまざるとまずいのですが、 \(D_i \leq \frac{S_N}{2}\) がなりたつのでそのようなことは起きません）。移動中の原点からのマンハッタン距離の最大値は \(\frac{S_N}{2} \leq K\) であり、\(|x_i|+|y_i| \leq K\) が成り立つように行動できています。

総和が \(2K\) より大きい場合、\(L,R\) は存在し \(L=R\) が成り立ちます。まず上記の \(3\) 条件を満たすことが必要です。このとき、\(N\) 回の行動の方法として、原点から \(S_{L-1}\) 離れた格子点へ移動 → ちょうど \(D_L\) だけ移動して原点から \(T_{R+1}\) 離れた格子点へ移動 → 原点に戻る、という方法が考えられ、これは \(|S_{L-1}-T_{R+1}| \leq D_L \leq S_{L-1}+T_{R+1}\) が満たされれば可能です。最初の不等号は \(S_{L-1} < K \leq T_{R+1}+D_L, T_{R+1} < K \leq S_{L-1}+D_L\) から成り立つことがわかります。次の不等号も成り立つことが [1] からわかります。よってこの場合も上記の \(3\) 条件が必要十分条件です。

[3] 順番が固定されていない場合の判定問題

[2] での考察をもとに、\(D_i\) の順番が固定されていない場合の判定問題を考えます。まず \(M \leq K\) の場合、条件を満たすように \(N\) 回の行動をおえることがかならず可能です。以下、\(\frac{M}{2} \leq K < M\) の場合を扱います。

このとき、[2] で考えた \(L,R\) は必ず存在します。ここで \(K\) より大きい \(D_i\) が \(1\) つしかない（すなわち \(M\) のみ）である場合、\(D_i\) に \(M\) をもう一個追加しても移動距離 \(M\) の移動を連続で行えばよく、 判定問題の結果は変わりません。よって \(K\) より大きい \(D_i\) が \(2\) つ以上存在するケースだけ考えればいいです。

このとき、必ず \(L < R\) となるので判定問題は

• \(D_{i_1} + D_{i_2} + \dots D_{i_{n-1}} < K\)
• \(K \leq D_{i_1} + D_{i_2} + \dots D_{i_{n-1}}+D_{i_n}\)
• \(D_{i_n} \leq K+D_{i_1} + D_{i_2} + \dots D_{i_{n-1}}\)

を満たす集合 \(\{i_1,i_2,\dots,i_n\}\) を（共通部分を持たないように） \(2\) つ作れるか？という問題に帰着できます。

\(1\) 番目の条件から \(D_{i_k} < K\ (k\neq n)\) です。そして \(D_{i_n} \leq K\) の場合、\(3\) 番目の条件は必ず成り立ちます。すると \(D_{i_k} < K\ (k\neq n)\) という条件の下で \(1\)番目の条件が成り立たないとき、適切に \(i_k\) を除けばこのような条件を満たす集合を作り直せるので、

• \(D_{i_k} < K\ (k\neq n)\)
• \(K \leq D_{i_1} + D_{i_2} + \dots D_{i_{n-1}}+D_{i_n}\)
• \(D_{i_n} \leq K+D_{i_1} + D_{i_2} + \dots D_{i_{n-1}}\)

が成り立つ集合が作れればいいです。さらに \(D_{i_n} \leq K\) がなりたつとき、新たに \(K\) より大きい \(D_i\) を追加してもこれらの条件が成り立つことから、 \(K < D_{i_n}\) という条件を付けくわえてもいいです（ \(K\) より大きい \(D_i\) は \(2\) つ以上存在するので付け加えることは可能です）。このとき \(2\) 番目の条件は常に成り立つので

• \(D_{i_k} < K\ (k\neq n)\)
• \(D_{i_n} \leq K+D_{i_1} + D_{i_2} + \dots D_{i_{n-1}}\)

を満たす集合 \(\{i_1,i_2,\dots,i_n\}\) を \(2\) つ作れるか？という問題になります。\(D_{i_n}\) は明らかに小さいほうがいいので \(K\) より大きい \(D_i\) のうち小さいものから \(2\) つとればいいです。

以上の議論から \(K\) 以下の \(D_i\) の総和を \(S,\) \(K\) より大きい \(D_i\) のうち小さいものから \(2\) つを \(A,B\) としたとき、

• \(K\) 以下の \(D_i\) の部分和 \(s\) であって、\(A-K\) 以上 \(S-(B-K)\) 以下のものが存在するか判定せよ

という部分和問題に帰着されます。

\(S\) が非常に大きい場合の処理を考えましょう。\(K\) 以下の \(D_i\) を小さい値から追加していき、 総和が \(A-K\) 以上になった時点で追加をやめて部分和 \(s\) を作ります。足し合わせている \(D_i\) は \(K\) 以下なので \(s < A\) であり、\(A+(B-K) \leq S\) を満たせばこの部分和は上記の不等式を満たします。特に \(2M \leq S\) ならば必ずこの不等式は成り立つので \(S < 2M\) のときだけ考えればいいです。このとき \(D_i\) の種類数は \(O(\sqrt{M})\) なので 部分和問題は\(O(M\sqrt{M})\) で解くことができます。

これを用いて二分探索をすると \(O(M\sqrt{M}\log M)\) で解けますが、\(K\) 以下の整数であって \(\frac{M}{2}\) 以上 \(K\) 以下の \(D_i\) が \(2\) つ存在する場合、上記のような部分和はかならず存在することを考えると「 \(K\) 以下の \(D_i\) の集合」は高々 \(2\) 種類だけ考えればいいので \(O(M\sqrt{M})\) で解くことができます。