AtCoder Beginner Contest 165 C～F問題メモ

AtCoder Beginner Contest 165

C - Many Requirements

問題

長さ $N$ で $1～M$ の整数からなる、広義単調増加の数列 $A$ を作ることを考える
以下のような条件が $Q$ 個ある
- 条件は $a_i,b_i,c_i,d_i$ からなる
- $A_{b_i} - A_{a_i} = c_i$ なら、スコアに $d_i$ 加算される
上手く数列を作ったとき、スコアの最大値を求めよ
$2 \le N \le 10$
$1 \le M \le 10$
$1 \le Q \le 50$

解法

全探索は疑ったけど、何故か作れる数列の個数をざっくり $M^N$ オーダーだと思い込んで無理じゃんってなってた。

${}_{M}H_{N}$ だから、たかだか $10^5$ 個程度なんだね。

Pythonでは、重複組み合わせの具体的な中身を列挙してくれる itertools.combinations_with_replacement がある。

これで生成される結果は、与えられたSequenceで先に出てくる方から優先的に使われる辞書式順序となっている。

つまり、$[1,2,3,...,M]$ の中から重複ありで $N$ 個選んでね、とすると、結果は $(1,1,1,2,2,3,...)$ のようにソートされており、決して $(1,2,5,1,1,3,...)$ などとはならないとドキュメントに明言されている。

よって列挙された1つ1つが既に広義単調増加の条件を満たしているので、それをそのまま調べればよい。

from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
queries = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    queries.append((a, b, c, d))

ans = 0
for arr in combinations_with_replacement(range(m), n):
    score = 0
    for a, b, c, d in queries:
        if arr[b] - arr[a] == c:
            score += d
    ans = max(ans, score)

print(ans)

D - Floor Function

問題

整数 $A, B, N$ が与えられる
$0$ 以上 $N$ 以下の整数 $x$ に対する、$\dfrac{Ax}{B}-A\dfrac{x}{B}$（切り捨て）の最大値を求めよ
$1 \le A \le 10^6$
$1 \le B \le 10^{12}$
$1 \le N \le 10^{12}$

解法

ある程度の考察さえできれば、実装はあってないようなもの。

$x$ を $B$ で割った商を $d$、剰余を $m$ とすると、それぞれは以下のように表せる。

$\dfrac{Ax}{B} = Ad+\dfrac{Am}{B}$
$A\dfrac{x}{B} = Ad$

なので、$m$ を最大化すればよい。

$m=B-1$ とできるなら、それが最大となる。$N$ の制約のせいでできないなら、できるだけ大きい数なので、$x=N$ とすればよい。

a, b, n = map(int, input().split())

