AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY）F,G問題メモ

AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY）

F - Shortest One Formula

問題文

正整数 $N$ が与えられます。
1, +, *, (, ) のみからなる数式のうち、値が $N$ となるものの中で、文字列としての長さが最小のものを一つ求めてください。

制約

$1\leq N\leq 2000$
入力は全て整数

解法

$N$ の数式表現は、「直接“1”だけで作れる」もので無い限りは、何らかの値 $k$ を使って、以下のいずれかの形になる。

[$k$ の数式表現]+[$N-k$ の数式表現]
[$k$ の数式表現]*[$N/k$ の数式表現]

よって、$1,2,...,N$ について順に「最も短い数式表現」をDPで求めていける。

ただしかけ算を使う場合は、左項や右項に「括弧でくくられていない足し算」があったら括弧でくくらないといけない。
でも、最終的な答えは別に括弧でくくる必要は無い。
そのままかけ算できる形なのかどうか、分けて情報を持たせる必要がある。

$\mathrm{DP}_1[i]:=$ 値が $i$ となる数式で「直接かけ算できる」もののうち、長さが最小のものの長さ。
$\mathrm{DP}_2[i]:=$ 値が $i$ となる数式で長さが最小のものの長さ。直接かけ算できるとは限らない。

(例) $1+11*11$ のように括弧でくくられていない足し算がある形は $\mathrm{DP}_1$ の対象には含まれない。$(1+11)*11$ や $(1+11*11)$ なら含まれる。

また、復元のために以下も記録する。

$\mathrm{TB}_1[i]:=\mathrm{DP}_1[i]$ を達成する方法の一例
$\mathrm{TB}_2[i]:=\mathrm{DP}_2[i]$ を達成する方法の一例
持たせる情報例
- $(0,)$: '111..' という形なので直接作れる。
- $(1,x,y)$: 値が $x$ になる式と $y$ になる式を足し算で結合し括弧で囲んだ。
- $(2,x,y)$: 値が $x$ になる式と $y$ になる式を足し算で結合した。括弧では囲んでない。
- $(3,x,y)$: 値が $x$ になる式と $y$ になる式をかけ算で結合した。

$O(N^2)$ が間に合うので、各 $i$ につき「2つの足し算に分解する方法」「2つのかけ算に分解する方法」を全て試せばよい。

途中経過を文字列として持つと時間が危ないかな? と思い復元情報のみ持たせるようにしたが、値が $n$ になる最短文字列長は $O(\log{n})$ であると示せるので、直接持たせても $O(N^2 \log{N})$ で大丈夫みたい。

kyopro_friends氏による解説:数式の長さがlogオーダーになることの略証

Python3

def get_lower_divisors(n):
    lower_divisors = []
    i = 1
    while i * i <= n:
        d, m = divmod(n, i)
        if m == 0:
            lower_divisors.append(i)
        i += 1
    return lower_divisors


