351.1

かなり簡単めなセット。典型問題が多めなので、やっても良いのかも。

250

大中小3種類の価値のある通貨があって、一つランクが落ちる方に違えば1:9で、一つランクが上がる方に違えば11:1で交換してもらえる。このとき、ある支払いをするときのそれぞれの必要枚数と、それぞれの手持ち枚数が与えられるので、必要な交換回数の最小値を答えよ、という問題。

交換に優先順位をつけた上で、条件を満たさないところを局所改善していく。綺麗に実装する方針がいまいち...。

500

ABCからなる文字列が与えられるので、同じ文字が3回連続しないように並び替えたい。このとき、移動しない文字の数の最大値を答えよ、という問題。

ABCのそれぞれの数を状態にして、位置があってるものの数の最大値をDPで求める。このとき、直前二つの文字のパターンも覚えておけば良い。

1000

5x5の盤面に1から25の数字を一個ずつ配置したいが、各行は昇順にソートされてなければならない。各行に高々1個埋まった状態の盤面が与えられるので、辞書順で最初の盤面を答えよ、という問題。

取り敢えず左上から順に一番小さいものを埋めてみて、答えがあるかを調べる。あればそのまま次のマスに移動し、なければ一つ大きい値で埋めてみる。答えがあるかどうかは、盤面を見て、埋まってない範囲の両端にある値(左端に数字がなければ0で、右端に数字がなければ26などとしておく)とそこに入れるべき数字の数を調べる。大きい順に数字を見ていって、それが入る範囲で、かつ一番左端の値が大きい(要はギリギリのところ)範囲に割り当てていく。割り当てができない範囲がなければ何かしら埋める方法がある。(日本語ひどいけれど、区間グラフをスイープしているだけ。)