TCO 2010 Round 1

タイトルの付け方の規則を忘れた...。

250

二つの文字列が与えられるので、各文字について、前後の文字に書き換える処理をできるだけ少ない回数することで、同じ文字列に変形せよ、という問題。

基本的には小さい文字に合わせるわけだけれど、aとzがつながっているので、aに到達できるならaにする。二つの文字の距離が13以上ならaを通るパスがある。

500

二つの整数XとYが初期値1で与えられる。各ステップで、両方の和でどちらかの値を更新する。Xが指定された値に到達するまでの更新を文字列として表現したとき、一番短いもので辞書順で最初のものを答えよ、という問題。

このステップは、大きい方から小さい方を引くことで逆に戻れる。Xが与えられているので、Yはそれよりも小さい値であることが分かり、全部確かめていけばおしまい。途中で中途半端に文字列を復元すると終わらないので、長さ比較と辞書順比較を効率良くやるだけ。

1000

有向グラフが与えられ、枝にコストが付与されている。ノード0から今までに通っていない点を巡回して0に戻るパスのコストを指定された値から引いたものが、利益として加算される。パスは何本作成しても良い。このとき最大利益を求めよ、という問題。

グラフ問題なので良く分からない...。コストが正になる閉路が存在する限り追加していく感じにやれば解けるんじゃないかな？