def solve(n):
    INF = 1 << 60
    dp1 = [INF] * (n + 1)  # この後にかけ算を加えられる（括弧は不要か、既に付けてある）
    dp2 = [INF] * (n + 1)  # この後にかけ算を加えられるとは限らない（括弧が追加で必要になる可能性がある）
    trace_back1 = [(-1, -1, -1)] * (n + 1)
    trace_back2 = [(-1, -1, -1)] * (n + 1)
    # (0,0,0): そのままの値を出力する
    # (1,x,y):x2とy2を+で結合して()で覆う
    # (2,x,y):x2とy2を+で結合するだけ
    # (3,x,y):x1とy1を*で結合する
    try:
        for d in range(1, 5):
            repunit_str = '1' * d
            repunit_int = int(repunit_str)
            dp1[repunit_int] = d
            dp2[repunit_int] = d
            trace_back1[repunit_int] = (0, 0, 0)
            trace_back2[repunit_int] = (0, 0, 0)
    except IndexError:
        pass

    for x in range(2, n + 1):
        if dp1[x] != INF:
            continue
        for y in range(1, x // 2 + 1):
            tmp = dp2[y] + dp2[x - y] + 1
            if dp1[x] > tmp + 2:
                dp1[x] = tmp + 2
                trace_back1[x] = (1, y, x - y)
            if dp2[x] > tmp:
                dp2[x] = tmp
                trace_back2[x] = (2, y, x - y)
        divisors = get_lower_divisors(x)
        for d in divisors:
            tmp = dp1[d] + 1 + dp1[x // d]
            if dp1[x] > tmp:
                dp1[x] = tmp
                trace_back1[x] = (3, d, x // d)
            if dp2[x] > tmp:
                dp2[x] = tmp
                trace_back2[x] = (3, d, x // d)

    def restore(n, i):
        if i == 1:
            op, x, y = trace_back1[n]
        else:
            op, x, y = trace_back2[n]
        if op == 0:
            return str(n)
        if op == 1:
            return '(' + restore(x, 2) + '+' + restore(y, 2) + ')'
        if op == 2:
            return restore(x, 2) + '+' + restore(y, 2)
        else:
            return restore(x, 1) + '*' + restore(y, 1)

    ans = restore(n, 2)
    return ans


n = int(input())
ans = solve(n)
print(ans)

G - Odd Position Sum Query

問題文

空の数列 $A$ があります。
$Q$ 個のクエリが与えられるので順に処理してください。$i$ 番目のクエリは以下で説明されます。
- 整数 $y_i$ が与えられる。
- $z$ を、$i=1$ のときは $0$、それ以外のときは $i-1$ 番目のクエリに対する答えとする。
- $x_i$ を $x_i=((y_i+z)\bmod 10^9)+1$ で定義する。
- $A$ の末尾に $x_i$ を追加する。
- その後、$A$ を昇順に並べた列を $B=(B_1,B_2,\ldots,B_i)$ としたとき $B$ の奇数番目の要素の総和を求めよ。
- すなわち、$i$ 以下の最大の奇数を $m$ としたとき $B_1+B_3+B_5+\ldots+B_m$ を求めよ。

制約

$ 1\leq Q\leq 3\times 10^5$
$ 0\leq y_i\lt 10^9$
$ 1\leq x_i\leq 10^9$
入力は全て整数

解法

入力として与えられるのは $y_i$ だが、クエリの実質的な入力は $y_i$ から計算で求める $x_i$ である。ただし計算に前のクエリの答えを必要とする。
これは「クエリを先読みして解く」ことを禁じる出題方法の1つと考えられる。要は「与えられた順で解けよ」と言っている。

わざわざ禁止しているということは「クエリが先読みできたら楽に解ける」可能性が高い。
先読みできない場合と全く別の解法となる可能性もあるが、ひとまず「クエリを先読みできたとしたら？」を考えてみる。
すると、前もって座標圧縮しておけば、1点更新、区間集計のセグメント木で解けることが分かる。

各ノードは $A_i$ の値の範囲を示し、$[l,r)$ を表すノードには以下を持たせると良い。

現時点の $l$ 以上 $r$ 未満の $A_i$ の個数
現時点の $l$ 以上 $r$ 未満の $A_i$ の小さい方から奇数番目の要素の和
現時点の $l$ 以上 $r$ 未満の $A_i$ の小さい方から偶数番目の要素の和

左の区間と右の区間をマージするとき、左の区間の個数の偶奇によって、右の区間の奇数番目・偶数番目を反転させて合算するのか、そのまま合算するのかを切り替えればよい。

ただ、制約が$1\leq x_i\leq 10^9$ であるため、値を基準にセグメント木を作るには $10^9$ オーダーの空間計算量が必要となる。
先読みできれば座標圧縮で対応できるが、今回はできない。

そこで、動的セグメント木を使う。「必要なところだけ作るセグメント木」とも呼ばれている。

My Algorithm : kopricky アルゴリズムライブラリ

まぁ、こういうデータ構造を知っているかどうか、という側面が大きい。

Pythonでは実装をちゃんとしないとTLEしてしまった。
（自作ノードクラスを作成する、再帰関数を使う、などの実装が重くなりがち。あと入力によっては辞書を使う場合）
普通に通っている人もいるので、ちょっとした実装の工夫次第で速くなるとは思うのだが。。。

Python3

import os
import sys

import numpy as np


def solve(inp):
    seg = {0: (0, 0, 0)}
    seg.clear()

    seg_lower_bound = 0
    seg_upper_bound = 1 << 30
    seg_default_value = (0, 0, 0)

    def add_value(left, right):
        k1, odd1, even1 = left
        k2, odd2, even2 = right
        if k1 % 2 == 0:
            return (k1 + k2, odd1 + odd2, even1 + even2)
        else:
            return (k1 + k2, odd1 + even2, even1 + odd2)

    def seg_add(idx, x):
        """位置 idx に x を追加"""
        path = []
        l = seg_lower_bound
        r = seg_upper_bound
        while l + 1 < r:
            mid = (l + r) // 2
            path.append((l, mid, r))
            if idx < mid:
                r = mid
            else:
                l = mid

        key = (l << 30) | r

        k, odd, even = seg.get(key, seg_default_value)
        if k % 2 == 0:
            seg[key] = (k + 1, odd + x, even)
        else:
            seg[key] = (k + 1, odd, even + x)

        path.reverse()
        for l, mid, r in path:
            seg[(l << 30) | r] = add_value(seg.get((l << 30) | mid, seg_default_value),
                                           seg.get((mid << 30) | r, seg_default_value))

    q = inp[0]
    queries = inp[1:]

    prev = 0
    mod = 10 ** 9
    ans = np.zeros(q, np.int64)
    for qi in range(q):
        y = queries[qi]
        x = (prev + y) % mod + 1
        seg_add(x, x)
        _, prev, _ = seg.get(seg_upper_bound, seg_default_value)
        ans[qi] = prev

    return ans


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

目次

AtCoder Beginner Contest 403（Promotion of AtCoder Career Design DAY）F,G問題メモ

F - Shortest One Formula

問題文

制約

解法

G - Odd Position Sum Query

問題文

制約

解法