キャディプログラミングコンテスト2021に参加しました。

結果

A,B,C問題の3問正解でパフォーマンスが754。D問題が以降がやっぱり解けない。とはいえD問題もほとんど解けてて、たぶんコーナーケースを漏らしてるのが原因で7ケースがWA。

8割位通るけどなんかのコーナーケースを見逃してるのが原因でWAってのが多いから、頭を柔らかくしてコーナーケースを気付けるようになりたい。

A問題

算数ができれば解ける問題。何%引きって聞かれると戸惑うけど落ちつて計算すれば解ける。

B問題

A分後にはA台在庫が減ってるのでX-Aが1以上の店が考える対象となる。 X-Aが1以上の中から最小のPを求めれば良い。

C問題

1から順番に $a^{b}$ で表せるかどうかを確認するのは面倒だから、 $a^{b}$ で表せるものの数を数えてNから引くという方針で解きました。

$2 \leq a,b \leq N$ の範囲で全探索って思ったけど、 $N^{10}$ なので二重ループで処理しようとすると $O(N^{100})$ くらいだから全然間に合わない。少し考えて、bが2以上という条件から探索範囲は $a^{2} \leq a^{b} \leq N$ になるから、aは最大でも $\sqrt{N} = 10^{5}$ 程度って気づいたので、 $2 \leq a \leq \sqrt{N} , 2 \leq b \leq N$ 　かつ　 $a^{b} \leq N$ の範囲を二重ループで探索。bの範囲はもう少し小さくできそうだけど、とりあえずAC。