目次
Keyence Programming Contest 2020 A～E問題メモ
A - Painting
問題
- $H \times W$ のマス目があり、始めは全て白
- 操作を繰り返してマスを黒く塗る。1回の操作では以下の2つのどちらかを行う
- 行を1つ選んで全て黒く塗る
- 列を1つ選んで全て黒く塗る
- $N$ マス以上が黒く塗られた状態にするために必要な最小操作回数を求めよ
- $1 \le H,W \le 100$
- $1 \le N \le H \times W$
解法
1回の操作で多く塗りたい。行、列の長い方を選ぶと1回で $\max(H,W)$ 個塗れる。$N$ を割って切り上げた値が答え。
h = int(input()) w = int(input()) n = int(input()) print((n - 1) // max(h, w) + 1)
B - Robot Arms
問題
- 数直線上に $N$ 個のロボットがある
- $i$ 番目のロボットは座標 $X_i$ に位置し、腕の長さは $L_i$
- この場合、ロボットは $X_i-L_i \le x \lt X_i+L_i$ の範囲に腕を伸ばせる
- どの2つのロボットも腕を伸ばせる範囲が被らないように、いくつかロボットを取り除く
- 残せるロボットの最大数を求めよ
- $1 \le N \le 10^5$
- $0 \le X_i \le 10^9$
- $0 \le L_i \le 10^9$
解法
ロボットを、$[X_i-L_i, X_i+L_i)$ を覆う1つの区間と見なすと、これは区間スケジューリング問題そのものである。
右端が左にある区間から順に、残せるなら貪欲に残していけばよい。
典型とはいえ、ABCなら200点ではまず出されない気はする。ただ、問題の配点は1つのコンテスト内での相対的な関係以外、あまり参考にしない方がよい。
import sys
from operator import itemgetter
n = int(input())
robots = []
for line in sys.stdin:
X, L = map(int, line.split())
l, r = X - L, X + L
robots.append((l, r))
robots.sort(key=itemgetter(1))
curr = -1
ans = 0
for l, r in robots:
if curr > l:
continue
ans += 1
curr = r
print(ans)
C - Subarray Sum
問題
- 3つの整数 $N, K, S$ が与えられる
- 1以上 $10^9$ 以下の整数からなる長さ $N$ の数列 $A_1,A_2,...,A_N$ で、以下の条件を満たすものを1つ構築せよ
- $A_l+A_{l+1}+...+A_r=S$ を満たすような $(l,r)$ の組はちょうど $K$ 個ある
- $1 \le N \le 10^5$
- $0 \le K \le N$
- $1 \le S \le 10^9$
解法
問題Bとは打って変わって、思いつけば「え、そんなんでいいの」というような問題。
$0 \le K \le N$ という制約が鍵。つまり単独で $A_i=S$ であるような要素を $K$ 個作り、他の区間では和が $S$ にならないようにすれば、それで条件を満たす。
他の区緩和が $S$ にならないようにするには、たとえば $K$ 個以外の要素を $S$ より大きい数にすればいい。
ただし、$S=10^9$ の場合のみ、要素を $10^9$ より大きくはできないので、たとえば1にする。$N \le 10^5$ より、どんなに1が連続しても区間和が $10^9$ になることは無い。
n, k, s = map(int, input().split()) print(*([s] * k + [1 if s == 10 ** 9 else s + 1] * (n - k)))
D - Swap and Flip
問題
- $N$ 枚のカードがあり、片方の面は赤、もう片方は青く塗られている
- $i$ 番目のカードの赤い面には整数 $A_i$、青い面には整数 $B_i$ が書かれている
- 最初、全てのカードは番号順に左から、赤い面を表に置かれている
- 以下の操作を何回でも行える
- 隣り合う2枚のカードの位置を交換し、同時に両方とも裏返す
- 最終的に表を向いている数字が、左から広義単調増加になるようにしたい
- 可能か判定し、可能なら最小操作回数を求めよ
- $2 \le N \le 18$
- $1 \le A_i,B_i \le 50$
解法
$N$ も $A_i,B_i$ も小さい。
まず、手元で簡単な例を試すと、以下の点に気付く。
- $i$ 番目のカードが最終的に左から $j$ 番目に移動したら、そのカードに対する操作回数と、$i-j$ の偶奇は一致する
- それに伴い、最終的に表になっている面も分かる
- 偶数なら赤
- 奇数なら青
これで、カードを最終的に置く場所が決まれば、裏表の場合分けはしなくて済む。
しかし、最終位置は $N!$ 通りあるので、まだ全探索は不可能。動的計画法的に情報をまとめるか、枝刈りが必要。
最終位置を左から決めていくことを考える。
初期位置 1 2 3 4 5 最終位置 4 2 5 1 3
この最終位置に対する操作回数は転倒数であり、左から順に要素を確定させていった回数と一致する。 未確定のカードは初期位置順に並び、未確定の中で $k$ 番目のカードを左に持って行くには $k-1$ 回の操作がかかる。
4を移動 4 | 1 2 3 5 3回 2を移動 4 2 | 1 3 5 1回 5を移動 4 2 5 | 1 3 2回 1を移動 4 2 5 1 | 3 0回 => 計6回
左から $j$ 番目の位置まで確定していて、残りの部分からスコアを求めるには、どういった情報が必要か。
- 残るカードの集合
- $j$ 番目までの操作回数
- $j$ 番目のカードで表になっている数字
よって、以下のDPを考える。
- $DP[grp][num]=$ 未確定のカードの集合のbit表現が $grp$ で、最右の確定済みのカードで表になっている数字が $num$ の時の、最小操作回数
これを、立っているbitの数が多い方から埋めていくと、$DP[0][num]$ の中で、最小の値を持つものが答えとなる。
計算量は、grpが $2^N$ 通り、$num$ も $A_i,B_i$ の値の種類数つまり最大 $2N$ 通りの状態があり、各遷移が $N$ かかるので、$O(N^2 2^N)$ となる。
一方、操作回数と最右の数字を入れ替えたこんなDPも作れるが、
- $DP[grp][op]=$ 未確定のカードの集合のbit表現が $grp$ で、操作回数が $op$ の時の、確定済みカードの最も右で表になっている数字
こちらは、$op$ の状態数が大きくなりすぎるため、TLEとなる。 $A_i,B_i$ の範囲が小さいことを利用する。
def iter_bit(k, LIMIT):
v = (1 << k) - 1
while v < LIMIT:
yield v
x = v & -v
y = v + x
v = (v & ~y) // x >> 1 | y
def solve(n, cards):
dp = [{} for _ in range(1 << n)]
dp[-1][0] = 0
LIMIT = 1 << n
for d in range(n):
for state in iter_bit(n - d, LIMIT):
scores = dp[state]
k = state
curr = 0
while k:
b = k & -k
i = b.bit_length() - 1
num = cards[i][(d - i) % 2]
next_dp = dp[state ^ b]
for left_num, score in scores.items():
if left_num > num:
continue
ns = score + curr
if num not in next_dp or next_dp[num] > ns:
next_dp[num] = ns
k ^= b
curr += 1
if len(dp[0]) > 0:
return min(dp[0].values())
else:
return -1
n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
cards = list(zip(aaa, bbb))
print(solve(n, cards))
E - Bichromization
問題
- $N$ 頂点 $M$ 辺の無向グラフが与えられる
- $i$ 番目の辺は $U_i$ と $V_i$ を結ぶ
- ここから「各頂点を白か黒で塗り分ける」「辺に重みを付ける」という2つの処理を行う
- $D_1,D_2,...,D_N$ が与えられる
- 以下の条件を満たす塗り分け方・重みの付け方が可能か判定し、可能ならを1つ構築せよ
- 白、黒の頂点はそれぞれ1つ以上ある
- 頂点 $i$ から、異なる色の頂点への最短距離はちょうど $D_i$ である
- $2 \le N \le 10^5$
- $1 \le M \le 2 \times 10^5$
- $1 \le D_i \le 10^9$
解法
最小の $D_i$ を考えたとき、わりと可能な状態は少ないことに気付く。以下の例で、5が最小の $D_i$ であるとする。
b --- 5 --- a --- g --- f 数字,記号はDiを表す
`--- d ---' 便宜上、頂点のこともDiで呼ぶ
異色の頂点に距離5でたどり着くには、当然、その最短路に含まれる辺には5以下の重みをつけなければならない。
(頂点5の条件を満たす塗り分け方と重みの設定例) 頂点 5 --- a --- g --- f 色 B B B W 重み 1 3 1
しかし、5からまず最初に出る辺(5-a)を考えると、
- 5とaが同色
- 頂点5が距離5でたどり着けるなら、aはそれ未満でたどり着けることになる
- →5が最小の $D_i$ であることに矛盾
- 5とaが異色
- 辺の重みは5に設定することになる。aの側から見たら、異色の頂点（=5）に距離5でたどり着けることになる
なので、$a=5$ の時のみ、条件を満たす方法が存在する。
より広げていうと、ある頂点 $D_i$ に対してそこから直接繋がる頂点の内、最小のものを $D_j$、辺を $L_{i,j}$ とすると、
- $D_i \lt D_j$ のとき、すぐ上の理由で矛盾
- $D_i \ge D_j$ のとき、$L_{i,j}$ の重みを $D_i$ とし、$i$ と $j$ を異色にする
これを全ての頂点に対して繰り返す。矛盾する頂点が1つでもあると不可能。
サンプル1（丸付き数字はDi）
③--------④-----⑤-----⑦
`---③---'
注目中の頂点を黒丸で示す。
❸--------④-----⑤-----⑦ ❸にとって、隣接中最もDjの小さい頂点は③
3`--③---' よってその間の辺の重みを3に設定
③--------④-----⑤-----⑦ ❸にとっても同様
3`--❸---'
③----4---❹-----⑤-----⑦ ❹にとっては隣接最小は③（2つあるが、どちらか一方）
3`--③---' その間を4に設定
③----4---④--5--⑤--7--⑦ 以下同様。
3`--③---' ←の③-④を結ぶ辺は最後まで設定されなかった
この過程で重さが設定される辺数は、1頂点から1辺が設定されるので最大 $N$ 辺（重複する可能性はある）。 他の辺を最大値 $10^9$ にしておけば、とりあえず色を無視して「一番近い頂点に距離 $D_i$ で行ける」という距離の要件は満たす。
後は、その $N$ 辺の各辺について両端の頂点の色を逆にすると、条件を満たせる。
懸念点としては、$N$ 辺に奇数長の閉路が含まれると、隣り合う頂点同士が異なるように塗れない。 しかし、最も $D_j$ が小さい頂点を選んでいるため、閉路ができるのは閉路中の頂点が全て同じ $D$ を持つ場合しかありえない。 また、それも「$D_j$ が同じ場合は、辺番号（または頂点番号）が小さいものを優先する」とタイブレークを一意にしておけば防げるため、閉路の可能性は除外できる。
結果として $N$ 辺のみからなるグラフは森となり、連結成分ごとにDFSなどで隣り合う頂点を別にしながら色を設定していけばいい。
import sys
from operator import itemgetter
def solve(n, m, ddd, links):
ddi = list(enumerate(ddd))
ddi.sort(key=itemgetter(1))
LIMIT = 10 ** 9 + 1
costs = [LIMIT] * m
for v, dv in ddi:
du, li, u = min(links[v])
if du > dv:
print(-1)
return
costs[li] = dv
colors = [-1] * n
for i in range(n):
q = [(i, 0)]
while q:
v, color = q.pop()
if colors[v] != -1:
continue
colors[v] = color
for du, li, u in links[v]:
if costs[li] == LIMIT:
continue
q.append((u, color ^ 1))
MAX = 10 ** 9
costs = [MAX if cost == LIMIT else cost for cost in costs]
print(''.join('BW'[c] for c in colors))
print('\n'.join(map(str, costs)))
n, m = map(int, input().split())
ddd = list(map(int, input().split()))
links = [[] for _ in range(n)]
for li, line in enumerate(sys.stdin):
u, v = map(int, line.split())
u -= 1
v -= 1
links[u].append((ddd[v], li, v))
links[v].append((ddd[u], li, u))
solve(n, m, ddd, links)
