eijit's blog

第一回日本最強プログラマー学生選手権-予選- 参加

第一回日本最強プログラマー学生選手権-予選- に参加した。今回は AB 2 完答 の 1385 位でパフォーマンスは 1160 だった。

以下のコードは PyPy3 (2.4.0) で AC を確認している。

問題 A

与えられた \(M, D\) を全探索して条件を満足するものを数え上げた。 1 を数えないように注意した。

# PyPy3 (2.4.0)
M, D = map(int, input().split())

def mul_day(d):
    d1 = d % 10
    d10 = (d // 10) % 10
    if d1 < 2 or d10 < 2:
        return -1
    return d1 * d10

ans = 0

for i in range(2, M + 1):
    for j in range(2, D + 1):
        if i == mul_day(j):
            ans += 1

print(ans)

問題 B

\(A\) 内で自分より右側の要素と転倒していると \(K, K - 1, \ldots, 1\) 回転倒するので、合計で \(K \times (K + 1) / 2\) 回転倒する。対して \(A\) 内で自分より左側の要素と転倒していると \(K - 1, K - 2, \ldots, 1\) 回転倒するので、合計で \((K - 1) \times K / 2\) 回転倒する。

具体例として \(N = 4, K = 3, A = (1, 4, 3, 2)\) の場合を考える。

\(4\) について、自分より右側の要素と転倒しているのは \(3, 2\) なので

$$ \begin{bmatrix} a_1 = 1\\ a_2 = 4\\ a_3 = 3\\ a_4 = 2\\ a_5 = 1\\ a_6 = 4\\ a_7 = 3\\ a_8 = 2\\ a_9 = 1\\ a_{10} = 4\\ a_{11} = 3\\ a_{12} = 2\\ \end{bmatrix} $$

について

  • \(a_2\): \(3 \times 2\)
  • \(a_6\): \(2 \times 2\)
  • \(a_{10}\): \(1 \times 2\)

で合計 12 回転倒する。同様に \(3\) についても \(2\) と転倒しているので、合計で 6 回転倒する。

次に左側の要素と転倒しているものについて考える。 \(4\) は \(1\) と転倒しているので

  • \(a_2\): \(2 \times 1\)
  • \(a_6\): \(1 \times 1\)

で合計 3 回転倒する。同様に \(3, 2\) についても \(1\) とそれぞれ \(3\) 回転倒する。

ここまでを合計すると \(12 + 6 + 3 + 3 + 3 = 27\) となる。右側で転倒する要素同士と、左側で転倒する要素同士は、繰り返す回数について平等なので、計算をまとめて

$$(2 + 1) \times 3 \times (3 + 1) / 2 + (1 + 1 + 1) \times (3 - 1) \times 3 / 2 = 27$$

と考えると良い。

下記のコードでは、右側で転倒する要素の個数を intra とし、左側で転倒する要素の個数を inter とした。

# PyPy3 (2.4.0)
N, K = map(int, input().split())
A = list(map(int, input().split()))

mod = 10**9 + 7
intra, inter = 0, 0
for i in range(N):
    ai = A[i]
    for j in range(i, N):
        aj = A[j]
        if ai > aj:
            intra += 1
    for j in range(i + 1):
        aj = A[j]
        if ai > aj:
            inter += 1

ans = (intra * K * (K + 1) // 2) % mod
ans += (inter * (K - 1) * K // 2) % mod
print(ans % mod)

コンテスト後に転倒数といえば BIT (Binary Indexed Tree) というコメントを見かけたので勉強した。

転倒数や BIT については

がとても参考になった。特に最後の資料は BIT の図解があって理解が進んで応用しやすいと感じた。

# PyPy3 (2.4.0)
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        ret = 0
        while i > 0:
            ret += self.tree[i]
            i -= i & -i
        return ret

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, K = map(int, input().split())

bit = Bit(2000)

intra, inter = 0, 0
for i, a in enumerate(map(int, input().split())):
    bit.add(a, 1)
    intra += i + 1 - bit.sum(a)
    inter += bit.sum(a - 1)

mod = 10**9 + 7
ans = (intra * K * (K + 1) // 2) % mod
ans += (inter * (K - 1) * K // 2) % mod
print(ans % mod)

intra は自分より右側で転倒する要素、つまり A 内でのみ転倒する要素なので、通常の転倒数の求め方でよい。一方で inter に関しては、ある要素を追加したときに自分より左側にある (値が小さい) 要素を数え上げれば良いと理解した。

計算量のオーダーが \(O\left(N^2\right)\) から \(O\left(N \log\left(N\right)\right)\) に落ちており、実際に実行時間も短くなっていた。今回の要素数だと全探索でも TLE にならなかったが、別の問題では役に立つ場面も出てくると期待したい。

問題 C

  • 反転回数の偶奇に制限があること
  • 両端が W だと反転する機会が一度のため W にできないこと
  • 並べ替えの順番は問わないので、一つの解につき \(N!\) 通りの別解があること

などは解って、具体例を色々と触っていたがそれ以上は何も思い浮かばずに終了した。

Published

Category

Programming

Tags

Contact