1/28 Virtual Contest 解法一覧
https://kenkoooo.com/atcoder/#/contest/show/dfe2ad98-8e29-40b6-b570-7782091b5527
Section 1
1. ABC148 C - Snack
https://atcoder.jp/contests/abc148/tasks/abc148_c
最後のケースに $9999900000$ という巨大なケースが存在する。このケースから、$1$ から順に全ての数字を確認するのは不可能であることがわかる。
用意するお菓子の個数を $N$ とする。
$N$ 個のお菓子を $A$ 人に対して均等に配れるなら、$N$ は $A$ の倍数である。
また、$N$ 個のお菓子を $B$ 人に対して均等に配れるなら、$N$ は $B$ の倍数である。
このことから、$N$ は $A$ の倍数であり $B$ の倍数である必要がある。そのようなもののうち、最小のものを
最小公倍数
と呼んでいた記憶はないだろうか？
今回は、$A$ と $B$ の最小公倍数を求めればそれがそのまま題意を満たす。
なお、最小公倍数のことは一般に $\mathrm{LCM}$ (Least Common Multiple の略)と呼ばれる。同様に、これとセットとなる最大公倍数は $\mathrm{GCD}$ (Greatest Common Divisor) と呼ばれる。
「最小公倍数 java」などと検索すると GCD を求め、そこから LCM を求めるプログラムが見つかる。いったんそれを貼って提出すれば AC は得られる。
ただし、64 bit 整数型、Java では long を使う必要があるので注意。
以下に、その仕組みを説明する。
最小公倍数の求め方
$A$ と $B$ の $\mathrm{LCM}$ を $\mathrm{lcm}(A, B)$ と表記する。同様に、$A$ と $B$ の $\mathrm{GCD}$ を $\mathrm{gcd}(A, B)$ と表記する。
このとき、$\mathrm{lcm}(A, B) = A \times B \div \mathrm{gcd}(A, B)$ が成り立つ。
この証明には素因数分解などを用いたものがあるが、割愛する。
最大公約数の求め方
手計算だと
- ユークリッドの互除法
- $A$ と $B$ の約数をそれぞれ全部書き出す
といった方法がある。どちらもプログラム上で実現はするのだが、
- ユークリッドの互除法は、$Ο(\log(\mathrm{min}(A, B)))$
- 約数の全列挙は $Ο(\sqrt{A+B})$
という計算量の違いがある。
前者はたとえ $A, B \leq 10^{18}$ だろうが非常に高速 ($60$ 回程度の計算で終了する)なのに対して、後者は $A, B \leq 10^{18}$ だと $10^9$ ステップを超える計算が必要であり、低速である。
なお競プロでは、基本的にユークリッドの互除法をどこかに保存して持っておけばよく、空で書ける必要はない。
2. ABC124 B - Great Ocean View
https://atcoder.jp/contests/abc124/tasks/abc124_b
各 $i$ について題意を満たすか調べるのに、$H_1, H_2, \ldots, H_{i - 1}$ を調べなくてはならない。
しかし、$N \leq 20$ なので、合計で最大でも $200$ 回程度の計算しか必要ないため、一つ一つシンプルに調べればよい。
問題文に示された条件は、言い換えれば「自分より先頭側の要素に、自分より真に大きい値がない」ことであり、これは単純な < 演算子を用いて判定できる。
なお、直感に反するかもしれないが、オーダー表記の計算量は $Ο(N^2)$ である。よって、これが $N \leq 2 \times 10^5$ などの場合はこの解法だと TLE すると言える。
Bonus
$N \leq 2 \times 10^5$ でも解く方法が存在する。考えてみると考察力向上の一助となるはずだ。
3. M-Solutions プロコンオープン 2020 B - Magic 2
https://atcoder.jp/contests/m-solutions2020/tasks/m_solutions2020_b
まず、赤のカードに対して操作するべきではない。なぜなら、緑のカードに要求される数字が大きくなってしまうからだ。
そして、$A<B$ である場合はいつまでたっても魔術が成功しない。よって、まずは $A<B$ となるまで緑のカードに対して操作をすればよい。
$A<B$ を満たしたあとは、青のカードに対して操作をする。この間 $A<B$ である状態は必ず保たれるので、青のカードに対して限界まで操作をして $B<C$ になれば Yes と出力すればよい。
このように、一見操作順序などにいくつもの可能性がありそうな場合に、最も良い方法を $1$ 通り見つけてそれを行うことを貪欲法と呼ぶ。
Section 2
4. ABC064 C - Colorful Leaderboard
https://atcoder.jp/contests/abc064/tasks/abc064_c
危険なコーナーケースがサンプル上に存在しないので注意されたい。全員がレーティング $3200$ 以上の場合は適当に実装すると $0$ を出力するようなプログラムを作りかねない。
それにさえ気が付けば、後は区間数 $10 = σ$ として $Ο(σN)$ 程度でユーザを振り分けて map などで処理できる。
Bonus
わずかな改善だが $Ο(N \log σ)$ でも解ける。
5. ABC180 D - Takahashi Unevolved
https://atcoder.jp/contests/abc180/tasks/abc180_d
愚直にシミュレーションを行うことが出来ない。条件をうまく切り分けていくこととなる。
もちろん、$\times A$ と $+B$ ではいずれ後者の方が必ず変動量が小さくなるタイミングが来る。逆に、それまでは必ず前者の方が変動量は小さい。
ところでそのタイミングだが、そもそも $X=1$ の場合でも $\times A$ する回数は $\log_A{Y}$ 程度となるため、非常にその回数は少ない($60$ 程度)。
よって、$\times A$ する部分だけは愚直にシミュレートできる。
ただし、条件式は丁寧に構築すること。
6. ABC178D - Redistribution
https://atcoder.jp/contests/abc178/tasks/abc178_d
非常に難しいが、このような個数が多すぎる数え上げはまず $\mathrm{DP}$ で解けないかと考えてよい。
$\mathrm{DP}[x]$ は $S = x$ の時の解である、とすると
$A[0] = 1$ という初期条件と
$A[n] = Σ_{k=0}^{n-3} A[k]$ という漸化式を得られて、これは $Ο(N^2)$ で処理できて、解くことが出来る。
Bonus 1
$Ο(N)$ で解けるように漸化式を変形できる。これは difficulty $1000$ 程度なので挑戦する価値はあり。
Bonus 2
$Ο(\log N)$ でも解ける。difficulty $1600$ を超えるような難易度ではあるが。
