kuretchi's blog

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

AtCoder Beginner Contest 063

http://abc063.contest.atcoder.jp/

  • Rank: 118th
  • Performance: 1255
  • Rating: 988 (+42) (Highest)

3完。そろそろ水色が見えてきた気がする。多分気がするだけ。

A: Restricted

解法

#include <stdio.h>

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    if (a + b >= 10) puts("error");
    else printf("%d\n", a + b);
    return 0;
}

所感

58 秒。C と Haskell のどちらで書くか悩んで 5 秒、VSCode のスニペットがクソでさらに 5 秒ロス。LL 系の言語を早解き用に覚えようか悩んでいる。

B: Varied

解法

重複を取り除き、長さが変われば no

import Data.List (nub)
 
main :: IO ()
main = putStr . solve =<< getLine
 
solve :: String -> String
solve s = if length (nub s) == length s then "yes" else "no"

所感

1 分 27 秒。これくらいなら 1 分は切りたい。

C: Bugged

解法

合計が 10 の倍数のときは、10 の倍数でない配点のうち最小のものを引けばよい。配点がすべて 10 の倍数のときがコーナーで、0 になる。

所感

配点をソートし忘れたことが原因で 1WA。なお DP 解は思いつきはしたが実装が面倒くさかったのでスルー。

D: Widespread

以下、魔物 $i$ を中心に爆発を起こすことを、魔物 $i$ を爆発させるという。

方針

体力が一番大きい魔物を爆発させるのが常に最適であることは容易に分かる。ただし、愚直にシミュレートすると明らかに間に合わないので、少し工夫する。

TLE 解法

最大の体力を持つ魔物が変わるまでは同じ魔物を爆発させればよいので、そこだけ $O(1)$ にする。これだけだとサンプル 3 ($A = 2, B = 1, h_{max} = 10^{9}$) が TLE する。

WA 解法

爆発が $h_{max}/A$ 回以上必要なことは自明なので、その回数だけ先にシミュレートしておく:

  • $0 \leq i \leq N$ について、 $h_i-B\cdot(h_{max}/A) > 0$ であるような魔物 $i$ を爆発させる。
  • 爆発が $h_{max}/A$ 回起こるまで回す。

大して変わらなさそうだが、これで一応サンプル 3 が通る。ただし、TLE は取れないし WA が生えた (嘘解法?)。

AC 解法

ここから先は思いつかず。

$T$ 回以内の爆発で魔物を全滅させることが可能かどうかを返す関数 $f(T)$ を考えると、$f(t) = True$ であるような任意の $t$ に対して、 $f(u) = True\ (u > t)$ が常に成り立つ。というわけで、後は $f(T) = True$ となるような最小の $T$ を二分探索。

所感

明らかに研鑽が足りなかったが、これで今後の類似問題は多分解けるようになった。