atcoder.jp
問題
- 1辺7の立方体を、座標空間上に3つ配置するよ
- V1,V2,V3が与えられるよ
- 3つの立方体のうち、丁度1つに含まれる領域の体積がV1
- 3つの立方体のうち、丁度2つに含まれる領域の体積がV2
- 3つの立方体のうち、丁度3つに含まれる領域の体積がV3
- になるような立方体の配置を教えてね。無理なら無理って言ってね
成約
- $1 \leq V_1,V_2,V_3 \leq 3 \times 7^{3}$
思考
- 3つの衝突判定面倒くさそうだなぁ、と思って割と早めに投げ捨てた…終了後、解説を読んで冷静に考えるととてももったいないことをした…
- まず、1辺7の立方体3つで、与えられた体積が実現できるの？で枝刈り
- 黒ココアさんの手癖。何も考えずに刈る。よくなさそう。
- 3つ置くことを考える時、1個は中心で固定しちゃって問題なさそう（直感）
- 残り2つが、固定した1つとの相対的な位置で話が進みそう（直感）
- 立方体2つを設置する座標を全探索しそう
- また、めっちゃ遠くに立方体を設置しても、共通領域が存在しないベタ付けしても、話はあんまり変わらなさそう
- 各方向に対して、-7~7までの座標で良さそう
- 0~7だとダメ
- 実は-1~7で良い、らしい（解説）
- 固定した立方体をAとした時、以下の2種類の数値を考える
- AとBの共通部分
- BとCの共通部分
- CとAの共通部分
- AとBとCの共通部分
- ベン図を書いてみて、上記4つが分かれば、V1も計算できるね
- 後は、全体の計算量の見積もり
- -7~7の15座標が、3方向
- その立方体を2つ置くので、$O(15^{6}) \fallingdotseq 10^{7}$で間に合うとの話
- 実装面倒くさい問題だったけど、話は割とシンプルだった、とかいう…
コード
import sys
input = sys.stdin.buffer.readline
V = list(map(int,input().split()))
if 7*7*7*3 != V[0] + 2*V[1] + 3*V[2]:
print("No")
exit()
ax,ay,az = 0,0,0
def calc_v3(bx,by,bz,cx,cy,cz):
xl = sorted([ax,bx,cx])
x = xl[0] - xl[2] + 7
if x <= 0:return 0
yl = sorted([ay,by,cy])
y = yl[0] - yl[2] + 7
if y <= 0:return 0
zl = sorted([az,bz,cz])
z = zl[0] - zl[2] + 7
if z <= 0:return 0
return x*y*z
def calc_v2(ax,ay,az,bx,by,bz):
x = min(ax,bx) - max(ax,bx) + 7
if x <= 0:return 0
y = min(ay,by) - max(ay,by) + 7
if y <= 0:return 0
z = min(az,bz) - max(az,bz) + 7
if z <= 0:return 0
return x*y*z
for bx in range(-7,8):
for by in range(-7,8):
for bz in range(-7,8):
for cx in range(-7,8):
for cy in range(-7,8):
for cz in range(-7,8):
v3 = calc_v3(bx,by,bz,cx,cy,cz)
if v3 != V[2]: continue
abv = calc_v2(ax,ay,az,bx,by,bz)
cav = calc_v2(ax,ay,az,cx,cy,cz)
bcv = calc_v2(cx,cy,cz,bx,by,bz)
v2 = abv + cav + bcv - 3*v3
if v2 != V[1]: continue
v1 = 7**3*3 - 2*v2 - 3*v3
if v1 != V[0]: continue
print("Yes")
print(ax,ay,az,bx,by,bz,cx,cy,cz)
exit()
print("No")
