ABC165参加

ABC165に参加しました！！ コンテスト結果はこちら Fortranで2完, Pythonで1完, C++で1完でした.

A問題

Fortranでだしました.
$A$から$B$までループ回して$K$の倍数があったら'OK', なかったら'NG'を出力しました.

B問題

Pythonでだしました.
預金額を$Y$円としたときに$\lfloor Y/100 \rfloor $をループを回して足していって$X$円を超えたところでループを止めました.

C問題

C++でだしました.
最初貪欲でやっていったらサンプル2でWAだったので発狂して先にD解いてました.
Dとき終わったあとに制約とか見返してたら先頭を固定すれば$A$の場合の数は高々$10 ^ 9$だとわかったので*1全探索で行くことにしました.
DFSで考えられる数列を全列挙し, あたえられた条件に当てはまるか全ての条件を試して得点を足していきました.

D問題

紙でsample1を解いていたときになんか周期性を感じたので(は？)頑張って数式化してみました.
$x=Bc+d$ ($0 \le d \le B-1$)とすると,
$\lfloor \frac{Ax}{B} \rfloor = \lfloor \frac{ABc+Ad}{B} \rfloor = Ac+ \lfloor \frac{Ad}{B} \rfloor$
$A \times \lfloor \frac{x}{B} \rfloor = Ac$
よって
$\lfloor \frac{Ax}{B} \rfloor - A \times \lfloor \frac{x}{B} \rfloor = \lfloor \frac{Ad}{B} \rfloor$
ここで$\lfloor \frac{Ad}{B} \rfloor$は単調増加なので, $N < B-1$なら$d$に$N$を代入して, $N \ge B-1$なら$d$に$B-1$を代入して計算し, 出力するようにしました.
今回開始が10分遅れだったのに終了時刻がいつもどおりだと勘違いしてC問題でやみくもに提出しまくって3ペナ生やしてしまいました…
やみくもに提出せず, ペナを生やしていなければパフォが30くらい上がっていたのでもったいなかったです…
ただ最近あまり精進できていなかったのに4完できたのは偉いと思います.
みんなほめてください(は？

*1:本当はそれよりもっと少なくて${} _ {20} \mathrm{C} _ {10}$らしいです