目次
AtCoder Grand Contest 032 A～E 問題メモ
A - Limited Insertion
問題
- 数列 $b_1,b_2,...,b_N$ がある
- 空の数列 $a$ に以下の操作を $N$ 回繰り返して数列 $b$ と同じにできるか判定し、可能なら操作手順を示せ
- $i$ 番目の操作では、$1 \le j \le i$ なる $j$ を1つ選び、$a$ の $j$ 番目に整数 $j$ を挿入する
- $1 \le N \le 100$
解法
- $i$ 番目より左に整数 $i$ を挿入することは出来ない。
- 各要素は、自分より前に挿入されると1つずつ右に動くことはあるが、左に動くことは無い。
以上の2つより、$i$ 番目より左に整数 $i$ が存在してると、つまり $i \lt b_i$ となる $i$ が存在していると構築不可能。 それ以外の場合を考える。
最後に挿入した数字は、$a_i=i$ となっているはずである。
そのような箇所が複数ある場合は、1つ前の状態を考えると、一番右を最後に操作したことにしないと矛盾が発生する。
i 1 2 3 4 5
a 1 1 3 2 5 → 1,3,5 が i = ai となっている。このどれかが最後に挿入された
i=3を最後に操作したことにすると、1つ前の状態は
i 1 2 3 4
a 1 1 2 5
^ ここで i < ai となり構築不可能な形になる
i=5を最後に操作したことにすると、構築可能な状態を保てる
i 1 2 3 4
a 1 1 3 2
$i=b_i$ となっている一番最後の $i$ を特定し、$i$ を $b$ から消す。 これを $N$ 回繰り返し、最後にひっくり返せばそれが操作手順となる。
$N \le 100$ なので、上記を毎回ループして間に合う。
n = int(input())
bbb = list(map(int, input().split()))
for i, b in enumerate(bbb, start=1):
if i < b:
print(-1)
exit()
ans = []
for _ in range(n):
for i, b in reversed(list(enumerate(bbb, start=1))):
if i == b:
ans.append(i)
bbb.pop(i - 1)
break
ans.reverse()
print('\n'.join(map(str, ans)))
B - Balanced Neighbors
問題
- 単純で連結な無向グラフを考える
- 単純: 自己ループや多重辺を持たない
- 自己ループ: 自分から出て自分へ入る辺
- 多重辺: 同じ頂点同士を結ぶ複数の辺
- 連結: 分割されていない。どの2頂点間も、辺を通じて行き来できる
- 以下の条件を満たすグラフを1つ構築せよ
- $N$ 頂点で、頂点に $1 ... N$ まで番号が付いている
- 「自身に隣接する全ての頂点の番号の和」は、全ての頂点で等しい
- $2 \le N \le 100$
解法
自身の頂点の和を調整するために、ある辺を無くすと、その相手の和にも影響してしまうため、考え出すとこんがらがる。
こういうのは、サイコロの対面が必ず7になるように、和が同じになるペアに着目するとうまくいきそう。
１ ２ ３ ↕ ↕ ↕ ６ ５ ４
$N$ が偶数の場合
$S=1+2+...+N$ とする。また、$T=1+N$ とする。$T$ はペアの和となる。
ある頂点から、他の全ての頂点に辺を張った完全グラフを考える。
自身に対する辺のみが無いので、このままでは頂点 $v$ に隣接する頂点の和は $S-v$ となる。
ここで、ペアへの辺を1本だけ無くすと、$S-T$ となり、これは全ての頂点で同じとなる。
$N$ が奇数の場合
$T=N$ とする。頂点 $N$ だけぼっちとなる。上記と同様に構築すると、完全グラフの時点で頂点 $N$ に隣接する頂点の和は $S-T$ となり、他の頂点と等しくなっている。
n = int(input())
ans = []
if n % 2 == 0:
m = n + 1
else:
m = n
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
if i + j == m:
continue
ans.append('{} {}'.format(i, j))
print(len(ans))
print('\n'.join(ans))
C - Three Circuits
問題
- $N$ 頂点 $M$ 辺の単純連結無向グラフが与えられる
- グラフを、3つの閉路に分割できるか判定せよ
- 閉路は、同じ頂点を2回以上通過してもよい
解法
以下で全網羅できるという証明はよく分かっていないが、実験して「何となく出来そう」で通った。
まず、閉路を作るには、入る辺と出る辺で必ずペアが必要。これは閉路が重なり合っても変わらないので、全ての頂点の次数は偶数である。奇数の頂点があればNo。
その上で、
- 次数が6以上の頂点が1つでも存在すると、Yes
- 次数が4の頂点が3つ以上存在すると、Yes
- 次数が4の頂点が1つ以下だと、No
次数が4の頂点が2つの場合、2パターンに分かれる。
,--, ,--, ,--, ( ○ ○ ) →OK `--' `--' `--' ,--, |,--,| ○ ○ →NG |`--'| `--'
次数4の2頂点を $S,T$ として、$S$ から出発して $T$ を経由せず $S$ に戻ってくる辺があるかを調べればよい。
import sys
def solve(n, m, links):
v4 = set()
v6 = 0
for v, link in enumerate(links):
l = len(link)
if l % 2 == 1:
return False
if l == 4:
v4.add(v)
elif l >= 6:
v6 += 1
if v6 > 0:
return True
if len(v4) > 2:
return True
if len(v4) < 2:
return False
s = v4.pop()
t = v4.pop()
for c in links[s]:
visited = {s, t}
q = [c]
while q:
v = q.pop()
if v in visited:
continue
visited.add(v)
for u in links[v]:
if v != c and u == s:
return True
if u not in visited:
q.append(u)
return False
n, m = map(int, input().split())
links = [set() for _ in [0] * n]
for line in sys.stdin:
a, b = map(int, line.split())
a -= 1
b -= 1
links[a].add(b)
links[b].add(a)
print('Yes' if solve(n, m, links) else 'No')
D - Rotation Sort
問題
- ${1,...,N}$ の順列 $p=(p1,...,pN)$
- 以下の操作を好きな順序で繰り返して、$p$ を昇順にソートする
- コスト $A$ を支払い、任意の数 $p_i$ を取り出し、取り出した位置より右の任意の位置に挿入する
- コスト $B$ を支払い、任意の数 $p_i$ を取り出し、取り出した位置より左の任意の位置に挿入する
- 必要な総コストの最小値を求めよ
- $1 \le N \le 5000$
解法
最小カットで解く方法はありそうだけど、辺数が多くなりすぎるためTLE。（数字の大小が入れ替わっている場所では、小を右に持っていくか、大を左に持っていくか、少なくともどちらかは実行しなければならない、というのに見立てたグラフを作る）
解説pdfによると、DP。
この問題が行っているのは要は挿入ソートであり、最終的な順番のみが大事な挿入ソート系の問題では、途中段階において厳密なindexを考慮する必要は無い。「indexの間」にも入れられると考える方法がある。
【こういう風に、毎回indexを定義しなおさなくてもよい】 i 1 2 3 4 5 6 7 8 9 p 5 3 4 7 6 1 2 9 8 ,--------------' 1を左へ p 1 5 3 4 7 6 2 9 8 ↓ ,--------------' 2を左へ p 1 2 5 3 4 7 6 9 8 ...
【indexの間の位置も許して挿入すると考えてよい】
i 1 2 3 4 5 6 7 8 9
p 5 3 4 7 6 1 2 9 8
,--------------------------------------' 1を左へ
p 1 5 3 4 7 6 2 9 8
,-------------------------------------------' 2を左へ
p 1 2 5 3 4 7 6 9 8
`----------------, 5を右へ
p 1 2 3 4 5 7 6 9 8
...
ので、元のindexに加えて区間にも通し番号を付ける。これを $x$ とする。
i 1 2 3 4 5 6 7 8 9 x 0 )1( 2 )3( 4 )5( 6 )7( 8 )9( 10 )11( 12 )13( 14 )15( 16 )17( 18
括弧内は両端を含まないその間の任意の位置、括弧外はもともとの $i$ ちょうどの位置を示す。
各数字の初期位置は括弧外であり、数字の移動では必ず括弧内に挿入する。
同じ括弧内の区間に入った数字同士は、昇順になるように自由に並び替えられるとしてよい。 （括弧内に入っている数字は全て操作によって動かされた数字であり、操作では好きな箇所へ挿入できる）
こうすることで、$p_i$ を小さい方から順に、ソートされた状態を保ちながら挿入していくDPが可能になる。
$DP[k][x]$: $p_i=1～k$ まで考えて、$k$ の位置が $x$ だった場合の、最小コスト
- 初期化: $DP[0][0]=0$
- 答え: $\min(DP[N])$
$p_i$ の小さい順に挿入していくことで、DPで保持すべき状態が、1つ前の数字の位置だけで良くなる。（それより左の数字の並びがどうなっていようと、どうせそこには挿入しないので気にしなくてよい）
k=5 x=8 x 0 1 2 ...... 8 9 ~~~~~~~~~~~~~~ 5 1～4がどこかで |→ 6の挿入は5より右なので この順に並ぶ | 1～4の位置は考慮しなくてよい
$k→k+1$ の遷移は、「$k$ の移動後の位置 $y$」と「$k+1$ が最初に存在していた位置 $z$」の大小関係によって決まる。
$y < z$ の場合
$k+1$ は動かさなくても昇順を保てる。
$$DP[k+1][z] = DP[k][y]$$
ただ、この後の数字の位置関係によっては動かしておいた方が最小的なコストが小さくなるかも知れない。その場合、出来るだけ左に寄せておいた方がよい。
$k+1$ が移動できる最も左の位置は、$y$ が括弧内の場合 $y$、$y$ が初期位置の場合、$y+1$ となる。
$$ \left\{ \begin{array}{ll} DP[k+1][y] &= DP[k][y]+B & (y=even) \\ DP[k+1][y+1] &= DP[k][y]+B & (y=odd) \end{array} \right. $$
$y > z$ の場合
昇順を保つため、$k+1$ は必ず右に動かす必要がある。この場合の挿入位置も出来るだけ左、つまり $y$ のすぐ右でよい。
$$ \left\{ \begin{array}{ll} DP[k+1][y] &= DP[k][y]+A & (y=even) \\ DP[k+1][y+1] &= DP[k][y]+A & (y=odd) \end{array} \right. $$
■DPの遷移と、各状態が示す暫定数列の一例
[サンプル5]
9 40 50
5 3 4 7 6 1 2 9 8
i 1 2 3 4 5 6 7 8 9
x 0 )1( 2 )3( 4 )5( 6 )7( 8 )9( 10 )11( 12 )13( 14 )15( 16 )17( 18
初期p 5 3 4 7 6 1 2 9 8
"1" は、初期位置 z=11 に存在 | | | | | 1 | | |
・y=0
・動かさない DP[1][11] = 0 1
・動かす DP[1][ 0] = 50 1
"2" は、初期位置 z=13 に存在 | | | | | | 2 | |
・y= 0 の場合 (cost=50)
・動かさない DP[2][13] = 50 1 2
・動かす DP[2][ 0] = 100 1 2
・y=11 の場合 (cost=0)
・動かさない DP[2][13] = 0 1 2
・動かす DP[2][12] = 50 1 2
"3" は、初期位置 z=3 に存在 | 3 | | | | | | |
・y= 0 の場合 (cost=100)
・動かさない DP[3][ 3] = 100 1 2 3
・動かす DP[3][ 0] = 150 123
・y=12 の場合 (cost=50)
・必ず動かす DP[3][12] = 90 1 2 3
・y=13 の場合 (cost=0)
・必ず動かす DP[3][14] = 40 1 2 3
こんな感じで、直前の数字の位置のみを状態として、DPを遷移できる。
さて、ここまでの考察で、区間は「indexちょうど」と「その間」で分けたが、今回のように小さい方から確定させていけるDPの場合、半開区間で持ってもよい。区間数が半分になり、定数倍の高速化になる。
i 1 2 3 4 5 6 7 8 9 x 0 )[ 1 )[ 2 )[ 3 )[ 4 )[ 5 )[ 6 )[ 7 )[ 8 )[ 9
$k$ の位置が $y$ なら、$y$ の実態が整数座標でも小数座標でも、$k+1$ が挿入できる最も左の位置は $y$ である。
大きい方から見る場合は開区間と閉区間を逆にする。大小両方から見る必要があるような場合は、やはりindexちょうどとその間は区別する必要がある。
別解法
グラフを作って最短経路で解く。
通過する頂点は、位置を変化させない数字。通過しない頂点の位置を変化させる。
通過する頂点の位置を変化させないために、その間で前や後ろに持っていく必要のある数字の移動コストが、辺のコストになる。
from bisect import bisect
n, a, b = map(int, input().split())
ppp = map(int, input().split())
qqq = [0] * n
for i, p in enumerate(ppp, start=1):
qqq[p - 1] = i
dp = [(0, 0)]
for i in qqq:
s = bisect(dp, (i,))
ndp = [(j, cost + b) for j, cost in dp[:s]]
stay_cost = dp[s - 1][1]
ndp.append((i, stay_cost))
remain = iter(dp[s:])
for j, cost in remain:
if stay_cost > cost + a:
ndp.append((j, cost + a))
break
ndp.extend((j, cost + a) for j, cost in remain)
dp = ndp
print(dp[-1][1])
E - Modulo Pairing
問題
- 正整数 $M$ がある
- $2N$ 個の、$0 \le a_i \lt M$ の整数 $a_1,a_2,...,a_{2N}$ がある
- これを2つずつ組み合わせて $N$ 個のペアを作る
- ペアの「醜さ」を、ペアの数字をそれぞれ $x,y$ として、$(x+y) \mod{M}$ とする
- $N$ 個のペアの中での醜さの最大値を $Z$ とする
- $Z$ が最小となるようにペアを作ったときの値を求めよ
- $1 \le N \le 10^5$
- $1 \le M \le 10^9$
解法
解説pdfを読んだら理解と実装は比較的簡単だが、考察の時点で結構地道なパターン分けが必要。
最大値をなるべく低く抑えるということは、ペアの合計を均等にした方が良さそうなので、大きいのと小さいのを組み合わせる方向性が思いつく。
,---------, M=10 | ,-, | 0 2 3 4 5 9 `-----'
仮に、$\mod{M}$ の条件がないのであれば、つまり単にペアの和の最大値を低く抑えるのであれば、この組合せ方が正解となる。
これを確認する。$a \le b \le c \le d$ として、ペアの組み方は3通りある。
A B C
,--, | ,-----, | ,--------,
a b c d | a b c d | a b c d
`--' | `-----' | `--'
ある2通りのペアの組み方 $P,Q$ があって、醜さの最大値の比較で $Z_P \le Z_Q$ と言うためには、 「$P$ の全てのペアについて、それぞれ、より醜さが大きいペアが $Q$ に存在する」ということが言えればよい。
すると、$C$ のペアは、
(C) a + d <= (A) c + d (C) b + c <= (A) c + d (C) a + d <= (B) b + d (C) b + c <= (B) b + d
となり、$A,B$ より醜さの最大値は小さくなることが分かる。
もっとペアの数が増えても、上記のことを1つ1つ順に適用していくことで、最終的に「小さい方と大きい方から順に組み合わせていく」方針が最適となることが分かる。
ただ、modを含めて考えると、先ほどの例だと $Z=9$ になる。$M=10$ なので、答えとなり得る値の中で最大であり、そのまま適用するのはあまり有効そうではない。
ところで、各数字は $0 \le a_i \lt M$ なので、2つ足しても $2M$ を超えることはない。「和が $M$ を超えるペア」のスコアは必ず「2数の和$-M$」である。つまり、「和が $M$ を超えるペア」同士の間では、2数の和がそのまま大小比較に使える。
なので「和が $M$ 未満のペアに使われる数字」「$M$ 以上のペアに使われる数字」に分類した際、各分類の中での適切なペアの作り方は、やはり大きい方と小さい方から順に組み合わせる方針が適用できる。
※a～hは昇順にソート済み
,--------------,
| ,--, |
M未満 a c d f
M以上 b e g h
| `-----' |
`-----------------'
ここから、分類を組み替えることで、より $Z$ を小さく出来ないか考える。
こんなペア（左）があった時、こうする（右）と、
,-----, ,--,
M未満 a c → a b
M以上 b d → c d
`-----' `--'
ペア a + c a + b
b + d - M c + d - M
- (左) $a+c$ で $M$ 未満 ⇒ (右) $a+b$ は $M$ 未満
- (左) $b+d$ で $M$ 以上 ⇒ (右) $c+d$ は $M$ 以上
よって、組み替えた後も $M$未満/以上という分類は成立している。
また、$(左)a+c \ge (右)a+b$、$(左)b+d \ge (右)c+d$ が成り立つので、最終的な $Z$ の値も $Z_左 \ge Z_右$ となり、常に改善される。
他のケースも、考えていくと同じ事が言える。
,--------, ,--,
M未満 a d → a b
M以上 b c → c d
`--' `--'
a + d >= a + b
a + d > c + d - M (= d + (c - M) = d + 負)
,--, ,--,
M未満 b c → a b
M以上 a d → c d
`--------' `--'
b + c >= a + b
b + c > c + d - M (= c + 負)
なので、これを繰り返すと、和が $M$ 未満グループを左、$M$ 以上グループを右に寄せてしまってよいことがわかる。
,--------,
| ,--, |
M未満 a b c d
M以上 e f g h
| `--' |
`--------'
残る問題は、
- この分類が正しいのか（たとえば$b+c$は実際に$M$未満か？）
- 正しい分類が複数ある場合、どれが最小なのか
2番目の問題から考える。仮に $M$ 未満の個数を1減らしてみる。
,--,
M未満 a b
M以上 c d e f g h
| | `--' | |
| `--------' |
`--------------'
$\mod{M}$ の条件を取り除いたときの考察と同様に、変化前と変化後で、変化後の全てのペアのスコアが、変化前のいずれかのスコア以下、ということが言いたい。 そしてそれは実際に言える。
変化前 変化後 a + d >= a + b e + h - M >= c + h - M f + g - M >= d + g - M f + g - M >= e + f - M
よって、分類が正しく成立してるなら、$M$ 未満の個数はなるべく少ない方がよいと言える。 （厳密に証明するなら、項数 $N$ や変化前後の分類の個数について一般化する必要があるが）
分類が成立していて、$M$ 未満の個数が最も少ない境界を、2分探索で求める。
$a_1,a_2,...$ をソート後、真ん中に境界を仮定して、分類の成立を調べる。
- 成立、または $M$ 未満グループが不成立（和が $M$ 以上のペアが出来てしまう）なら左半分から境界を探索
- $M$ 以上グループが不成立（和が $M$ 未満のペアが出来てしまう）なら右半分から境界を探索
両方のグループが同時に不成立となることは無い。仮に $M$ 未満グループから $a,b$、$M$ 以上グループから $c,d$ が不成立だったとすると、矛盾する。
小← 分類の境界 →大 ... a ... b ... | ... c ... d ... ソート順: a <= b <= c <= d => a+b <= c+d 不成立条件: a + b >= M、c + d < M => a+b > c+d
def check(k):
ret = 0
b = 2 * k - 1
for j in range(k):
t = aaa[j] + aaa[b - j]
if t >= m:
return -1
ret = max(ret, t)
b = 2 * k
c = 2 * n - 1
for j in range(n - k):
t = aaa[b + j] + aaa[c - j]
if t < m:
return -2
ret = max(ret, t - m)
return ret
n, m = map(int, input().split())
aaa = sorted(map(int, input().split()))
l, r = 0, n
ans = -1
while l < r:
mid = (l + r) // 2
res = check(mid)
if res == -1:
r = mid
elif res == -2:
l = mid + 1
else:
ans = res
r = mid
if ans == -1:
ans = check(n)
print(ans)
