AtCoder Regular Contest 117-B - ARC Wrecker のエスパーしてみた！！！
皆さんARC117お疲れ様でした！！
いつも通り？２完速解きコンテストでしたね...
自分のコンテスト結果はこんな感じです！！
昨日の色変と言い、今日のコンテストと言い速解きでパフォが出てしまっているので今後が怖いです！！！
そんな中で、今日はタイトルにもある通り、B問題のエスパーの仕方を紹介したいと思います！！
目次はこちら！！
こんな記事書いたら炎上しそうです...
問題
問題はこちら！！！
N個の連なるビルに対して、大砲を撃っていき、撃った全ての階が崩壊する。
この時、何通りありますか？というもの...
見た瞬間はまじでわかりませんでした。
なのでどういう風に考えて10分ほどで解けたのか、紹介していきます。
エスパーの仕方
※以下、入力例３を例に紹介していきます！！
1. set 取れますやん
最初はsetをとって、同じ高さのビルの重複があればビルの個数減らせるじゃん！というものです。
だってそうですよね？同じ高さのビルがあっても、同じ崩壊の仕方をするだけですから、重複してるビルは消去しても問題ありません。
2. sort 出来ちゃうんですよねーー
つい昨日の事なんですが、コンテスト中に迷ってしまった場合、何をすればまとめたリストを作成しようと思い、Twitterで募集をかけました。
作るかこれ pic.twitter.com/noEzXq3Hpf
— カイリュー (@ryusuke__h) 2021年4月17日
このときに、 harurun さんが ソートしてみる とコメントを下さいました。
ソートしてみる
— harurun🌹 (@harurun_p) 2021年4月17日
そうなんですよ、、やることがなくなったら次はソートするんですよ！！！
そしたら、各ビルが何階くらい離れてるのか知りたかったので、差をとってみました！！
すると、以下のような結果になりました！！
なるほどなーこれもなんか ソート してみるか！！
としてみたら以下のようになりました。
んーーなんかわからんな？？？
手が進まなかったら、次はもちろんあれだよな？？？
3. デカイ数字はとりま素因数分解！！！
今回のB問題は出力例３がいつもと違って、modを取る前の答えが書いてありました。
なので、これを素因数分解するとなんと...!!!
あれ？？107？？？
さっきの差を取った時に出てきてるやんwwwwwwww
ここが本日の勝因となりました。
ということでここでこのソートして差を取ってきたことが無駄ではないと確信しました。
ここで一旦先ほどの差を取った配列を全てかけてみることにしました。
しかし、答えが少し小さい値になってしまいました！！
4. 何が足りない！？
ということで、ここで後何をかければ、答えが 20192492160000 になるのかをめっちゃ考えました。
ここで考えたのが、先ほどの素因数分解の結果と今回の差の配列の全ての素因数を比較して、何が足りないのかを考えることにしました（俺は一体何をしてるんだ？？）
その結果がこちらです！
さて、ここまできたぞ！！
あとは、この160の正体はなんぞや！ということですね。。
5. 160って何者？？？
そしたら、ここで160を思い浮かべるものがありますよね？？
それは、
与えられた配列Aの最小値に１を足したもの！！！
ということです！！！
さて、他にこんなことを考えた参加者はいるのでしょうか？（いないと信じたい。）
なので最後に
ans *= (min(a) + 1) ans %= mod print(ans)
とやると、見事AC出来たという訳です。
Pythonコード
n = int(input()) a = list(map(int,input().split())) mod = 10 ** 9 + 7 a = list(set(a)) a.sort() x = [] for i in range(len(a) - 1): x.append(a[i + 1] - a[i] + 1) ans = 1 for i in range(len(x)): ans *= x[i] ans %= mod ans *= (a[0] + 1) print(ans % mod)
最後に
エスパー記事いかがでしたか？
なかなか面白いものが出来たと個人的には思っています。
結論は...
こんな感じでレート上がっても嬉しくないよ！！！
以上！！！！！
最後までありがとうございました！！！
