ABC 343 E — 7x7x7

考察

平行移動で体積は変わらないので、一つのcubeをC1=(0,0,0)に固定する。重なりgraphが連結なら、三角形の場合は任意のcubeを、長さ2のpathの場合は中央のcubeをC1に選ぶ。残る二つはC1と重なるため、各軸の座標差は[-7,7]に入る。重なる一組と孤立した一個に分かれる場合は、重なる組の一方をC1にし、もう一方とのx差を見て孤立cubeを反対側のx=±7へ置く。これで既存の重なりを変えず、孤立cubeは両方から離れる。全て互いに離れているなら、x座標を−7,0,7として配置すれば全ての交差体積0を保つ。いずれも同じ三領域体積を持つ代表配置が各座標差[-7,7]にある。

よってC2,C3の6座標だけを[-7,7]で列挙する。各二個の共通体積の和をP、三個の共通体積をTとすると、三重領域V3=T、二重領域V2=P-3T、単独領域V1=3·7^3-2V2-3V3である。各候補の体積条件を調べる。

典型の発動条件

平行移動対称性の固定

発動条件: 配置問題の目的が物体間の相対位置だけで決まる。

一つのcubeを原点へ固定し、接触まで平行移動できることから残る6座標を[-7,7]へ界して15^6候補を全列挙する。

包除的なexact coverage集計

発動条件: pair/triple intersectionからexactly k個に覆われるvolumeを求めたい。

多重に数えたtriple領域の係数を補正し、体積総和式でv1を得る。

問題固有の要素

side lengthが7の軸平行cube同士のintersectionも軸平行直方体なので、3D体積は各axisのinterval overlap長の積へ完全分離する。

別の問題へ持ち帰る視点: 直積形状の交差量は各次元の一次元overlapを独立計算して掛ける。

正当性

軸平行cubeの交差体積は、各軸の区間交差長の積で正確に求まる。上の有界配置に解が必ず含まれるため、全6座標の列挙は可能な解を落とさない。またPでは三重領域を3回数え、Tでは1回数えるので、V2=P−3Tとなり、総cube体積からV1も復元できる。列挙で条件を満たした候補は指定された各領域体積を持つため、探索の成功・失敗は解の存在と一致する。

実装上の注意

  • 境界で接するだけならoverlap長0であり候補範囲には±7を含める。v2=P-3v3、v1=1029-2v2-3v3の係数を混同しない。

復習の核

  • 三cube一致、全てdisjoint、pairだけoverlap、triple overlapありを手計算し、出力座標からvolumeを再検算する。

計算量と制約

時間

O(15⁶)、各候補のintersectionはO(1)。

空間

O(1)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 0 \leq V_1, V_2, V_3 \leq 3 \times 7^3; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

7x7x7 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 候補数を界して全列挙・有限case分解する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 有界全列挙・有限case分解

    補助タグ: 幾何の基本判定・配置・座標変換 集合上の包除原理

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 候補数を界して全列挙・有限case分解する

    • 制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。

    先に読む単元:

    この解説で扱わないこと:

    • 探索空間を二つへ分けて照合するmeet-in-the-middle、および再帰部分問題へ分ける分割統治。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題