AtCoder Beginner Contest 448 E,F問題メモ

AtCoder Beginner Contest 448

E - Simple Division

問題文

整数 $N,M$ が与えられるので、 $\lfloor N/M \rfloor$ を $\color{red}{10007}$ で割った余りを求めてください。
但し、この問題では $N$ は直接与えられず、ランレングス圧縮された形で与えられます。
- 具体的には、 $N$ は $K$ 個の「$0～9$ の数字 $c_i$ とその連続長 $l_i$ の組」からなる列で表現されます。

制約

$1 \le M \le 10^4$
$1 \le K \le 10^5$
$c_i$ は $0,1,2,3,4,5,6,7,8,9$ いずれかの数字
$1 \le l_i \le 10^9$
$c_1 \neq 0$
$M,K,l_i$ は整数

解法

$N$ は $\sum_i l_i$ 桁の数になるので、愚直に復元して筆算のように1桁ずつ商を求めるのは無理。

たとえば $M=21$ の時、$c=5$ が繰り返される数に対して割り算の筆算をしているところを考えると、商は一定のフレーズが繰り返される。

   __0_2_6_4_5_5_0_2_6_4_5_5_0_...
21 ) 5 5 5 5 5 5 5 5 5 5 5 5 5
     4 2
     1 3 5
     1 2 6
         9 5
         8 4
         1 1 5
         1 0 5
           1 0 5
           1 0 5
               0 5 ...

ただ、最初のラン（$c_1$）の場合についてはこれでいいが、 2番目以降のランについては、前のランから繰り下がってくる剰余がある場合がある。

   __0_1_5_8|7_4_0_7_4_  ←② ここの商もさっきとは異なったものとなる
21 ) 3 3 3 3|5 5 5 5 5
     2 1    |
     1 2 3  |
     1 0 5  |
       1 8 3|
       1 6 8|
         1 5|5      ←① 前のランから"15"が降りてきているので
         1 4 7
             8 5
             8 4
               1 5
                 0
               1 5 5
               1 4 7
                   8 5 ...

「上の桁から降りてくる値」は、それ自体を頂点番号として、グラフの頂点移動のように考えることもできる。現在の $c_i$ によって移動ルールが異なる。また、その移動時に商に立つ値も決まっている。

   __0_1_5_8|7_4_0_7_4_
21 ) 3 3 3 3|5 5 5 5 5
     0      |           | c=3の移動ルール | c=5の移動ルール
    [3]3    |           |                 |
     2 1    |      頂点 (0)→3→12→18→15→8→1→15→8→...
    [1 2]3  |        商     0  1   5   8   7  4  0   7
     1 0 5  |
      [1 8]3|
       1 6 8|        現在の頂点を v とすると、
        [1 5]5         (v * 10 + c) // m の商が立ち、
         1 4 7         (v * 10 + c) %  m の頂点に移動する。
            [8]5
             8 4
              [1]5
                 0
              [1 5]5
               1 4 7
                  [8]5 ...

$c_i$ が変わらない限り、移動ルール、および商に立つ値は変わらない。
よって、ダブリングによって $2^0,2^1,2^2,...$ 回移動時の行き先頂点、およびその時に商に立つ値 $\mod{10007}$ を記録しておけばよい。

$dbl[c][a][r]:=$「$c_i=c$ の時、$r$ から $2^a$ 回移動を繰り返した時の (移動先、商に立つ値 $\mod{10007}$)」

$c=0～9$、$a=0～29$、$r=0～M-1$ の範囲を計算しておけば十分なので、状態数は $3 \times 10^6$、計算量もそれに比例する。

dbl があれば、ラン $(c_i,l_i)$ に対して、

ラン開始時に、前のランから
- 「商を10007で割った結果において」上から降りてきている余りを $x$ とする。
- 「$N$ を $M$ で割った結果において」上から降りてきている余りを $r$ とする。
- 初期値は、$x=r=0$ である。
$l_i$ において $2^a$ の bit が立っている場合、
- $x←x \times 10^{2^a} + dbl[c_i][a][r][1] \mod{10007}$ とする
- $r←dbl[c_i][a][r][0]$ とする

これを繰り返せば、1つのランにつき $O(\log{l_i})$ で次のランへの $r,x$ が求まる。最終的な $x$ が答えとなる。

$M$ と $10007$、2種類の「割る数」が出てきて混乱しやすいので注意。

Python3

def solve(k, m, rlc):
    MOD = 10007

    pow10 = [pow(10, 1 << a, MOD) for a in range(30)]

    loops = []  # loops[c][a][r] = r→(r*10 + c) mod m という移動を 2^a 回繰り返した時の (移動先, 商の mod 100007)
    # c=0～9, r=0～m-1, a=0～30  状態数 3*10^6

    for c in range(10):
        result = []
        a0 = []
        for x in range(m):
            d, r = divmod(x * 10 + c, m)
            a0.append((r, d))
        result.append(a0)

        for a in range(1, 30):
            prev = result[-1]
            curr = []
            for x in range(m):
                r1, d1 = prev[x]
                r2, d2 = prev[r1]
                d = (d1 * pow10[a - 1] + d2) % MOD
                curr.append((r2, d))
            result.append(curr)

        loops.append(result)

    ans = 0
    r = 0
    for c, l in rlc:
        for a in range(30):
            if l & (1 << a):
                r, d = loops[c][a][r]
                ans *= pow10[a]
                ans += d
                ans %= MOD

    return ans


