日立製作所 社会システム事業部 プログラミングコンテスト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演算で作り上げると楽だし高速。

programming_algorithm/contest_history/atcoder/2020/0308_hitachi2020.txt · 最終更新: 2020/03/12 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0