yukicoder contest 218 F - 増える演算
F問題の解説です。
問題
No.856 増える演算 - yukicoder
問題文(要約)
問題文
を求めよ。制約
全部が掛け算の形になるように解いていくことを考えます。
まず、指数の部分です。
これはを決め打つととなり、累積和があるとで構築できます。
これにより、まずは指数部について解が求まりました。
次に、和の部分です。
これは個数に関しては畳み込み演算が可能なので、FFTを用いると高速に個数が分かります。
最後に、minの部分です。
これは必ずを決め打った時は最小を選んでることを利用すると、適当な比較関数を用いて求めることができます。
よって、全部が積の形になったので後は掛ければ答えが求まります。
感想
テストケースの
3
1 5 3
が可能なんじゃないかという話から、30分で作った問題でした。
サンプル3、入力が3153で出力が6000なの凄いと思いません?
個人的には色々と詰め込んでいる上にFFTとかも出てくるので難しいかなと思いましたが、上位勢にとってはやっぱり簡単なようですね。
まぁ私からは難しかった、ということで……。
実際、tester提示の★3からは上がり、★4.5に届いたようですし。
yukicoder contest 218 E - ヘビの日光浴
E問題の解説です。
問題
問題文、説明が難しいのでこっち読んでね。
さて、ヘビの移動について実際にシミュレーションしていきましょう。
各ヘビについて、正面のヘビとぶつかるか?は簡単に求められるかと思います。
同じ座標のヘビについて簡単に判定できれば良いので、座圧しておけばインデックスと対応します。
次に、左右のヘビとぶつかるかを考えます。
これは、左右のヘビそれぞれについて、自分とぶつかる長さ以上のヘビのうち最も近い位置のヘビがぶつかる位置ならぶつかります。
これはセグメント木上の二分探索を行うとで判定することができます。
よってアルゴリズムとしては解くことができます。
実装に関しては、セグメント木4本を左右それぞれ二分探索する必要があるなどかなり重い実装を要求するので注意してください。
yukicoder contest 218 D - 公平なりんご分配
D問題の解説です。
問題
No.854 公平なりんご分配 - yukicoder
問題文(要約)
問題文
個のクエリが与えられるので、各クエリについてがで割り切れるか判定してください。制約
この手の連続部分列のクエリ系問題は、累積和で高速にするのが有効ですよね!
ただ、このままだと逆元が無いので良い感じにクエリの判定ができないし、値をそのまま計算すると大きくなりすぎてしまいます……。
そこでを素因数分解すると、各素因数については単にその個数だけ素因数を含むか判定する問題になります。
これならば累積和上で個数は管理できるので、無事に解けました。
感想
まぁ典型よりですかね、これは普通に解かれる問題と思っていました。
実際に解かれている模様なので、こんなものかなと。