Codeforces #206, Division 2, B : Vasya and Public Transport

問題文

http://codeforces.com/contest/355/problem/B

概要

二種類の交通機関 A, B があり、それぞれいくつかの車両が走っている。
これらの交通機関で使えるチケットが四種類あり、i 番のチケットの価格は である。
チケットの詳細は次のようになる。

1. A または B の一つの車両を一回利用できる
2. A または B の一つの車両を何度でも利用できる
3. A, B どちらかの全ての車両を何度でも利用できる
4. A, B 両方の全ての車両を何度でも利用できる

それぞれの車両を利用したい回数が与えられる。
必要なチケット代の最小値を求めよ。

解法

一つの交通機関について考えます。
このとき、3 を一枚買うか、1 と 2 だけで利用するかの二通りが考えられます。
1 か 2 だけで利用する場合のチケット代は、一つの車両を利用する回数を とすると、 となります。
1, 2, 3 は全て一つの交通機関に関するもので、4 だけが二つに関わるので、購入パターンは次の二つです。

• それぞれの交通機関を 1, 2, 3 で利用する
• 4 を一枚買う。

それぞれの買い方を試して、最小値をとれば解けます。

コード

main = do
	[ [ c1, c2, c3, c4 ] , _, as, bs ] <- replicateM 4 $ do
		map read . words <$> getLine
	
	let
		f a = min ( c1 * a ) c2
	
	print $ min c4 $ min c3 ( sum ( map f as ) ) + min c3 ( sum ( map f bs ) )