AtCoder Regular Contest 129 A - Smaller XOR 解けなかった方いますか？　僕はエスパーしました。

エスパー解説 競技プログラミング 問題解説

皆さんこんばんは。

ARC129お疲れ様でした！！

なんとか２完出来て耐えました。。

f:id:ryusuke_920:20211121230411p:plain
ARC129のコンテスト結果

所でA問題を皆さんどのようにして解きましたか？
僕はエスパーしました。

ということで
今回はエスパー記事第３弾です！！！！

↓今までのエスパー記事はこちら↓
ryusuke920.hatenablog.jp


それではまずは問題から見ていきましょう。

A - Smaller XOR

1. 問題の概要

整数N, L, R が与えられます。
以下の条件を満たす整数 x の個数を数える問題

  • \displaystyle L \leqq x \leqq R
  • \displaystyle (x \oplus N) < N

2. 問題の制約・入力例

2-1. 問題の制約・入力例

  • \displaystyle 1 \leqq N \leqq 10^{18}
  • \displaystyle 1 \leqq N \leqq 10^{18}
  • \displaystyle 入力される値は全て整数である

2-2. 入力例

入力例1

\displaystyle 2 \quad 1 \quad 2

出力例1

\displaystyle 1

入力例2

\displaystyle 10 \quad 2 \quad 19

出力例2

\displaystyle 10

入力例3

\displaystyle 1000000000000000000 \quad 1 \quad 1000000000000000000

出力例3

\displaystyle 847078495393153025

3. エスパー方法

まずは実験です。
解けなかった方、ちゃんと実験しましたか？
実験はエスパーを行う上で本当に大切です。

今回の勝因は完全に実験です。

入力例1, 3は両極端なので今回は２を使って説明します。
すると、以下のような結果になります。

f:id:ryusuke_920:20211121230545j:plain
入力例２の実行結果

もう見えましたよね？

これ、 \displaystyle 2^{i}ずつ条件を満たすものと満たさないものがあります。

なので、 R の２進数の長さ分 for文を回して条件を満たしていれば、 \displaystyle (min(R, 2^{i + 1}) - 1) - 2^{i} + 1をカウントするだけです。

4. ACコード

n, l, r = map(int,input().split())
 
def f(x):
    ans = 0
    for i in range(len(int(bin(x)[2:]))):
        if 2 ** i ^ n < n:
            ans += min(2 ** (i + 1) - 1, r) - 2 ** i + 1
    return ans
 
print(f(r) - f(l - 1))

5. 最後に

ここまでエスパー出来てるのになぜ２ペナしてる？と思う方いるかも知れません。
それは...

1 ~ R までの個数で求めていてずっと気づきませんでした！！！！！！！！！！！！！！！！！

1 ~ R で考えてもこの入力例が全て通ってしまうのは罠ですね...

最後までありがとうございました！

AtCoder Beginner Contest 157 D - Friend Suggestions (Python)

問題解説 水-difficult 競技プログラミング

本日はこちらの水diff！！

問題はこちら〜

https://atcoder.jp/contests/abc157/tasks/abc157_d

友達関係の問題！
現代社会にまつわる問題ですね（笑）

1. 問題の概要

N人の人々の間にM組の「友達関係」とK組の「ブロック関係」があります。

各人々 i に対して、友達候補の数を出力せよという問題。

ここでいう友達候補というのは簡単にいうとAさんから友達を伝って行ってBさんまでたどれればAとBは友達候補になります。

2. 問題の制約と入力例

2-1. 問題の制約

  • 入力は全て整数
  • \displaystyle 2 \leqq N \leqq 10^{5}
  • \displaystyle 0 \leqq M \leqq 10^{5}
  • \displaystyle 0 \leqq K \leqq 10^{5}
  • \displaystyle 1 \leqq A_{i}, B_{i} \leqq N
  • \displaystyle A_{i} \neq B_{i}
  • \displaystyle 1 \leqq C_{i}, D_{i} \leqq N
  • \displaystyle C_{i} \neq D_{i}
  • \displaystyle (A_{i}, B_{i}) \neq (A_{j}, B_{j}) \quad (i \neq j)
  • \displaystyle (A_{i}, B_{i}) \neq (B_{j}, A_{j})
  • \displaystyle (C_{i}, D_{i}) \neq (C_{j}, D_{j}) \quad (i \neq j)
  • \displaystyle (C_{i}, D_{i}) \neq (D_{j}, C_{j})
  • \displaystyle (A_{i}, B_{i}) \neq (C_{j}, D_{j})
  • \displaystyle (A_{i}, B_{i}) \neq (D_{j}, C_{j})