k, m = list(map(int, input().split()))
rlc = [list(map(int, input().split())) for _ in range(k)]
ans = solve(k, m, rlc)
print(ans)

F - Authentic Traveling Salesman Problem

問題文

$2$ 次元平面上に $N$ カ所の地点があります。地点 $i$ は座標 $(X_i, Y_i)$ にあります。
あなたは地点 $1$ を出発して全ての地点をちょうど $1$ 回ずつ巡回して再び地点 $1$ に戻ることにしました。
- ここで、地点 $i$ から地点 $j$ へ移動するには $\vert X_i - X_j \vert + \vert Y_i - Y_j \vert$ 秒かかります。
地点 $1$ を出発してから $10^{10}$ 秒以内に全ての地点を巡回して再び地点 $1$ に戻ることができるような地点の訪問順を出力してください。なお、制約下においてこの条件を満たす経路が少なくとも $1$ つ存在することが保証されます。

制約

$1 \leq N \leq 6 \times 10^4$
$0 \leq X_i \leq 2 \times 10^7$
$0 \leq Y_i \leq 2 \times 10^7$
$i \neq j$ ならば $(X_i, Y_i) \neq (X_j, Y_j)$
入力される値は全て整数

解法

マンハッタン距離での巡回セールスマン問題を、そこそこいい近似値で求めろ、という問題。

焼きなましなどは、（上手い人は上手くやるのだろうが）$N$ がそこそこ大きい割りに制限時間が2秒なので、十分な探索回数を稼げそうにない。
やるにしても、初期解をある程度ちゃんと作る必要がある。

$X$ でソートするなどの単純な方法では、何度も $Y$ 方向の往復が発生し、効率が悪い。

どんな座標の散らばり方に対しても、安定して空間的に近い順に探索する方法として、以下がある。

ヒルベルト曲線
Z階数曲線（モートン符号）

どちらも $O(\log{X}+\log{Y})$ 程度の軽いアルゴリズムによって、$(X,Y)$→その曲線上のindex に変換できる。
マンハッタン距離が近い順に探索すると効率がよい Mo's Algorithm などでも、クエリ処理順を決めるのに使われることがある。

この曲線が通る順で訪問するとよい。

だが距離合計 $10^{10}$ 以下という制約はなかなか厳しいようで、ヒルベルト曲線を使った方法でも数ケースでWAとなってしまう。

ヒルベルト曲線は構築の仕組み上、$2$ の冪乗毎に切れ目があるので、この付近で、本当は近いのに続けて訪問されない地点ができるようにテストケースを意図的に作られている可能性がある。

よって「移動距離が $10^{10}$ を超えた場合は、$X,Y$ 座標を1だけとかちょっとずらしてやって再計算する」などのようにすると、切れ目の位置が変わり、切れ目付近の訪問順が大きく変わる。

「そのいずれでも上手くいかないように高度に意図的に作られている」可能性もあるが、まぁ、ずらす値をランダムに何回か試すとかすると、さすがに大丈夫だろうと信じると通る。

Python3

from random import sample

def solve(n, coords):
    if n == 1:
        return [1]
    if n == 2:
        return [1, 2]

    def hilbert_index(x: int, y: int, max_bit: int = 25) -> int:
        """
        (x, y) をヒルベルト曲線順のインデックスに変換する。

        returns: ヒルベルト順序の整数
        """
        index = 0
        full_bit = (1 << max_bit) - 1

        for s in range(max_bit - 1, -1, -1):
            rx = (x >> s) & 1
            ry = (y >> s) & 1
            index <<= 2
            index |= (rx * 3) ^ ry

            # 回転処理
            if ry == 0:
                if rx == 1:
                    x = full_bit - x
                    y = full_bit - y
                x, y = y, x

        return index

    def dist(a, b):
        ax, ay = coords[a]
        bx, by = coords[b]
        return abs(ax - bx) + abs(ay - by)

    def try_dxy():
        for dx in sample(range(100), k=10):
            for dy in sample(range(100), k=10):
                order = sorted(range(n), key=lambda i: hilbert_index(coords[i][0] + dx, coords[i][1] + dy))
                score = sum(dist(order[k], order[(k + 1) % n]) for k in range(n))
                if score <= 10 ** 10:
                    return order
        return None

    tour = try_dxy()
    assert tour is not None

    tour = [p + 1 for p in tour]
    i1 = tour.index(1)
    ans = tour[i1:] + tour[:i1]
    return ans


n = int(input())
coords = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, coords)
print(' '.join(map(str, ans)))

目次

AtCoder Beginner Contest 448 E,F問題メモ

E - Simple Division

問題文

制約

解法

F - Authentic Traveling Salesman Problem

問題文

制約

解法