情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

yukicoder contest 218 F - 増える演算

F問題の解説です。

問題

No.856 増える演算 - yukicoder

問題文(要約)

問題文

\frac{\prod_{i=1}^{N} \prod_{j=i+1}^{N} (A_i + A_j) \cdot A_i^{A_j}}{\underset{i < j}{\min}((A_i + A_j) \cdot A_i^{A_j})} \mod 1000000007$を求めよ。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^5


全部が掛け算の形になるように解いていくことを考えます。
まず、指数の部分です。
これはiを決め打つとA_i^{\sum_{j=i+1}^{N} A_j}となり、累積和があると{\rm O}(N \log A_i)で構築できます。
これにより、まずは指数部について解が求まりました。
次に、和の部分です。
これは個数に関しては畳み込み演算が可能なので、FFTを用いると高速に個数が分かります。
最後に、minの部分です。
これは必ずA_iを決め打った時A_jは最小を選んでることを利用すると、適当な比較関数を用いて求めることができます。
よって、全部が積の形になったので後は掛ければ答えが求まります。

感想

テストケースの
3
1 5 3
が可能なんじゃないかという話から、30分で作った問題でした。
サンプル3、入力が3153で出力が6000なの凄いと思いません？
個人的には色々と詰め込んでいる上にFFTとかも出てくるので難しいかなと思いましたが、上位勢にとってはやっぱり簡単なようですね。
まぁ私からは難しかった、ということで……。
実際、tester提示の★3からは上がり、★4.5に届いたようですし。

yukicoder contest 218 E - ヘビの日光浴

E問題の解説です。

問題

問題文、説明が難しいのでこっち読んでね。

さて、ヘビの移動について実際にシミュレーションしていきましょう。
各ヘビについて、正面のヘビとぶつかるか？は簡単に求められるかと思います。
同じ座標のヘビについて簡単に判定できれば良いので、座圧しておけばインデックスと対応します。
次に、左右のヘビとぶつかるかを考えます。
これは、左右のヘビそれぞれについて、自分とぶつかる長さ以上のヘビのうち最も近い位置のヘビがぶつかる位置ならぶつかります。
これはセグメント木上の二分探索を行うと{\rm O}(\log N)で判定することができます。
よってアルゴリズムとしては解くことができます。
実装に関しては、セグメント木4本を左右それぞれ二分探索する必要があるなどかなり重い実装を要求するので注意してください。

感想

実装が面倒な典型問題ですね。
セグメント木の二分探索における典型問題なので、verifyなどにお使いください。
正直writerは間違えた、これ難しい！()
とはいえ元は典型なので★3かなぁとかやっていましたが、本番で全然解かれなかったら★5に一瞬なりました。
えー……流石にそんな難易度は無いよね？
これICPCの時期に作問したからかなり重実装なのですが、正直これくらいは実装できないとICPCでは苦戦すると思うのですよ……。

yukicoder contest 218 D - 公平なりんご分配

D問題の解説です。

問題

No.854 公平なりんご分配 - yukicoder

問題文(要約)

問題文

Q個のクエリが与えられるので、各クエリについて\prod_{j=L_i}^{R_i} A_jがP_iで割り切れるか判定してください。

制約

  • 1 \leq N, Q \leq 10^5
  • 0 \leq A_i \leq 2 \times 10^3
  • 1 \leq L_i \leq R_i \leq N
  • 1 \leq P_i \leq 10^9


この手の連続部分列のクエリ系問題は、累積和で高速にするのが有効ですよね！
ただ、このままだと逆元が無いので良い感じにクエリの判定ができないし、値をそのまま計算すると大きくなりすぎてしまいます……。
そこでP_iを素因数分解すると、各素因数については単にその個数だけ素因数を含むか判定する問題になります。
これならば累積和上で個数は管理できるので、無事に解けました。

感想

まぁ典型よりですかね、これは普通に解かれる問題と思っていました。
実際に解かれている模様なので、こんなものかなと。