2-2. 入力例

入力例1

\displaystyle 4 \quad 4 \quad 1
\displaystyle 2 \quad 1
\displaystyle 1 \quad 3
\displaystyle 3 \quad 2
\displaystyle 3 \quad 4
\displaystyle 4 \quad 1

出力例1

\displaystyle 0 \quad 1 \quad 0 \quad 1

入力例2

\displaystyle 5 \quad 10 \quad 0
\displaystyle 1 \quad 2
\displaystyle 1 \quad 3
\displaystyle 1 \quad 4
\displaystyle 1 \quad 5
\displaystyle 3 \quad 2
\displaystyle 2 \quad 4
\displaystyle 2 \quad 5
\displaystyle 4 \quad 3
\displaystyle 5 \quad 3
\displaystyle 4 \quad 5

出力例2

\displaystyle 0 \quad 0 \quad 0 \quad 0 \quad 0

3. 問題を見て考えたこと

友達の関係と言われたらぱっと思いつくのはやはり Union-Find ですよね。
でもどのように管理すれば良いかがよくわからない。

とりあえず「友達関係」の集合を Union-Find で管理してその後は...と言う所で少し躓いてしまいました。

それでは解説していきます。

4. 解説

この問題はお気づきの通り、 Union-Findで解くことができます。

まず、「友達関係」の集合を Union-Find で管理します。

その中で「友達候補」になることができないのは、自分自身もしくは「ブロック関係」にある人々です。

したがって、まずM個の入力で「友達関係」の集合を管理し、K個の入力で \displaystyle C_{i}, D_{i}が同じグループに属していれば「友達候補」になれない集合（今回の場合は out 配列）に加えます。

そうすると、各人々 i に対して出力する友達候補の数は

\displaystyle uf.size(i) - len(out[i]) - 1

となります。
ここで out[i] := 人 i に対して友達候補になれない人数です。
-1 をしているのは自分自身を除くためです。

このようにしてこの問題は解くことが出来ました。

5. ACコード

class UnionFind:
  def __init__(self, n):
    self.n = n
    self.p = [-1] * n

  def leader(self, a):
    while self.p[a] >= 0:
      a = self.p[a]
    return a

  def merge(self, a, b):
    x = self.leader(a)
    y = self.leader(b)
    if x == y: return x
    if self.p[x] > self.p[y]:
      x, y = y, x
    self.p[x] += self.p[y]
    self.p[y] = x
    return x

  def same(self, a, b): return self.leader(a) == self.leader(b)

  def size(self, a): return -self.p[self.leader(a)]

n, m, k = map(int,input().split())

uf = UnionFind(n)

out = [[] for _ in range(n)] # 友達もしくは同じグループの中で喧嘩の組み合わせの集合
for _ in range(m):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    uf.merge(a, b)
    out[a].append(b)
    out[b].append(a)

for _ in range(k):
    c, d = map(int,input().split())
    c -= 1
    d -= 1
    if uf.same(c, d):
        out[c].append(d)
        out[d].append(c)

ans = []
for i in range(n):
    ans.append(uf.size(i) - len(out[i]) - 1)

print(*ans)

6. 最後に

ここ２日間ですが、早朝に起きて精進をする生活をしています。
朝を有効活用するととても得した気分になるので今後も続けて行けたらやっていきたいなと考えています。

Twitterのスペースを活用しているのでよければ作業がてら来てください！

最後まで見ていただきありがとうございました！

AtCoder Beginner Contest 080 C - Shopping Street (Python)

問題解説 緑-difficult 競技プログラミング

本日は前まで解けなかった緑diffが今考えたら解けたので紹介したいと思います！

問題はこちら〜

https://atcoder.jp/contests/abc080/tasks/abc080_c

とにかく問題文が長い...
見るだけで嫌になってしまいますよね。

1. 問題の概要

月曜日〜金曜日までの５日間、それぞれ午前・午後に分けた10区間に対して、お店がそれぞれ開店、もしくは閉店している。

joisinoお姉ちゃんは各店が営業している時間帯に店を開くと、その個数に応じた利益が得られます。（説明がとにかく複雑なので詳しくは問題文を見てください...）

このとき、利益の最大値はいくらになるか。

2. 問題を見て考えたこと

