AtCoder Beginner Contest 165 解説

https://atcoder.jp/contests/abc165

ABCの存在を忘れてて遅刻した。108位。EがWAで最初のWAは偶奇によるバグでそれはすぐ直せたんだけど、二つ目のWAに手間取った。原因は出力のしすぎだったんだけど、Mが最大のケースでデバッグしてたせいでバグに気付くのが遅れた。序盤の難易度が高かった気がする。

A問題

A以上で最小のKの倍数は$\lceil A/K \rceil K$であり、これがB以下であるかを確かめる。

B問題

お金が指数関数的に増えるので、大した年数かからずに10^18を超える。なのでシミュレーションで解ける。

C問題

制約を満たす数列はC(10+9,9)=92378通りしかないので全探索。雑学として、少なくともgoogleとduckduckgoは19 choose 9で検索すると計算結果がでてくる。競技中は気づいてなかったんだけど、重複組合せの列挙が標準に含まれている言語はそれを使うと楽。

D問題

目的関数がBの周期を持っていることに気付くと、$x$は$0 \le x \le B-1$の範囲で動かせばいいことが分かる。この範囲では$\lfloor x/B \rfloor=0$なので、目的関数は結局$\lfloor Ax/B\rfloor$になる。これは単調増加関数なので$x$が最大のとき最大値を取る。つまり答えは$\lfloor A \min(N, B-1) / B \rfloor$である。

補足　周期性の証明は、$\lfloor a/b \rfloor= (a - (a \bmod b))/b$の変形を使うとできる。自分はこれで気づいた。

E問題

対戦場の組の距離がどれも異なれば、同じ人が組になることはないので、異なるように設定すればいい。

F問題

lower_boundを使うDPをベースに解法を考える。次のクエリが飛んでくるので処理してください。

• 数列の末尾にxを追加する。
• 数列の末尾を削除する。
• 現在の数列のLISを計算する。

追加したときにDP配列は1要素だけ変化するので、何が変化したかを覚えておけば元に戻すことができる。なのでこのクエリはどれもO(log N)で処理できる。あとはDFSすればよくて、親から子に降りるときに要素を追加して、子から親に戻るときに要素を削除すればいい。