はじめに
おはようございます。本記事では、私がJOI サッカー の解説を読んでいて詰まった部分の行間を埋めることを目指します。
何に詰まったか
解説スライド41Pにある
▶ シュートされたあと誰かに拾われるわけですが、この時、同じ選手が二回ボールを蹴らないという考察から、(初期位置が) 一番近くの人が拾えば良いことが分かります。
という記述の正当性を疑問に思いました。より具体的には、
- それが最適値をだすのか
- 対応する操作列が存在するのか
の $2$ 点が気になりました。よって、これを納得する事を目標にします。
記法
「$(i, j)$ にボールがあり、かつ誰もボールを持っていない」状態を $(0, i, j)$ と置きます。
「$(i, j)$ にボールがあり、かつボールを持っている人が居る」状態を $(1, i, j)$ と置きます。
また、状態 $(t, i, j)$ になる操作列のうち、コストが最小のもののそのコストを $d(t, i, j)$ と置きます。
前提
次の命題を認めます。
命題:操作列を任意に取る。この時、次の条件を満たす操作列であって、取った操作列以下のコストである物が存在する。
$\forall i,$ 人 $i$ がボールを $1$ 回以上持ち、かつ手放したならば人 $i$ は以降ボールを持たない
よって、同じ人は $1$ 回までしかボールを持たないと制約をかけても最適解が求まります。なので今後はそうします。
また、次も認めます。
ということは、選手 1 の初期位置からはじめて -> ドリブル
をする -> シュートをする -> ある選手がボールの位置に移動
する -> ドリブルをする -> シュートをする -> ある選手が
ボールの位置に移動する -> ... -> ドリブルをする -> (シュー
トをする) -> ボールが選手 N の初期位置に到達する という
流れのみを考えればよい。
つまり、人はボールを持つ直前まで一歳動かないと制約をつけます。
命題
早速、
▶ シュートされたあと誰かに拾われるわけですが、この時、同じ選手が二回ボールを蹴らないという考察から、(初期位置が) 一番近くの人が拾えば良いことが分かります。
を証明したいのですが、そもそも"良い"という主張は命題ではなく、今回証明の対象とするにはやや曖昧で取り扱いに苦労します。よって、次の命題を示すことにします。
命題: 任意の $i, j$ について、 $(i, j)$ に初期位置が一番近い人を $k$, 人 $k$ から $(i, j)$ までのマンハッタン距離を $d$ と置くと、次が成立する。
$$ d(1, i, j) \le d(0, i, j) + d$$
証明
$d(0, i, j)$ を実現する操作列を任意に $1$ つとる。
1. 人 $k$ が $(0, i, j)$ に至るまでにボールを持たなかった場合
取った操作列に人 $k$ の動きを加えた操作列のコストが $d + d(0, i, j)$ である。
2. 人 $k$ が $(0, i, j)$ に至るまでにボールを持っていた場合
注意: $(0, i, j)$ の時点で人 $k$ がどこにいるかは不定である。
構成的な証明をする。
黒で人 $k$ を表す。
を元の操作列とする時、
の様に改変した操作列のコストは $d(0, i, j) + d$ 以下で、状態が $(1, i, j)$ である。
より正確には、
- 人 $k$ のボールを持つまでの移動を直前の人のドリブルで置き換える(コスト不変。ボールの位置は変化する)。
- 人 $k$ から起こる一連の操作を全て捨てる(コスト減)
- 人 $k$ から $(i, j)$ に行く(コスト $+d$ )
よって、命題は示された。
最短経路との対応
命題の不等式が成立するからと言って最短経路と答えが対応することは自明ではないと思います。$d(1, i, j) = - \infty$ でも一見すると良いわけで、 $d(0, ?, ?)$ と $d(1, ?, ?)$ の関係がまだ不明瞭です。でも、ここまでで疲れたので考えません。ごめんなさい。言うもおろかってやつです。
真面目に考えると、命題の系として次が直ちに得られます。
系(パス -> 操作列の対応): 解説の通りに辺を貼ったグラフにおいて、$(1, y_{n-1}, x_{n-1})$ への最短経路を取る。このパス長が $d$ の時、コスト $d$ 以下の操作列が存在する。
補足: 牛ゲーで、「最短経路が上界に一致」するのと多分同じだと思います。命題の制約が得られた時、それをグラフに起こすと上界が最短経路として得られます。
よって、
命題(操作列 -> パスの対応): 最適解のコスト以下のパス長をもつパスが存在する
補足: 得られた上界が真の値と一致している事を言えば良い訳です。
を言えば良いです。
最適解の状態に対応する様に頂点を遷移していきます。この時、ボールを拾う操作以外は素直な対応が取れます。ボールを拾う操作について、最適解は一番近いやつには拾わせないかもしれませんが、コスト的には一番近いやつに拾わせたとして計算した方が小さいです。以上より成立します。
お気持ち
問題 $1$ つ $1$ つにこういうことを考えていると時間がものすごく解けます。証明は付属していた方が嬉しいです。"良い"という言葉はカジュアルなので、読み手が十分に意図を理解していないと辛いです。
特に今回構成的かつ過去を改変するちょっと変わった証明をしたわけですが、もっとクリアな議論で示せたり、他に活かせそうなイカした議論が存在すると悲しいです。
長い春休み
なんでこんな事を