kuretchi's blog

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

AtCoder Beginner Contest 064

http://abc064.contest.atcoder.jp/

  • Rank: 394th
  • Performance: 1287
  • Rating: 1027 (+39) (Highest!)

全完だが早解き失敗。C が酷すぎた。

A: RGB Cards

解法

$(100r+10g+b) \bmod 4 = 0$ なら YES。

B: Traveling AtCoDeer Problem

解法

$max(a_1, a_2, \dots , a_N) - min(a_1, a_2, \dots , a_N)$ が答え。

所感

サンプルにつられて、ソートして先頭と末尾を見ていたが、よく考えたらソートする必要はなかった。

C: Colorful Leaderboard

以下、色を選べないレートの人を趣味、色を選べるレートの人をプロと呼ぶ。

解法

レートの色数を最小にするには、プロ全員が趣味の任意の色にすればよい。逆に最大にするには、プロ全員が異なる色、かつ趣味の色と被らない色にすればよい。

以上より、最小値$=max(1,$趣味の人数$)$、最大値$=$プロの人数。

所感

最初、プロは趣味の色のどれかから選べると解釈していて、WA。

その後、趣味が 0 人のコーナーケースに気づかず、なんだかんだで 2WA。

にゃーん (色々な思いが込められた鳴き声)。

D: Insertion

解法

先頭に (、末尾に ) を必要十分な数だけ加えればよい (辞書順最小なので)。

サンプルの )))()) が分かりやすいので、これを例に考える。まず、真ん中あたりにある () については、正しい括弧列なので考える必要はない。これを除いてみると )))) が得られるので、先頭に ( を 4 つ加えればよいことが分かる。

うまく実装するには、カウンタを 0 で初期化し、先頭から見ていって ) なら +1、( なら -1 をすると、カウンタが取った最大値が追加すべき ( の数になる。

所感

yukicoder で似たような ★1 問題があった気がする。