AtCoder Beginner Contest 024 参加記

AtCoder

はい。 oo-- http://abc024.contest.atcoder.jp/
Cは問題文をもっとよく読んで解こうとするべきだったなぁと。。。

A - 動物園

python

a,b,c,k=map(int,raw_input().split())
s,t=map(int,raw_input().split())
ans=chk=0
ans=a*s+b*t
print ans if s+t<k else ans-(s+t)*c

合計金額を計算してk人以上の場合だけ値引きの計算をして出力する。

B - 自動ドア

python

n,t=map(int,raw_input().split())
ans=chk=0
a=int(raw_input())
n-=1
chk=a+t
ans+=t
 
while n:
    n-=1
    a=int(raw_input())
    if a<=chk:
        ans+=t-(chk-a)
    else:
        ans+=t
    chk=a+t
print ans

よくわからなかったけどこの時間までは自動ドアが開いたままというのをchkに記録して、新たな入客が空いてる最中に来たら、開いてる時間はchkと来店時間の差を求めて更にtから引いて差を求める。その差を累計のansに加算する。
開いてるときに来なかった、新たな入客の時間がchkより大きかったらtをansに加算する。
自動ドアがいつまで開いていることになるかは既に開いてた、開いていなかったに関わらずt後になる。

C - 民族大移動

python

n,d,k=map(int,raw_input().split())
plan,allow=[],[]
ans=[]
for i in xrange(d):
    allow.append(map(int, raw_input().split()))
for i in xrange(k):
    x,y=map(int,raw_input().split())
    for i,j in enumerate(allow):
        if j[0]<=x<=j[1]:
            if j[0]<=y<=j[1]:
                ans.append(i+1)
                break
            elif abs(y-j[0])<abs(y-j[1]): x=j[0]
            else: x=j[1]
for i in ans:
    print i

勝手によく読まずにグラフ問題っぽく勘違いして探索の仕方が面倒くさそうで逃亡したけど貪欲法で大丈夫だったそうです。。なのでC問題はコンテスト後に書いてみてAC出たものです。
移動可能な日は常に目的地に近くなるように移動してしまってよかった。現在地より目的地の数のが小さい場合は移動可能先で最も小さい数の場所へ移動する。目的地の数のが大きい場合は移動可能先で最も大きい数に移動する。目的地の数に少しでも近くなるならその時は必ず移動してしまってよい、というか移動しておかないと最も早い移動パターンでなくなってしまう。それの証明は略します。