冒頭にも書いたようにとにかく問題文が長い...
読解するだけで自分は15分ほどかかってしまいました...

どのように考えれば良いか考えましたが、10区間しかなく、それぞれ営業するかしないかの２択！
これは〇〇しかなさそうですよね？？？

3. 問題の制約

  • \displaystyle 1 \leqq N \leqq 100
  • \displaystyle 0 \leqq F_{i,j,k} \leqq 1
  • \displaystyle 1 \leqq i \leqq N を満たす全ての整数 i に対して、 \displaystyle F_{i,j,k} = 1 を満たす (j, k) が必ず１つ以上存在する
  • \displaystyle -10^7 \leqq P_{i,j} \leqq 10^7
  • 入力は全て整数

4. 解説

こちらは bit全探索 のアルゴリズムを用いることでACすることができます！

N 個のお店それぞれ10区間に対して営業するかしないかを考えると、計算量も余裕で間に合います。

bit全探索でjoisinoお姉ちゃんのお店を開くか・開かないかを列挙し、josinoお姉ちゃんが店を開いているかつお店 i が開いていれば個数をカウントし、その個数に対応した利益を格納する配列（今回の場合はplus）の合計値の最大化をすれば解くことができます。

コーナーケースとして、全てのお店が開いていない場合は例外と問題文に書かれているのでその時だけは除外しましょう。（そうしないと入力例２で０が出力されます。）

5. ACコード

from itertools import product

n = int(input())
f = [list(map(int,input().split())) for _ in range(n)]
p = [list(map(int,input().split())) for _ in range(n)]

ans = -10 ** 18 # マイナスの場合もあるので初期値は負のINF
for i in product([0, 1], repeat=10):

    if i.count(0) == 10: continue # 店が１つも空いていない時はNG

    is_open = [0] * n # 各お店とjoisinoお姉ちゃんが両方とも営業している時間帯の数
    for j in range(n):
        for k in range(10):
            if i[k] == 1 and f[j][k] == 1: # どちらも営業している
                is_open[j] += 1

    plus = []
    for j in range(n):
        plus.append(p[j][is_open[j]])

    ans = max(ans, sum(plus))

print(ans)

6. 最後に

つい３ヶ月ほど前にロックアウトで1度出たのですが、全くわからず撤退してしまいました...
でもこうして時間を空けると思いのほか解けてしまいます。

成長を実感できて良かったです！

最後まで見ていただきありがとうございました！

キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227) C - ABC conjecture (Python)

茶-difficult 競技プログラミング 問題解説

お久しぶりです！

久々に解説記事を書きたいと思います！

問題はこちら！
https://atcoder.jp/contests/abc227/tasks/abc227_c

数学問題なので得意分野だし解説しようかと思いま〜す

1. 問題の概要

\displaystyle A \leqq B \leqq C かつ ABC \leqq N を満たす自然数 (A, B, C) の個数を求めよ。 \\ 答えは2^{63}未満であることが保証されます。

2. 制約と入力例

2-1. 制約

  • \displaystyle 1 \leqq N \leqq 10^{11}
  • \displaystyle N は整数

2-2. 入力例

入力例１

N = 4 のとき、条件を満たす組み合わせは、
(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 2, 2) の５つです。

入力例２

N = 100000000000 のとき、条件を満たす組み合わせは、 5745290566750 個です。

3. 見てすぐに考えたこと

  • 入力例２からわかるように N が最大の時の個数がとても多いので単純に回すのは絶対に無理
  • 整数問題でよくある O(N^2) 解法でもTLEしてしまう。
  • 高校数学の整数問題 \displaystyle \frac{1}{x} + \frac{1}{y} + \frac{1}{z} = 1 を満たす自然数 (x, y, z) の個数を求めよ。 に似ている？

ということで、３つ目の直感で思ったことから不等式で条件を絞っていこうと考えました。

4. 解説

まずは与えられた不等式を用いて範囲を絞ります！

\displaystyle A \times A \times A \leqq ABC \leqq N \\ A^3 \leqq N \\ A \leqq N^\frac{1}{3}

とわかるので、探索するAの範囲は \displaystyle N^{\frac{1}{3}}までで良いことがわかります。

次にBの範囲を絞っていきます。

\displaystyle BC \leqq \frac{N}{A} \\ B \times B \leqq BC \leqq \frac{N}{A} \\ B^2 \leqq \frac{N}{A} \\ B \leqq \sqrt{\frac{N}{A}}

