Beta2

一回だけかと思ってたら結構続くみたい。

300

0と1からなる二次元配列の2x2のマスを90度どちらかに回転させる操作を行ったとする。前の状態がと後の状態が部分的に伏せられて与えられるので、後の状態として可能なもので辞書順で先頭のものを答えよ、という問題。

どこを回すか全探索。無矛盾になるように伏せられたマスを埋めて、辞書順で先頭を探すだけ。

450

N都市の間に道を引くか、空港を置くかすることで、全都市間を移動できるようにする最小コストを答えよ、という問題。

MSTなんだけれど、各ステップで残りを空港で終わらせた時のコストを計算して、最小値を答える。1都市の場合に初期値の設定が非常にまずかった...。

900

ある文字列が別の文字列の接頭辞にならないような文字列集合を考える。文字がK種類で、N要素の集合を作るとき、各文字のコストが与えられるので、文字集合の中に登場する文字のコストの総和の最小値を答えよ、という問題。

Greedyに一番小さいコストのものを追加していく、というのはダメらしいというところまで。