目次
日立製作所 社会システム事業部 プログラミングコンテスト2020 C,D,E問題メモ
Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020
3完でそこそこのレートは出たけど、DかEのどちらかは解きたかったところ。
C - ThREE
問題
- $N$ 頂点の木、$i$ 番目の辺は $a_i$ と $b_i$ を結ぶ
- 以下の条件を満たすように、各頂点に $1～N$ の数字を1つずつ割り当てる
- 頂点 $i$ に割り当てられた数字を $p_i$ とする
- 距離が3だけ離れた全ての頂点組 $(i,j)$ について、$p_i,p_j$ の和または積が3の倍数である
- 可能な割り当てがあるか判定し、可能なら割り当て方を1例求めよ
- $1 \le N \le 2 \times 10^5$
解法
$p_i$ が3の倍数であれば、$i$ から3個離れた頂点の数字は何でもよい。 そうでなくて、たとえば $3k+1$（3で割って1余る数）なら、3個離れた頂点の数字は「3の倍数」または「$3k+2$（3で割って2余る数）」でなければならない。
自身から3個離れた頂点が多い頂点から優先的に3の倍数を割り振るのが効率的？とか考えても、 そもそも3個離れた頂点のペアは最大 $10^{10}$ 近くになるのでとても列挙できないし、 3の倍数が尽きたときの処理が結局よく分からない。
3の倍数が関わらないペアでは「$3k+1$ と $3k+2$ をペアにする」さえ守ればよくて、他の条件はよく考えると無いので、3の倍数と言いつつ注目すべきグループは2つしかない。
2部グラフを思いつく。
適当に値を決めて、根からの距離が偶数と奇数グループに分けると、距離が3だけ離れた頂点は必ず2つのグループから1つずつ選ばれる。
よって、一旦グループ分けすればグラフの具体的な形は無視してよくて、 一方を $3k+1$、他方を $3k+2$ から割り振っていって、足りないのを $3k$ で補うと条件を満たす。
(例) N = 10 偶数 1 4 7 10 3 (3k+1 と 3) 奇数 2 5 8 6 9 (3k+2 と 6 9)
ただし、この方針は注意があって、頂点数が一方のグループにやたら偏っていると上手くいかない。
どこまで偏っているとダメかというと、少ない方のグループが $3k+2$ の個数より少なければ、もう一方にはみ出してしまう。
3k+1 1 4 7 10 3k+2 2 5 8 ←少ない方のグループの頂点数が3未満だと、 3k 3 6 9 上記の方法では矛盾が生じる可能性がある 偶数 1 4 7 10 3 6 9 ⑧ ← 3k+2 を割り振らざるを得ない 奇数 2 5
しかしその場合、少ない方のグループは $3k$ の個数以下である。（$3k+1,3k+2,3k$ の個数の差は高々1）
少ない方のグループ全てに3の倍数を割り当てることが可能であり、するともう一方は何でもよくなるので、偏りがある場合はそうすればよい。
結局、どんな場合でも条件を満たすように構築できる。
import sys
def part(s, links):
grp = [set(), set()]
q = [(s, -1, 0)]
while q:
v, p, g = q.pop()
grp[g].add(v)
for u in links[v]:
if u == p:
continue
q.append((u, v, g ^ 1))
return grp
def solve(n, links):
grp = part(0, links)
can = [[], [], []]
for i in range(1, n + 1):
can[i % 3].append(i)
if len(grp[0]) > len(grp[1]):
grp[0], grp[1] = grp[1], grp[0]
ans = [0] * n
if len(grp[0]) <= len(can[0]):
for v in grp[0]:
ans[v] = can[0].pop()
can = can[0] + can[1] + can[2]
for v in grp[1]:
ans[v] = can.pop()
return ans
for v in grp[0]:
if can[2]:
ans[v] = can[2].pop()
else:
ans[v] = can[0].pop()
for v in grp[1]:
if can[1]:
ans[v] = can[1].pop()
else:
ans[v] = can[0].pop()
return ans
n = int(input())
links = [set() for _ in range(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(*solve(n, links))
D - Manga Market
問題
- $N$ 個の店がある
- 高橋君は時刻0に自宅にいて、いくつかの店を回る予定を立てている
- 自宅から各店、また各店間の移動には全て1分かかる
- 時刻 $t$ に店 $i$ に着くと、行列のため買い物には $a_i t + b_i$ 分かかる
- 時刻 $T$ までに、最大いくつの店で買い物が出来るか
- $T$ ちょうどに買えたのはセーフだが、並んでる途中はアウト
- 移動時間と買い物時間以外の時間は無視できる
- $1 \le N \le 2 \times 10^5$
- $0 \le a_i,b_i \le 10^9$
- $0 \le T \le 10^9$
解法
優先順位付きナップサック。
店を回る順番まで考慮するには制約が大きいので、回る店の集合が決まったら、効率の良い順番は貪欲に決まるのでは？と疑う。
「店 $i$ と $j$ に続けて行くのなら、常に先に $i$ に行った方がいい」という関係性が成り立たないかチェックする。それまでの買い物と移動に $t$ かかったとして、
- $i→j$
- $i$ 終了+移動: $t + a_it + b_i + 1 = (a_i+1)t + b_i + 1$
- $j$ 終了+移動: $(a_j+1)((a_i+1)t + b_i + 1) + b_j + 1 = S_{i→j}$
- $j→i$
- $j$ 終了+移動: $(a_j+1)t + b_j + 1$
- $i$ 終了+移動: $(a_i+1)((a_j+1)t + b_j + 1) + b_i + 1 = S_{j→i}$
で、$S_{i→j} \lt S_{j→i}$ となるための条件を移項して整理すると、綺麗に $t$ が打ち消し合って消えてくれる。添字が同じものを同じ側に持っていくと、
- $\dfrac{a_i}{b_i+1} \gt \dfrac{a_j}{b_j+1}$
となり、この指標が大きい方を先に（訪れるのであれば）訪れた方が、訪問時刻にかかわらずよいことがわかる。
以下のDPを考える。
- $dp[i][k]=$ 指標の大きい方から $i$ 番目の店までを見て、$k$ 店で買い物を済ませたときの、最短時刻（次の店への移動含む）
しかしこれ、$i$ も $k$ も最大 $N$ となり、$O(N^2)$ は間に合いそうにない。
ここで、この問題独特の考察が必要となる。つまり、「$a_i \ge 1$ なら、常に $t$ は1つの店ごとに2倍以上になる」
$a_i=1,b_i=0$ のミニマムを想定しても、買い物終了時刻（次の店に並びはじめられる時刻）は1店舗毎に $1→3→7→15→...$ となるので、意外と多くの店は回れない。
$T$ の上限が $10^9 \lt 2^{30}$ より、最大でも30店舗程度となる。
これならDPが回る。
$a_i \ge 1$ の店舗だけのDPで、各 $k$ について最短時間が求まったら、 そこから残り時間で $a_i=0$ の店に何軒行けるか $k$ 毎にチェックする。$b_i$ の小さい店から訪れた方がよい。
import sys
from bisect import bisect
from itertools import accumulate
n, t = map(int, input().split())
constant = []
variable = []
for line in sys.stdin:
a, b = map(int, line.split())
if a == 0:
constant.append(b + 1)
else:
variable.append((a / (b + 1), a, b))
constant.sort()
variable.sort(reverse=True)
INF = 10 ** 10
t += 1
t2 = t.bit_length() + 1
# dp[j]: (i番目まで見て) j件の店で買い物を完了した時の、次の店に到着できる最短時間
dp = [INF] * t2
dp[0] = 1
for _, a, b in variable:
for j in range(t2 - 1, -1, -1):
if dp[j] == INF:
continue
tmp = (a + 1) * dp[j] + b + 1
if tmp > t:
continue
if dp[j + 1] > tmp:
dp[j + 1] = tmp
const_acc = list(accumulate(constant))
ans = 0
for i, c in enumerate(dp):
if c == INF:
break
remaining = t - c
k = bisect(const_acc, remaining)
ans = max(ans, i + k)
print(ans)
E - Odd Sum Rectangles
問題
- $2^N-1$ 行 $2^M-1$ 列の各マスに、0または1を書き込む
- 左上 $(i_1,j_1)$、右下 $(i_2,j_2)$ の矩形領域に含まれる数字の和を $S(i_1,i_2,j_1,j_2)$ とする
- $(i_1,i_2,j_1,j_2)$ の組は $\dfrac{2^N(2^N-1)}{2} \times \dfrac{2^M(2^M-1)}{2}$ 通りあるが、全ての組について $S$ を求めるとき、$S$ が奇数となる組が最大となるような書き込み方を1つ構築せよ
- $1 \le N,M \le 10$
解法
まず書き込み方が決まっているとして、その上で $S$ が奇数となる個数を問う問題を考えてみる。
こういうのは2次元累積和で求められる。今回、偶奇にしか興味が無いので、XORで累積和を取る。先頭には便宜的に0を置く。
↓方向 →方向
(0 0 0) (0 0 0 0)
1 0 0 1 0 0 (0) 1 1 1
0 1 1 1 1 1 (0) 1 0 1
1 1 0 0 0 1 (0) 0 0 1
すると、ある矩形領域に含まれる数の和は、以下で求められる。
A│ B
──┼────┐ D - B - C + A
│ │
│ │ 今回は偶奇のみなので、^をXORの演算子として
C│ D│ A ^ B ^ C ^ D
└────┘
これが奇数になるとは、ABCDが (0,0,0,1) か (1,1,1,0) のように、3つが同じで1つだけ違うような状態になってるということである。 つまり「A=B なら C!=D」「A!=B なら C=D」となっている組が多いと嬉しい。
これを「理想の組」と呼ぶことにする。
矩形の和の問題が、累積和を取ることで、その4つ角の数字の組の問題になった。
後は、理想の組となる数を最大化した累積和盤面を作れれば、逆算して元の盤面を出力すればよい。
で、どうやって作るかをさっぱり思いつけず。
以下解説PDF読了後。
行、列の与えられ方が独特で、累積和を取ったときに便宜的に加えた1行を合わせるとちょうど2のべき乗となるので、 そこから構築方法を推察できなくもないが……難しい。
累積和を取った後の盤面の $i$ 行 $j$ 列目を $f_{i,j}$ で表す。
縦列 $j_1,j_2$ を固定して考える。$f_{i,j1}=f_{i,j2}$ となる行の個数を $r_0$、$f_{i,j1} \neq f_{i,j2}$ の行の個数を $r_1$ とする。
j1 j2 0 0 同じ →r0 1 0 異なる →r1 1 1 同じ →r0 0 1 異なる →r1 ...
縦列を固定した上での理想の組の個数は、$r_0,r_1$ それぞれから1行ずつピックアップして組にすれば良いので $r_0 \times r_1$ となる。
$r_0+r_1=2^N$ という制約があるので、これは $r_0 = r_1 = 2^{N-1}$ の場合が（そういう風に置けるのであれば）最適である。
$j_1,j_2$ を固定したら、その中で最大化するには $r_0,r_1$ を同数にすることとわかった。 なので、そのような $j_1,j_2$ の組を出来るだけ増やしたい。 究極的に言うと、全ての $j_1,j_2$ の組で $r_0,r_1$ を同数にできたら、文句なくそれが最大だと言える。
希望条件: 全ての $(j_1,j_2)$ の組で、$r_0,r_1$ が同数となるように0,1を配置できるか？
これは、$N=M$ の盤面であれば以下のようにすると実現可能である。
$N=M=1$ から初めて、数学帰納法的に $N=M=k$ （$k=2,3,...$）を作っていく。
まず累積和を取ったときの先頭行と先頭列は全て0なので、$N=M=1$ の時、右下には1を入れるのがよい。これで同数を達成できている（そもそも1組ずつしかない）。
0 0 0 1
ここから $N=M=2$ を考えると、縦と横には同じものを連結、そして右下の部分には、0,1を反転したものを置けばよい。
0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0
あたかも $\begin{bmatrix}0 & 0\\0 & 1\end{bmatrix}$ を1つの'0'と見做し、再帰的に同じように配置していく感じ。フラクタルっぽい。
解説を見たらそれで上手くいくことは分かっても、どうやったら思いつくのか、道筋が見えづらい。
希望条件を満たす盤面を元にして、まず縦にだけ2倍した盤面を作るなら、 元の盤面で任意の列の組において $r_0,r_1$ が同数であることが保証されているので、縦に繰り返しても同数なのは変わらない。 また、先頭列は'0'固定なので、それを踏まえても繰り返すのは自然な発想とは言える。
それを横に拡張するとき、ここでも単に繰り返すだけでも、だいたいの列においては $r_0,r_1$ が同数となるが、 唯一、拡張前に存在しなかった「同じ列（に相当する箇所）が選ばれる」場合のみ、当然ながら2列は全く一緒になり、条件を満たさなくなってしまう。
a b c d 縦・横ともに同じものを繰り返した盤面 0 0 0 0 0 1 0 1 (a,c), (b,d) が条件（r0=r1）を満たさない 0 0 0 0 0 1 0 1
それを解消する手段が、下半分だけ反転させる、ということになる。
希望条件を満たすなら「a列は全て0である」「a列と任意の列との組で、$r_0=r_1$ となる」以上、a列以外に含まれる'0'と'1'の個数は同数となっているはず。 それを踏まえれば「c列にも'1'が半分含まれないといけない」が、反転を思いつく取っかかりとなる……か？
n, m = map(int, input().split())
ans = [0, 1]
for i in range(1, min(n, m)):
k = 1 << i
x = (1 << k) - 1
slide = [a << k for a in ans]
new_ans = [s | a for s, a in zip(slide, ans)]
new_ans.extend(s | (a ^ x) for s, a in zip(slide, ans))
ans = new_ans
if n > m:
ans *= 1 << (n - m)
elif n < m:
for i in range(n, m):
k = 1 << i
ans = [(a << k) | a for a in ans]
ans = [a0 ^ a1 for a0, a1 in zip(ans, ans[1:])]
ans = [a ^ (a >> 1) for a in ans]
print('\n'.join(map(('{:0' + str(2 ** m - 1) + 'b}').format, ans)))
Pythonは $2^{1024}$ 程度ならbit演算で作り上げると楽だし高速。