したがって、探索するBの範囲は \displaystyle \sqrt{\frac{N}{A}}までで良いことがわかります。

ここまで、範囲が絞れたらあとは条件を満たす \displaystyle C \leqq \sqrt{\frac{N}{AB}}を満たす C の個数を求めれば良いです！

5. ACコード

n = int(input())

ans = 0
for a in range(1, int(n ** (1 / 3)) + 10):
    for b in range(a, int((n / a) ** 0.5) + 10):
        ans += max(0, int(n // (a * b)) - b + 1)

print(ans)

6. 最後に

久しぶりの数学問題 & 水パフォが出てとても嬉しかったです。
年内の入水を目指してこっそり精進しています。
最後まで見てくださってありがとうございました！！

AtCoder Regular Contest 035 🧪 C - アットコーダー王国の交通事情 (Python)

青-difficult 競技プログラミング 問題解説

久々投稿です！
おはこんばんにちは〜
今日は毎晩やっているバチャで面白い問題があったので紹介したいと思います！

問題はこちら！
https://atcoder.jp/contests/arc035/tasks/arc035_c

試験管🧪で難易度は青で1655diffとなってます！

解説記事の水以上は初めてなので緊張してますが、頑張っていきます！（' _ '）

ダイクストラ法やワーシャルフロイド法を知っている方であれば、
灰色の方も理解できるように頑張って作ったので見ていただけると幸いです。

1. 問題の概要

要は全ての都市間の最短経路長の総和を求めろと言う問題。

総和を S, ２頂点間の最短距離を D(i, j) とすると、

\displaystyle S = \sum_{i=1}^{N-1} \sum_{j=i+1}^{N} D(i, j) \\

となるので、 S を出力する問題である。

ただ求めるだけならば、ダイクストラを貼って O(N^2) で終わるが、
この問題は K 個のクエリが与えられ、毎度辺が追加されるという特徴がある。

これをどう処理していくかが重要である。

2. 入力例と制約

\displaystyle N \quad M \\ A_1 \quad B_1 \quad C_1 \\ A_2 \quad B_2 \quad C_2 \\ : \\ A_M \quad B_M \quad C_M \\ K \\ X_1 \quad Y_1 \quad Z_1 \\ X_2 \quad Y_2 \quad Z_2 \\ : \\ X_K \quad Y_K \quad Z_K \\

  • \displaystyle 1 \leqq N \leqq 400
  • \displaystyle 1 \leqq M \leqq 1000
  • \displaystyle 1 \leqq A_i, B_i \leqq N
  • \displaystyle 1 \leqq C_i \leqq 1000
  • \displaystyle 1 \leqq K \leqq 400
  • \displaystyle 1 \leqq X_i, Y_i \leqq N
  • \displaystyle 1 \leqq Z_i \leqq 1000

3. 解説

まず、計算量について考えてみよう。
今回の制約の特徴は何と言っても N が小さいことにある。

K 回のクエリごとに辺を追加し、最短距離を更新した後に、毎回全通りの D(i, j) を求めても O(KN^2) となるので間に合うことがわかる！

つまり、ダイクストラでクエリ処理前の全ての２頂点間の最短距離を O(N^2logN) 求めた後に、辺を追加していくことを考える。

では、頂点 (x, y) 間に z で行ける距離を追加した場合どのような更新が行われるかを考えよう。

以下、 dist[a][b] を a から b までの最短距離と定義する。

１つ目のパターンは、頂点 (a, b) の距離を a → x → y → b で辿っていく場合が考えられる。

f:id:ryusuke_920:20210714011914p:plain
a → x → y → b の順で辺を辿っていく場合

２つ目のパターンは、頂点 (a, b) の距離を a → y → x → b で辿っていく場合である。

f:id:ryusuke_920:20210714012002p:plain
a → y → x → b の順で辺を辿っていく場合

したがって、このように３パターン（更新せずに a → b に行くパターンを含めた）のうち、最短となるものを求めて更新していけば良いことがわかる。

a → b の組み合わせは 、

\displaystyle S = \sum_{a=1}^{N-1} \sum_{b=a+1}^{N} dist[a][b] \\
通りあるので、これは O(N^2) で処理することが可能となる。

したがって、

  1. 前処理としてダイクストラ法（ワーシャルフロイド法でも可能）で全ての２頂点間の最短距離を求める。
  2. K 回のクエリごとに最短距離を更新 O(N^2) し、クエリごとに毎回全ての２頂点間の全通り O(N^2) を試して総和を求めることができる。

したがって、計算量は O(N^2logN + KN^2) となる。

4. ACコード

ACしたコードはこちらになります。

import sys
input = sys.stdin.readline
from heapq import heappush, heappop

# ダイクストラ法で最短経路を求める
def dijkstra(s, graph):
    dist = [INF] * n
    check = [False] * n
    dist[s] = 0
    q = [(0, s)]
    while q:
        v = heappop(q)[1]
        if check[v]: continue
        check[v] = True
        for i, j in graph[v]:
            if check[i] != False: continue
            if dist[i] <= dist[v] + j: continue
            dist[i] = dist[v] + j
            heappush(q, (dist[i], i))
    return dist

INF = 10 ** 9
n, m = map(int,input().split())

# ノードの追加
g = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int,input().split())
    g[a - 1].append((b - 1, c))
    g[b - 1].append((a - 1, c))

# 全ての２頂点間の最短経路を求める
dist = []
for i in range(n):
    dist.append(dijkstra(i, g))

k = int(input())
for _ in range(k):
    x, y, z = map(int,input().split())

    # 最短距離の更新を行う
    for i in range(n):
        for j in range(n):
            if i == j: continue
            dist[i][j] = min(dist[i][j], dist[i][x - 1] + dist[y - 1][j] + z, dist[i][y - 1] + dist[j][x - 1] + z)

    # 総和 S を求める
    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            ans += dist[i][j]

    print(ans)

5. 最後に

久々に解説記事を書きました。

途中ではPower Pointを使用した画像を入れてみましたが、どうでしょうか？

また気分が向いたら記事を書きたいと思います！！

AtCoder Beginner Contest 200 - D Happy Birthday! 2 を嘘解法した (嘘・エスパーシリーズ Ver.2)

競技プログラミング 問題解説 エスパー解説 水-difficult

皆さんこんばんは！
炎上記事Part 2 です！！
本日行われたABCで今度は嘘解法してしまいました！！！

f:id:ryusuke_920:20210508225419p:plain
ABC200の結果

というか、今回はエスパーのつもりはなくて、とりまなんもすることないし、適当にやって嘘解法でも提出しちゃえ！！！ってやったらACして発狂しました。。。

ちなみに前回のエスパー記事はこちら

ryusuke920.hatenablog.jp


問題はこちら

D - Happy Birthday! 2

要約すると、配列 A からいくつか取り出し、余りが同じになる異なる取り出し方はありますか？という問題です。


今回は前回のように、エスパーの中での自分なりの考えすらもなく、ただ脳死で提出したので何を提出したのかをお話しします。

コード

早速ですが、まずはACしたコードを載せようと思います！こちら！！

n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    a[i] %= 200

num = [[] for _ in range(200)]

for i in range(n):
    cnt = a[i]
    cnt %= 200
    num[cnt].append([i + 1])

for i in range(n - 1):
    for j in range(i + 1, n):
        cnt = a[i] + a[j]
        cnt %= 200
        num[cnt].append([i + 1, j + 1])

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            cnt = a[i] + a[j] + a[k]
            cnt %= 200
            num[cnt].append([i + 1, j + 1, k + 1])

for i in range(len(num)):
    if len(num[i]) >= 2:
        print("Yes")
        print(len(num[i][0]), *num[i][0])
        print(len(num[i][1]), *num[i][1])
        exit()
print("No")

最初に言います。
なんでこれでACできるのかわかっていません！！
鳩の巣原理でなんかやるんだろうなーとは速攻で思ったんですけど（これも合っているのか分からんが。）そこからがわからなかった。

あとNが大きい時はどうせ鳩の巣原理で絶対にYesだろうくらいには思いました。

これ、何をしているのかと言うと、時間内に間に合う限りで全探索してみようと言う発想です！
N <= 200 の制約になっていたので、O(N^3) までなら間に合うかと言うことで、

Part 1 すべての始まりO(N)

num = [[] for _ in range(200)]

for i in range(n):
    cnt = a[i]
    cnt %= 200
    num[cnt].append([i + 1])

ここでは、まず O(N) で余りが 200 パターンのうち、何になるかを計算しています。

Part 2 ちょっとレベルアップ O(N^2)

for i in range(n - 1):
    for j in range(i + 1, n):
        cnt = a[i] + a[j]
        cnt %= 200
        num[cnt].append([i + 1, j + 1])

ここでは、２つの組み合わせで作れる余りを全列挙しています。時間も余裕で間に合いますよね。

Part 3 最後のステップ O(N^3)！！！！！

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            cnt = a[i] + a[j] + a[k]
            cnt %= 200
            num[cnt].append([i + 1, j + 1, k + 1])

ここでは、３つの組み合わせで作れる余りを全列挙しています。

答えはYes or No ?

最後にこのnum(上記の余りのパターンを格納した配列)の中身を全探索（200通り）し、あるあまりが２パターン以上(lengthが2以上)あれば、違う組み合わせで余りが同じになるパターンがあると言うことなので、それを出力します。

逆に見つからなかった場合は、一致する余りがないと言うことになる（はず）なので No を出力してACしました。

最後に

なんでこれでACしたのか本当によくわかりません。
緑になってから、エスパーして大幅にレートが上がるか、失敗して下がっているかの２択です。辛いです。

追記（解説見ました 2021/05/08/23:00現在）

Bit全探索？？？
は？？なにそれおいしいの？？？？

AtCoder Regular Contest 117-B - ARC Wrecker のエスパーしてみた！！！

茶-difficult 競技プログラミング 問題解説 エスパー解説

皆さんARC117お疲れ様でした！！
いつも通り？２完速解きコンテストでしたね...

自分のコンテスト結果はこんな感じです！！

f:id:ryusuke_920:20210418230129p:plain
ARC117-B のコンテスト結果

昨日の色変と言い、今日のコンテストと言い速解きでパフォが出てしまっているので今後が怖いです！！！

そんな中で、今日はタイトルにもある通り、B問題のエスパーの仕方を紹介したいと思います！！

目次はこちら！！

こんな記事書いたら炎上しそうです...

問題

問題はこちら！！！

B - ARC Wrecker

N個の連なるビルに対して、大砲を撃っていき、撃った全ての階が崩壊する。
この時、何通りありますか？というもの...

見た瞬間はまじでわかりませんでした。
なのでどういう風に考えて10分ほどで解けたのか、紹介していきます。

エスパーの仕方

※以下、入力例３を例に紹介していきます！！

1. set 取れますやん

最初はsetをとって、同じ高さのビルの重複があればビルの個数減らせるじゃん！というものです。
だってそうですよね？同じ高さのビルがあっても、同じ崩壊の仕方をするだけですから、重複してるビルは消去しても問題ありません。

2. sort 出来ちゃうんですよねーー

つい昨日の事なんですが、コンテスト中に迷ってしまった場合、何をすればまとめたリストを作成しようと思い、Twitterで募集をかけました。

このときに、 harurun さんが ソートしてみる とコメントを下さいました。

そうなんですよ、、やることがなくなったら次はソートするんですよ！！！

そしたら、各ビルが何階くらい離れてるのか知りたかったので、差をとってみました！！
すると、以下のような結果になりました！！

f:id:ryusuke_920:20210418225334p:plain
配列Aの差を取ってみた


なるほどなーこれもなんか ソート してみるか！！
としてみたら以下のようになりました。

f:id:ryusuke_920:20210418225452p:plain
配列Aの差をソートしてみた

んーーなんかわからんな？？？
手が進まなかったら、次はもちろんあれだよな？？？

3. デカイ数字はとりま素因数分解！！！

今回のB問題は出力例３がいつもと違って、modを取る前の答えが書いてありました。
なので、これを素因数分解するとなんと...!!!

f:id:ryusuke_920:20210418223644p:plain
20192492160000の素因数分解結果

あれ？？107？？？
さっきの差を取った時に出てきてるやんwwwwwwww

ここが本日の勝因となりました。
ということでここでこのソートして差を取ってきたことが無駄ではないと確信しました。

ここで一旦先ほどの差を取った配列を全てかけてみることにしました。
しかし、答えが少し小さい値になってしまいました！！

4. 何が足りない！？

ということで、ここで後何をかければ、答えが 20192492160000 になるのかをめっちゃ考えました。

ここで考えたのが、先ほどの素因数分解の結果と今回の差の配列の全ての素因数を比較して、何が足りないのかを考えることにしました（俺は一体何をしてるんだ？？）

その結果がこちらです！

f:id:ryusuke_920:20210418224630j:plain
素因数分解の比較

さて、ここまできたぞ！！
あとは、この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)

最後に

エスパー記事いかがでしたか？
なかなか面白いものが出来たと個人的には思っています。

結論は...

こんな感じでレート上がっても嬉しくないよ！！！


以上！！！！！
最後までありがとうございました！！！