kuretchi's blog

競技プログラミング初心者のブログです。

AtCoder Grand Contest 015

http://agc015.contest.atcoder.jp/

  • Rank: 664th
  • Performance: 1094
  • Rating: 946 (+21) (Highest)

2完。時間がかかりすぎた。

A: A+…+B Problem

解法

  • $A > B$ を満たす数列は存在しないので、$0$。
  • $N = 1$ かつ $A \neq B$ を満たす数列も存在しないので、$0$。
  • $A = B$ の場合は $A (= B)$ を $N$ 個持っているパターンしかないので $1$。

以上をフィルタした後、$(b - a)(n - 2) + 1$ が答え。

所感

サンプルが通ることをきちんと確認しなかったことが原因で気付かなかった実装ミスをこじらせ、2WA

B: Evilator

考察

制約の

  • $S_1$ は U である
  • $S_{|S|}$ は D である

より、任意の2階間を移動することができる。

ある階が U なら、それより上の階へ移動は明らかに1回で可能だが、下の階へ移動するときは、それより上の階に D である階が存在することが保証されているため、その階へ移動し、そこから目的の階へ移動することで高々2回で移動ができる。D の場合も同様。

解法

$S$ を前から見ていき、$S_i$ が

  • U なら $|S| - 1 - i$ + $2i$
  • D なら $2(|S| - 1 - i) + i$

をカウント。最後に総和を出力。

所感

#define int long long を書けば AC。