AtCoder Beginner Contest206に参加しました。
結果
A,B,C問題の3問正解でパフォーマンスが879でした。
D問題が解けそうで解けず、E問題がもうすこし頑張れば解けそうな気がした。結局時間は足らなかったけど…
A - Maxi-Buying
問題文の通り税込価格を計算して、計算結果に応じて適切な文字列を表示させる。 注意点は言語によっては計算結果を整数型に変換する処理が必要かもしれないくらい。
B - Savings
ループ文で1+2+・・・を計算してN以上になったタイミングで何日目なのかを表示させれば良い。
少し考えると、1+2+・・・+X=なので
になる。ほぼ
だから
あたりの値が答えになりそう。
C - Swappable
問題文を読むと結局、Aの各値に対して注目しているの値と異なる
の個数を求めて足していけば答えになる。
Aにはどの値が何個含まれるか数えておき、各値(Xとする)に対してを足していけば良い。
E - Divide Both
問題文と制約を読むと全探索は明らかに難しそう。条件を満たす整数組を数え上げるのは難しそうなので全体から条件を満たさない整数組を除外していき、残ったものを数えていけば良さそうな気がする。
条件を見ると
からx,yは互いに素ではない。
から
となる。つまりx,yの最大公約数がxではない → yはxの倍数ではない。
が言える。また、x<yだけ考えて、最後に2倍すれば答えになりそう。 後はL以上R以下の範囲で、ある値xに対して
- x以上
- xの倍数
- 互いに素じゃない
数を探してx以上R以下の値から除外すれば求めたい条件を満たすyになると思う。
互いに素じゃないという部分が難しい気がした。約数列挙とかエラトステネスの篩とか使って求めようとしたけどうまくできなかった…