Educational Codeforces Round 182 (Rated for Div. 2)

　Cまで三完。遅刻でE1。Dで考え込んでしまった。

コンテストへのリンク

コンテスト後のツイート

Educational Codeforces Round 182 (Rated for Div. 2) ABC三完。遅刻してE1はAC。
A 全探索
B 大きい順に入れる。端のP[i]!=iのを探す。
C DP
E1 左右からDP。DP[i][j]で何個まで見て、塔の何番目までが見えたときの場合の数。DP[i][-1]はそこまでで全て見えたということなので左右から組み合わせる。

— titia (@titia_til) September 15, 2025

D. Price Tags

　自力で解けず、色々解説を見てAC。難しくない？

　コンテスト中は、xを絞れるのではないか？　ということを中心に考えていたが、これはダメな方針だった。

 xの全探索を考えるのが正解。

　しかし、その後も容易ではない。各C[i]を割っていくのではダメ。

　xのとき、割引後の値がdになるものは何個あるか？　と考えて、Cの頻度表を累積和の形でもっておくと調和級数の計算量になる。

　xを全探索すれば調和級数になる、と聞いてからも解法が分かるまでかなり時間がかかってしまったので全然ダメでした。