読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

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

概要

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

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

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

解法

一つの交通機関について考えます。
このとき、3 を一枚買うか、1 と 2 だけで利用するかの二通りが考えられます。
1 か 2 だけで利用する場合のチケット代は、一つの車両を利用する回数を a_i とすると、\sum{ min( c_1 * a_i, c_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 ) )