Codeforces Round #433 Div.2 A,B,C,D

 

Problem - A - Codeforces

a<b,a+b=n に対し既約分数 a/b が最大になるように求める。

 

条件よりaは最大でもn/2であり、a/bが最大になるときaは最大なのでa=n/2,b=n-aから順番に最大公約数が1かを調べる。

 

Problem - B - Codeforces

n個の家の内k個が埋まっており、どこかの家に隣接した家を選ぶ時の最小値と最大値を求める。

 

当たり前だが k=0 or n の時は何れの家にも入れないので両方0。それ以外では、最小値は端から埋まっている場合だから1、最大値は埋まっている一つの家に対して候補は左右の2個だから、n個の家を超えないように注意して 2*k個。

 

Problem - C - Codeforces

c1,c2,c3...cn に対し、Σc_i * (t_i - i) (ただし (t1,t2,t3...,tn)は(k+1,k+2...,k+n)の順列であり、t_i>=i) の最小値を求める。

 

まず、t_i = k+1 について考えると、t_i >= i の条件より i = 1,2,...k のいずれかと分かる。あるc_iについて、後に選べば選ぶほど、係数 t_i が大きくなるので、コストを最小化するには現在選べるc_iの内最大のものを選べばよい。実装はpairのpriority_queueが便利。

 

Problem - D - Codeforces

1-n番の街にいる人たちが0番の街に集まり、k日を過ごし、1-n番の街に帰らねばならない。m個の飛行機はd日目にf(f:1-n)番からt(t:0)番の街に飛ぶ、または、f(f:0)番の街からt(t:1-n)番の街にあるコストcで飛ぶ。条件を達成するためのコストの最小値を求める。

 

まず行きだけを考えると、dが小さい飛行機から見ていくことで(バケツソートが早い)、全ての街から0番の街に飛んだ初めての日(fDay)と総コストが分かる。その次の日からは、コストが以前使ったものより安かったものだけを更新することで、{(fDay,sum1),(fDay+1,sum2),...(Max_Day,sum_M)}というpairの配列が作れる(もちろんsum1>=sum2>=...>=sum_M)。

同様に帰りを考えると、dが大きい飛行機から見ていくことで同様の配列が作れる。

行きで到着する日 D (fDay <= D <= Max_Day) について、D日で行くときのコストと、(D+k)日後から帰るときのコストの和の最小を調べる。