AtCoder ABC165 参加記 - 雄大な大福

5/2 に開催された AtCoder の ABC165 に参加したので参加記を書いていこうと思います。

非常にあったまりました。個人的には激ムズセットだったという感じです。
A, B, C, D の 4 完でした。

A 問題

問題概要

整数 A, B, K が与えられる
A 以上 B 以下の範囲に K の倍数があれば OK と、なければ NG と出力する。

解答

実際にループを回して試せば良いです。

提出したコード

B 問題

問題概要

整数 X が与えられる
もともと 100 円預金していて、1 年で 1 % の利子がつく
初めて預金が X 円以上になるのはなん年後か

解答

サンプル 2 に最大ケースが親切に置いてあり、答えが余裕で 2 秒に間に合うことがわかります。
シミュレーションしていけばいいです。

提出したコード

C 問題

問題概要

正整数 N, M, Q と整数の組 $(a_i, b_i, c_i, d_i)$ が Q 組与えられる
長さ N の整数列 A : $1 \leq A_1 \leq A_2 \leq ... \leq A_N \leq M$ を考える
数列の得点を $A_{b_i} - A_{a_i} = c_i$ を満たすような i について $d_i$ の総和とする
得点の最大値を求める

解答

問題が長くてわかりづらかったです。
制約 N, M, Q がそれぞれ
$2 \leq N \leq 10, 1 \leq M \leq 10, 1 \leq Q \leq 50$ と
小さいので作り得る数列を DFS で全探索することにしました。
しかし、普通に全探索すると $10^{10}$ とTLE してしまいます。
そこで新しく数列に値を追加する際に最後尾よりも小さい値の際は continue するように枝刈りをしました。