Skip to content

第二回マスターズ選手権-決勝-

問題概要

  • 平面上(10^6 * 10^6)に、X個の燃えるゴミ、Y個の燃えないゴミ、Z個の資源ゴミが点として表されている
  • 1回の指示で、2人がそれぞれ両手の座標を指定した位置に動かし、動かした範囲内のゴミをすべて回収する
    • 簡単のため、1人目の左手、1人目の右手、2人目の左手、2人目の右手の順で動かしたときの範囲や優先順で回収される
    • 開始地点は任意
  • このとき、移動時間は、それぞれの両手の移動距離の和で大きい方だけかかる
  • できるだけ移動時間が短くなるように、資源ゴミを回収せず、1人目はすべての燃えるゴミのみ、2人目はすべての燃えないゴミのみを回収するような指示の出し方を求めよ
  • 問題ごとの違い
    • A問題: X=100, Y=0, Z=10〜100
    • B問題: X=100, Y=100, Z=0
    • C問題: X=100, Y=100, Z=1〜100 (D問題で提出された各チームの自作ケースからなる)
    • D問題: C問題向け自作ケース生成

時間

  • 360 分

個人的メモ

「移動距離を最小化」

  • 移動距離を小さくするのが目的なので、微小移動が多い(手数が多い)ような操作でも移動距離が小さければあまり問題はない
  • 手の位置が行ったり来たりが発生するようなアプローチだと、移動距離が増えてしまい、スコアがあまりでない
    • 取りこぼしを取りに行ったりや、資源ゴミを避けるために大きく動く必要がある、など
    • 適当に次の手の位置を探索するような貪欲・ビームとかはあまり良い方針ではなかった模様
  • また、2人のうち、移動距離が大きい方のみスコアに影響するので、移動距離が短い方はいい感じに位置調整する余地もある

自作ケース(D問題)

  • 今回、各チームが前半にD問題に提出した自作ケース(4つ)からC問題のテストケースが作られるという形式になっていた
    • 決勝進出チームのみ
    • そのため、C問題は提出は後半から可能
    • 4ケース中1ケースが別途質問ページから公開されていた
    • 未提出や提出失敗している場合は、自動生成のものが使われる
    • 自チームのケースは事前にわかるので、埋め込みなども許されていた
  • 回収に失敗したりすると結構スコアに差がでたりもするため、地獄のような配置へのケアも考慮する必要があった
    • パターンに対応した解法、失敗しない解法、など
    • 特に、外周や直線上に配置されるケースなどは、避けたり、回収順番など気をつけないとかなり厳しい
  • パターン
    • 直線上に並べる
    • 外周上に並べる
    • 4つ角に固める
    • 最長ケース
    • 等間隔・グリッド的に配置する
    • 少数だけ離れた場所に配置する
    • 円形・ミラー的に配置する
    • 資源ごみを壁として利用する

アプローチ

TSP(1本道)ベース

  • 手を点で考えると、全点を訪問する最小距離の問題になるので、TSP(1本道)を作って回収することが考えられる
  • 片手で回収
    • 片手を固定して、もう片手だけを動かして回収できるなら、片手分だけの移動距離で済むので、移動距離が減る可能性がある
    • 凸包、クラスタリング、など
  • 並列化
    • 辿るときに、他の拾いたくないゴミを回収しないならば、それぞれの手が分担して並列に回収することで、移動距離が減る可能性がある
  • 最短距離で動かす
    • 必ずしもゴミの位置に手を持っていく必要はないので、もし2個先に直線的に動かしても(中点を経由しても)拾えるなら、移動距離が減る可能性がある

スキャンベース

  • B問題について、「左手を平面の左端、右手を平面の右端に沿って下に動かす」というような動きを考えると、上のゴミから順番に回収することができる
  • このとき、移動距離の合計がかなり小さくできるため、B問題で1G点を超えることができる
  • これを応用して、点群を囲む最小の長方形(斜めも許す)で動かすなどするとかなり移動距離を抑えることができる模様
  • また、A問題にも応用して、上下の動き以外に横の動きもしてスキャンするように動かすアプローチもかなり強かった模様
  • さらに平行ではなく、片手を動かすアプローチも(偏角ソートベースに近い?)
  • 左手と右手で逆方向に動かす、みたいなのが有効なケースも作れた模様

偏角ソートベース

その他

2名以上が参加している所属機関一覧

出展企業紹介

お絵かき

解説

(発言を見つけられた方のみ)