Codeforces Round #322 (Div.2) - 君はまるで砂漠に咲く、一輪の花。

A. Vasya the Hipster

ざっくりと大意

・赤い靴下がa個、青い靴下がb個あり、それらは全て使い捨てる。
・靴下を履ける最大日数を色違い、同色の順で出力する。靴下の履き方は流行の左右色違いで履くのを優先する。

方針のようなもの

・靴下の数は減るだけで増える(洗濯で回復or購入で補充)ことがないので楽そう。

a,b=map(int,raw_input().split())
print min(a,b),(max(a,b)-min(a,b))/2

色違いで履ける最大回数は数が少ない方の靴下の数になる、赤青が同数ならそれで終わる。どちらかが多かったら残った靴下の数を2で割ると左右が同色で靴下を履いた回数になる。

B. Luxurious Houses

ざっくりと大意

・n件の住宅はそれぞれ\(h_i\)階建である？
・住宅は一列に並んでいて左から右に1,2,3..とナンバリングされている。
・右の家より豪華になるように増床したいけど、増床するわけではない？？
・一番右の家の増床数は0で確定で大丈夫。
・\(a_i\)が右隣りにある複数の家たちより小さい時は最も大きくなる増床数を見積もるだけで\(a_i\)の大きさは更新されない。

方針のようなもの

・右側の家からシミュレートする。

python

n=int(raw_input())
l=map(int,raw_input().split())
ans=[0]
cnt,chk=l[-1],1
for i in l[-2::-1]:
    if i<=cnt:
        ans.append(cnt-i+1)
    else:
        cnt=i
        ans.append(0)

print ' '.join(map(str,ans[::-1]))

入力例1で考えると\(a_4\)は増床0にして大きさ2をメモ、\(a_3\)は大きさ2より大きくするための増床は2で大きさは変えない(増床するわけではないから)でメモはそのまま、\(a_2\)は大きさ2より既に大きいので大きさ3をメモする、\(a_1\)は大きさ3より大きくするための増床は2で大きさは変えない、\(a_0\)は大きさ3より大きくするための増床は3となる。問題文が非常に分かりにくい気がするし、入出力に関しての補足noteもなく不親切だが解法自体の難易度はそうでもない気がする。