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

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

AtCoder Beginner Contest 024 ◯◯◯×

競技プログラミング atcoder

久々の競技プログラミング
53位。D問題が解けない(´・ω・`)

公式の解説

www.slideshare.net

A: 動物園 - AtCoder Beginner Contest 024 | AtCoder

動物園の大人と子供の料金とそれぞれの人数、団体割引の金額が与えられるので、料金の総額を答える

やるだけ

def ln():
    return map(int, raw_input().strip().split())
A, B, C, K = ln()
S, T = ln()

print S * A + T * B if S + T < K else S * (A - C) + T * (B - C)

B: 自動ドア - AtCoder Beginner Contest 024 | AtCoder

自動ドアを人が通る時に\(T\)秒間開いている
人が通る時間が与えられるので、合計何秒間開いているかを求める

人と人の間隔が\(T\)秒以内ならその時間、それ以上なら\(T\)秒開いていると考えて計算する

def n():
    return int(raw_input())
def ln():
    return map(int, raw_input().strip().split())

N, T = ln()
A = []
for i in xrange(N):
    A.append(n())

before = -1
cum = T
for i in xrange(N - 1):
    j = i + 1
    cum += min(T, A[j] - A[i])
print cum

C: 民族大移動 - AtCoder Beginner Contest 024 | AtCoder

\(1\)から\(N\)の街がある
また始点と終点の番号が与えられる
\(i\)日目には\(L_i\)から\(R_i\)の間の範囲しか移動できない場合の最短で終点に行けるまでの日数を求める

貪欲法で、行ける限りできるだけ近づいた街だけを持っておけばよいらしい
自分は左端と右端の範囲を持って計算した

def ln():
    return map(int, raw_input().strip().split())

N, D, K = ln()
LR = []
for i in xrange(D):
    LR.append(ln())
ST = []
for i in xrange(K):
    ST.append(ln())

for i in xrange(K):
    s,t = ST[i]
    x = y = s
    if x <= t <= y:
        print j + 1
        continue
    for j in xrange(D):
        l, r = LR[j]
        if l <= y < r:
            y = r
        if l < x <= r:
            x = l
        if x <= t <= y:
            print j + 1
            break

D: 動的計画法 - AtCoder Beginner Contest 024 | AtCoder

格子状の道を一番左下から右か上に移動してある地点にたどり着く場合の数を考える
ただしそれぞれの場合の数は1,000,000,007で割った余りとする
ある地点とその右とその上の地点の場合の数が与えられた時、それが右何番目で上何番目の位置かを答える

本番では答えられず

modを取らない場合、格子状の道を通る場合の数は二項係数になる
二項係数の関係の式を計算すると位置を求める式がわかる
四則演算しか使っていないので、modをとった場合も逆元などを使って計算できる
mod 1,000,000,007の時のある数\(x\)の逆元はフェルマーの小定理より\(x^{1,000,000,007-2}\)で求められるので、ダブリングで計算する

Pythonだとダブリングとか気にせずpow関数を呼べばよしなにしてくれる

MOD = 1000000007

a = input()
b = input()
c = input()

C = (b * c - a * c) * pow(b * a - b * c + a * c, MOD - 2, MOD) % MOD
R = (b * c - a * b) * pow(c * a - b * c + a * b, MOD - 2, MOD) % MOD
print C, R
-->