232.1

久し振りに練習。来週GCJともいう。やっぱり昔のセットは簡単ですね。

250

文字の二次元配列が与えられて、特定の文字列が縦・横・ななめのいずれかに現れる最初の位置を答えよ、という問題。

二次元配列から切り出して、プレフィックスになっているかどうかをチェックしてみるだけ。(指定される文字列が複数なのと、自前で比較ルーチン書くのが面倒なのとを勘案すると結構妥当な方法だと思う。)

650

ある条件に対して陽性か陰性かわからないN個の液体について、それぞれの一部を取り出して別のものに移動する、という処理を数回行った結果、N個の液体が陽性か陰性かが与えられる。元のN個の液体の状態を答えよ、という問題。類推不可能なものについては分からないものは分からないままで良いが、矛盾する場合はその旨答える。

配合後の状態で、N個の液体が初期状態のどれに起因するかをまず計算する。その結果が陰性のものについては全部陰性。陽性のものについては陰性のものを全部除去した上で一個だけに起因するならばそれが陽性。何も残らなければ矛盾。たくさんあるなら分からない。これを全部について試せばおしまい。

900

N個の商品を買うことを考える。それぞれはポイントのみで購入することも可能で、現在Pポイントあり、それをすべて使い切らなくてはならない。またK個だけ半額で購入することができ、残りは定価のD％オフで変える。必ずK個は半額で買わないといけない。このとき、支払う金額の最小額を答えよ、という問題。

ポイントは15000で、商品は50個なので、15000*50*50のDPをやるだけ。テーブルの初期化を大きな値でやるのではなく、D％オフで買った場合の値段にしておくと良い。(毎回初期化していたら間に合わなかった＠Javaということ。)メモリ制約から、15000*50のテーブル二枚でやりくりする必要がある。