修行の日々

ずいぶん久しぶり(一月半ぶり)にuvaでも解くかなぁ
ということで問題を見てみた。
適当に英語が短いやつ…
10690番のExpression Againというやつを考えてみることに。
非負整数N,M(N,M<51)とN+M個の整数列X(-50〜50)が与えられるとき、
(x1+...+xN)*(y1+...+yM) (xi,yi∈X,重複なし)の最大/最小値を求める問題。
たとえば、
2 2
1 2 3 4
ならば答えは
最大値:25 (一例:(1+4)(2+5))
最小値:21 (〃 :(1+2)(3+4))
になる。

まずは自明な解法。
適当に全パターンを調べる方法。
この解法の計算量は
式を作る組み合わせの数から、大体
(N+M) C N
ということになる。
NMはそれぞれ50以下なので、これは現実的な大きさでは無さそうである。

上の方法が全然間に合わなさそうなのでDP解を探してみる。
ポイントは整数列が-50から50のレンジに収まっているということである。
この問題は整数列の和を二つ(整数列xとyの和)作るのだが、
そのおのおのの整数列のレンジが-2500〜2500になるのである。
ゆえに、整数列の和のペアは5000^2通りしか存在しないということになる。
これは25K個なので余裕でもてそうである。
注意すべきなのは
(1),(0,2)
(0,1),(2)
これらは両方とも和は1と2であるが、
それぞれに含まれる数の個数が異なる。
これらは区別する必要があるので、
両方を別々の状態として保持する必要がある。
具体的にはそれぞれにいくつ数が含まれるかなので、
最高でmax(N,M)通りありうる。
よってこのような状態を考慮すると整数列の和のペアは
5000^2*50=1M強個となる。
苦しいが何とかなる範囲か。

ここで整数列の前からn個目までを用いて作ることの出来る
整数列の和のペアの集合が求まっていれば、
整数列の前からn+1個目までを用いて作ることの出来る
整数列の和のペアの集合を求めることが出来る
ので、この辺でDPできる。
答えは最終的にありうる整数列和ペア全体から最大・最小を
抜き出せばよい。

で、計算時間の見積もりだが、
ありうる状態の個数は約1M、ループごとにこれを全部スキャンし、
その回数はN+M=100回。さらに問題は110問であるから、
全部掛けると必要なCPU時間は10G*(定数)ほど。
これが6秒…はちょっと厳しいかもしれない。
まさか配列のアクセス+計算が1クロック以下と言うことは無かろう…
というか、自前の環境で一番サイズの大きいケースの問題
1つ解くだけで1秒かかるんだけどな…
すべての問題がN=M=50ではないと思うので、
その辺で小手先時間稼ぎで何とか成るかもしれないが、
めんどくさいのでやらない…保障も無いし。

とりあえず出来たものを送ってみたが、
当然のごとくTime Limit Exceedであった。
幸先の悪いスタートだ。
多分もっとオーダの小さいアルゴリズムが存在するのだろう。
というか、なんというか、そんなことよりも
自分のアルゴリズム実装能力がすごく落ちているのにびっくり。
動くものが出来るまでめちゃくちゃ時間がかかってしまった。
やっぱり練習は大事だなぁ…しみじみ。