306.1

スコアと難易度に相関関係はなさそうなセット。方針は一瞬で立つが具体的に話が進まない、というのは難しいのは間違いではないが。

250

配列を、ある要素を先頭または末尾に移動する、という処理でソートするのに必要な最小ステップ数を答えよ、という問題。

ソート後の配列の連続する長さKの部分列に、ランダムに残りの要素が挿入されているとすると、残りの要素で、部分列よりも小さいもののうち大きいものから順に先頭に、部分列より大きいもののうち小さいものから順に末尾に、という風に追加するとソートが終了する。なので、元の配列からとびとびに要素をとって、ソート後の配列の連続する部分列を作り、その最長のものの長さを求めれば良い。

500

N個のランプがあり、そのうちのいくつかをトグルするスイッチがK個与えられる。最初すべてのランプが消えているとして、何通りランプのつけ方があるか答えよ、という問題。

ランプを次元と見て、一次独立なスイッチの個数を求めてやれば良い。要は行列のランクを求めるということ。

1050

有向グラフが与えらるので、長さK以下の閉路の総数を求めよ、という問題。

開始点と現在位置を状態にすると、その状態ベクトルの遷移行列が簡単に作れる。(実際には現在位置のみが影響するので、この行列の乗算はコンパクトにできる。)開始点と現在位置が一致するものの総和を保持する列を用意して、そこに値を流しこむようにして、行列乗算で総和を求めれば良い。...が行列がうまく書けない。