日立製作所 社会システム事業部 プログラミングコンテスト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の倍数を割り当てることが可能であり、するともう一方は何でもよくなるので、偏りがある場合はそうすればよい。

結局、どんな場合でも条件を満たすように構築できる。

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$ の小さい店から訪れた方がよい。

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'が半分含まれないといけない」が、反転を思いつく取っかかりとなる……か？

Pythonは $2^{1024}$ 程度ならbit演算で作り上げると楽だし高速。