251.1

250

入力文字列を空白で単語に切る。単語中の母音のうち、両側に子音が存在するものを削除した結果を答えよ、という問題。

子音は隣接している必要はないが、単語内で右側と左側に存在する必要がある。実装するだけ。

500

ドミノを並べることを考える。最初は好きなものを置くことができる。任意の端に、値が一致するものを追加することができる。ドミノを置いたときに、両端のスコアが5の倍数ならば、それが得点に加算される。両端のスコアは、1個のときはそのドミノに書かれている数字の合計で、そうでないときは両端に出ている数字の合計。ただし各端のドミノが同じ数字からなるドミノの場合は、両方の数字を合計する。(右端に2:2のドミノがあれば4とカウントする。)このとき、与えられたドミノを任意の順番で並べ、得られる最高得点を答えよ、という問題。ドミノを全部使い切る必要はない。

最初の一個さえ向きを決めてしまえば、後は並べ方は一通り。ドミノは高々10個までなので、10!通りの並べ方のうち、可能なものをすべて考える。後はその中でどういう順番で並べると良いかを計算する。これはDPで求まる。

1000

アーティストと曲数が与えられるので、各アーティストの曲がなるべく隣接しないように配置せよ、という問題。隣接しない、の定義は、あるアーティストの曲が配置されてから、次に同じアーティストの曲が配置されるまでの距離が最大であることと定義する。同じ値になる配置が複数ある場合はアーティスト名で見て辞書順で最初のものを答える。

同じアーティストについて、1曲の場合はどこにおいても同じ、2曲の場合はできるだけ離したい、3曲以上の場合は最初と最後をできるだけ離して、それ以外はどこにあっても変わらない。(中に置いてあるものは左に動かすと右から離れるけれど、左に近付くので意味がない。左右逆にしても同じ。同じアーティストのものでスワップしても意味がない。)このことから、2曲以上の場合には両端に適当な重み付けをする必要があり、それ以外のものは名前順。

つまり、最初の一曲の重みは-1にして最後の一曲の重みは+1にする状況で、その重みを優先してソートし、重みが同じならば名前順にソートするようなソートルーチンを書くだけ。