256.1

今までで一番簡単な問題セット、のような気がする。

250

27個の数字を使って、3x3x3の立方体を作成する。高々1回だけ任意の二つの数字をスワップして良いとき、三つの連続する数字(斜めは含まない)の合計の最大値と最小値の差分の最小値を求めよ、という問題。

実装あるのみ。

450

高々20ノードからなるグラフの最大クリークの個数を求めよ、という問題。

20ノードのうちのすべての組み合わせについて、クリーク判定をする。クリークだったら、自分より小さいノード集合については最大クリークではないので、そのためのフラグを管理しておけば良い。

1000

2次元文字配列が二つ与えられる。その双方に出現する共通部分文字配列のうち、最大の正方形のものの大きさを答えよ、という問題。

出題者の意図としてはDPしてください、というもの。ある点からNxNの正方形ができて、その右、下、右下の3か所でNxNの正方形ができるならば、その点からN+1xN+1の正方形ができる、ということをやる。計算量は辺の長さをNとするとO(N^5)で、N=50なので終わるっぽい。

結局これができてしまうので、すべての点について、NxNの正方形が一致するかどうかを検証するのでも間に合いそう。これはO(N^6)になるのだけれど、その点から作成可能な正方形の辺長と、今までに作った正方形の辺長などから、適当に無駄な計算を削減すれば終わるっぽい。