Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Regular Contest 165

1完8:28

各問題

A - Sum equals LCM

最小公倍数がNの方の条件は、Nを素因数分解して素因数の種類が複数であれば満たすことが可能です。60 = 2^2 * 3 * 5 であれば {4, 3, 5} という要領で各素因数ごとに A をとれば最小公倍数がNになります。素因数がひと種類(素数のべき乗の形)であれば、二つ以上のそれで最小公倍数でNを作ることは無理です。

和がNになる条件は、上記の A に N になるまで 1 を追加していけばよいです。

よって、Nを素因数分解して素因数の種類が複数あれば Yes、なければ No となります。

B - Sliding Window Sort 2

操作後の順列は辞書順でP以下になります。連続するK個の要素が昇順に並んでいる場合、その部分を操作しても順番は変わらないので答えはPです。

そこまでわかりましたが、それ以上はわからず...。

#まとめ

A がすぐ解けたのでなんとか水パフォはキープ。配点高めのARCだったのでまあしゃあないか、といったところ。