259.1

スコアの決定アルゴリズムがよく分からない...。

250

整数配列が与えられるので、任意の隣接する二つの要素をマージしていくという操作を行い、先頭から見たときと末尾から見たときで同じ配列になるように変形する。このマージ作業の必要最小回数を答えよ、という問題。

先頭と末尾を比較して、小さい方を次の要素にマージしてやれば良い。同じなら次へ進む。

600

文字列が与えられるので、部分文字列のうち、一度しか登場しないアルファベットの数が最大のものの中で、辞書順で先頭のものを答えよ、という問題。

A文字目からA+B文字目までの部分文字列に登場するアルファベット一覧と、一度しか登場しないアルファベット一覧を持っておいて、それを更新しつつ、最適解を覚えておくというDPをやれば良い。

900

N枚のカードのうち、両隣のカードが類似しているものを除去するという作業の行える最大回数を答えよ、という問題。二文字以上共通の文字があれば類似しているとする。

まず、類似関係を各カードについて構成する。別のテーブルに隣接関係をメモしておいて、これを更新する。初期状態として隣り合うカードは隣接しているとする。AとBが隣接して、BとCが隣接しているときに、AとCの間に類似関係があればAとCも隣接する。(Bを消せばそうなる。)

後は隣接関係を利用してBFSして、左端のカードから右端のカードまでの距離を計算する。これが最小距離になるので、全体-(距離+1)が除去できるカードの最大数になる。