if b <= n:
    print(a * (b - 1) // b)
else:
    print(a * n // b)

E - Rotation Matching

問題

以下の条件を満たすように、整数のペアを $M$ 個構築せよ
- 整数は $1～N$ の範囲内で、$2M$ 個の中で同じ数字が2回出てきてはいけない
- $N-1$ 回に渡って各ペアの数字を1ずつ減らす（ただし $1$ の次は $N$）とき、その計 $NM$ 個のペア中に同じ組み合わせがあってはいけない
$1 \le M$
$2M+1 \le N \le 10^5$

例

N=5  M=2
(1 5) (2 4)  ← 解答
(5 4) (1 3)
(4 3) (5 2)  N=5回に渡って各要素を1ずつ減らしたペア群
(3 2) (4 1)  どの2つを取っても（順番を入れ替えても）同じ組み合わせはない
(2 1) (3 5)

解法

1ずつ減らすという操作をしてもペア間で変わらないものを見つけて、それが $M$ 個全てのペアで異なっていれば、同じものは2回現れないという証明になる。

ペアの「差」は変わらないことに気付く。

最初に作るペアの差が全て異なっていれば、同じものは2度現れない？とすると、以下のような構成が思いつく。（サンプルにもあるし）

           差
(1 N  ) → N-1
(2 N-1) → N-3
(3 N-2) → N-5
...
(M N-M+1)

だが、これでは上手くいかない。整数はループしているので、$K$ の差のペアがあったとき、それは同時に $N-K$ の差のペアでもあるからだ。（上記の例で、差が4の $(1,5)$ が、1ずつ減らす過程で $(4,5)$ など差が1になっていることからも分かる）

なので、$M$ 個のペアで差が $K, N-K$ の2個ずつ、計 $2M$ 個できる中、そのどの2つも被らないように構築すればよい。

$N$ が奇数の場合は、先ほどの構築方法でもうまいこと被らないで構築できる。

N=11 M=5
          差       M が最大である (N-1)/2 であっても、
(1 11) → 10, 1
(2 10) →  8, 3    ・差の左は偶数で N-1 ～  2  の範囲
(3  9) →  6, 5    ・差の右は奇数で  1  ～ N-2 の範囲
(4  8) →  4, 7
(5  7) →  2, 9    ...となり、被らないで構築できる

しかし、$N$ が偶数の時、$M$ が $\dfrac{N}{2}$ に近ければ、途中で衝突してしまう。

N=12 M=5
          差
(1 12) → 11, 1
(2 11) →  9, 3  ←衝突A
(3 10) →  7, 5  ←衝突B
(4  9) →  5, 7  ←衝突B
(5  8) →  3, 9  ←衝突A

この方法では、ペアの左側が $\dfrac{N}{4}$（切り捨て）までなら、衝突せずに構築できる。

で、そこからは、2つの差が（奇数, 奇数）だから被ったのであって、（偶数, 偶数）にチェンジしてやると上手く残りを埋めることができる。

N=12 M=5
          差
(1 12) → 11,  1
(2 11) →  9,  3
(3 10) →  7,  5  ←ここまでは大丈夫
(4  8) →  4,  8  ←ここからは、ペアの右側を1ずらす
(5  7) →  2, 10

n, m = map(int, input().split())
if n % 2 == 1:
    for i in range(1, m + 1):
        print(i, n + 1 - i)
else:
    turning_point = (m + 1) // 2
    for i in range(1, turning_point + 1):
        print(i, n + 1 - i)
    for i in range(turning_point + 1, m + 1):
        print(i, n - i)

F - LIS on Tree

問題

$N$ 頂点の木があり、$i$ 番目の辺は頂点 $u_i,v_i$ を結んでいる
頂点 $i$ には整数 $a_i$ が書かれている
各頂点 $k$ について、以下を求めよ
- 頂点 $1$ から $k$ までの経路上にある整数を順に拾って数列とする
- その数列の、最長増加部分列の長さを求めよ
$2 \le N \le 2 \times 10^5$

解法

木では無く、単に数列が与えられたときの最長増加部分列（LIS）の長さは、以下の記事参照。

最長増加部分列・最長共通部分列

木の場合でも、基本的にはやることは変わらない。

$DP[k][l]=$ 頂点 $1～k$ の経路上で、長さ $l$ の増加部分列を作るとき、その末尾の値になり得る最小値

これは、そのまま持つと $O(N^2)$ でとても持てないので、実際には $k$ は省いて1次元配列を逐次更新する形で実装する。

親からDP情報を受け継いで、自身の値で更新した後、子に引き渡せばよい。

DPSなどで頂点1から順に埋めていける。

実装上の注意点

子が複数ある場合、それぞれに「自身の値で更新した直後のDP」を渡してやらなければならない。

しかし、逐次更新する実装では、1つの子に渡してしまうとその先でどういじられるか分からない。 1つの子の探索が終わった後、DP配列は、最初に渡した状態とは変わってしまっている。

だからといって、単純にDP配列をコピーしてしまうと、結局 $O(N^2)$ の空間が必要になるのでダメ。

あくまでメモリ上のDP配列は1つに保ったまま、その1つに対する操作のみで、DPを復元したい。

ここで、最長増加部分列のDPでは、1つの値（頂点）について、更新操作は以下のいずれか1つだけである。

配列の末尾に追加する
配列の1箇所を書き換える

なので、「どちらの更新を行ったか」「書き換えた場所・値は何か」さえ覚えておけば復元できる。

import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)


def dfs(v, p, links, state, ans):
    ans[v] = len(state)
    for u in links[v]:
        if u == p:
            continue
        a = aaa[u]
        # 更新箇所の記録
        b, i = -1, -1
        if state[-1] < a:
            state.append(a)
        else:
            i = bisect_left(state, a)
            b = state[i]
            state[i] = a
        # 子の探索
        dfs(u, v, links, state, ans)
        # 復元
        if b == -1:
            state.pop()
        else:
            state[i] = b


n = int(input())
aaa = list(map(int, input().split()))
links = [set() for _ in range(n)]
for line in sys.stdin:
    u, v = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add(v)
    links[v].add(u)
ans = [0] * n
dfs(0, -1, links, [aaa[0]], ans)
print('\n'.join(map(str, ans)))

目次