AtCoder Beginner Contest 024

 うまく出来た!この記事書いてたらARCが始まってた。

結果

 400/400 61:26 11位相当


 開始時刻 2017/08/06 19:52:00 提出履歴

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

 3:15(AC)
 A*S+B*Tに対して、S+TがK以上ならC*(S+T)を引く。三項演算子を使うと綺麗に書ける。

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

 7:48(AC)
 min(A[i+1]-A[i], T)を順次足していく。最後は必ずT。

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

 17:22(AC)
 貪欲に組めばK回のO(D)で済むので、全体でO(KD)で答えが出せる。

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

 61:26(AC)
 以下のような式変形をする。

  A={}_{r+c} C _r, B={}_{r+c+1} C _{r}, C={}_{r+c+1} C _{r+1}

  \displaystyle \frac{B}{A}=\frac{r+c+1}{c+1}, \frac{C}{A}=\frac{r+c+1}{r+1}

  \displaystyle r=\frac{B-A}{A}(c+1), c=\frac{C-A}{A}(r+1)

  \displaystyle r=\frac{(B-A)C}{AB-BC+CA}, c=\frac{(C-A)B}{AB-BC+CA}

 あとはこれを109+7を法に計算すればいい。MODの割り算は逆元をかけましょう。

感想

 D問題にスッキリ答えを出せたのが嬉しい。数学問題はできると楽しいなぁ。