##提出コード
| Question | Code |
|---|---|
| A問題 | ■ |
| B問題 | ■ |
| C問題 | ■ |
| D問題 | ■ |
| E問題 | ■ |
| F問題 | ■ |
#問題ごとの略解
## A問題 (100pts, diff: 6) Determinant
$2$ 行 $2$ 列の行列式の値は問題文に
$$\operatorname{det} \begin{bmatrix} a & b \\ c & d \end{bmatrix}=ad-bc$$
と書かれているので, その式のまま実装すればよい.
## B問題 (200pts, diff: 20) Quizzes
そのままシミュレーションすればよい. ただし, 得点が $0$ のときに不正解だった場合は点数が減らないことに注意せよ.
## C問題 (300pts, diff: 782) Super Ryuma
コマの移動に関する問題なので, 重要なのはスタートとゴールの座標そのものではなく, 2つの座標の差分である. よって, $v_r:=r_2-r_1, v_c=c_2-c_1$ として, $(0,0)$ から $(v_r, v_c)$ への移動としてもよい.
ここで, 以下の重大な事実がある.
どんなマスでも3手以下で移動可能である.
$(0,0)$ から $(x,y)$ への移動を考える.
- $x+y$ が偶数のとき: 最初の移動で $m=\frac{x+y}{2}$ とすると, 仮定から, $m$ は整数である. このとき, 1手目で $(0,0) \to (m,m)$ という移動をする. そして, $m+m=x+y$ なので, 2手目に $(m,m) \to (x,y)$ という移動が可能である. よって, $2$ 手で移動可能である.
- $x+y$ が奇数のとき: $x+(y-1)$ は偶数なので, 上での証明から $(0,0) \to (x,y-1)$ という移動は $2$ 手でできる. よって, $|x-x|+|y-(y-1)|=1 \leq 3$ なので, $(x,y-1) \to (x,y)$ という移動ができ, 合わせて $3$ 手で到達できた.
よって, どんな $(x,y)$ でも $3$ 手以内に到達可能なので, 答えは $0,1,2,3$ のいずれかになることがわかる.
ここから, 答えが $0,1,2,3$ になるそれぞれの場合を考える.
- 答えが $0$ 以下になるのは動かない場合である. よって, $v_r=v_c=0$ のときは $0$ である.
- 答えが $1$ 以下になるのは超竜馬が動ける範囲そのままである. 今, $r_1=c_1=0$ として考えているので, 1手で移動可能なのは,
$$v_r+v_c=0, \quad v_r-v_c=0, \quad |v_r|+|v_c| \leq 3$$
であるときであり, この場合に限る. - 答えが $2$ 以下になる場合について, それぞれの移動の方法で場合分けをする.
- 斜め移動 $2$ 回について, 同じ方向の斜め移動はまとめて $1$ 回でできることを考えると, (右上方向への移動) $\to$ (右下方向への移動) のみを考えれば良い. この移動については上で述べた証明を流用することによって, $v_r+v_c$ が偶数のとき, またその時に限り可能である.
- ブロック移動 $2$ 回について, 1回の移動でマンハッタン距離 $3$ 以下のマスに移動できるので, $2$ 回以下の場合はマンハッタン距離が $6$ 以下の場合は移動可能で, そうでないときは不可能である.
- 斜め移動とブロック移動 $1$ 回ずつの場合について, 移動は可換なので, (ブロック) $\to$ (斜め) としてもよい. 斜め移動の方向でさらに場合分けする.
- 斜め移動の方向が右上方向のとき: 右上方向の斜め移動について, 座標の差を保つ. 最初のブロック移動では座標の差は $-3$ 以上 $3$ 以下にすることができるので, この移動では $-3 \leq v_r-v_c \leq 3$ となる任意のマス $(v_r, v_c)$ に移動できる.
- 斜め移動の方向が右下方向のとき: 右下方向の斜め移動について, 座標の和を保つ. 最初のブロック移動では座標の差は $-3$ 以上 $3$ 以下にすることができるので, この移動では $-3 \leq v_r+v_c \leq 3$ となる任意のマス $(v_r, v_c)$ に移動できる.
- 答えが $3$ 以下になる場合について, どんなマスでも上で述べた事実から, 答えは $3$ 以下である.
これらの考察から, 上から順に条件を満たすかどうかを判定し, 初めて条件を満たしたときの移動回数が答えである.
## D問題 (400pts, diff: 1276) increment of coins
$(a,b,c) \neq (0,0,0)$ に対して, $X(a,b,c)$ で金貨 $a$ 枚, 銀貨 $b$ 枚, 銅貨 $c$ 枚の状態から操作を終了するまでにかかる操作の回数の期待値とする. まず, $\max (a,b,c) \geq 100$ ならば $X(a,b,c)=0$ である. 次に, $\max (a,b,c) < 100$ とする. このとき, 金貨, 銀貨, 銅貨を引く確率はそれぞれ $\frac{a}{a+b+c}, \frac{b}{a+b+c}, \frac{c}{a+b+c}$ であり, その後は $(a+1,b,c), (a,b+1,c), (a,b,c+1)$ という状態になることから,
$$X(a,b,c)=\frac{a}{a+b+c}X(a+1,b,c)+\frac{b}{a+b+c} X(a,b+1,c)+\frac{c}{a+b+c} X(a,b,c+1)+1$$
という関係式が成り立ち, $a+b+c$ が大きい順に求めることにより, $X(A,B,C)$ が答えになる. 計算量は, $M=100$ とすると, $O(M^3)$ である.
## E問題 (500pts, diff: 1418) Third Avenue
愚直にBFSで実装すると, 全てのテレポータが同じであるときに計算量が $\Theta ((HW)^2)$ になり, 実行時間制限に間に合わない. しかし, 以下の事実に気づくと計算量が $O(HW)$ になり, 間に合う.
最短時間で到達できる移動の方法は同じテレポータは2度以上使わない.
もし, 同じテレポータを2度使ったとする. 例えば, テレポータ $\alpha$ に関して, $\dots \to x \xrightarrow{{\rm Teleport}~\alpha} y \to \dots \to z \xrightarrow{{\rm Teleport}~\alpha} w \to \dots$ という移動だったとすると, $\dots \to x \xrightarrow{{\rm Teleport}~\alpha} w \to \dots$ という移動は $x$ から $w$ の移動で変わらず, 真に所要時間が短くなっている. よって, 同じテレポータを2度以上使うと最短になることはない.
この事実から, 各テレポータは高々1度だけしか使わないので, BFSにおいてテレポータを用いた移動を行った後, そのテレポータを全てクローズすることにより, 無駄な探索をせずに求めることができる.
## F問題 (600pts, diff: 1423) Programming Contest
愚直に求めると, 計算量が $O(2^N)$ となり, 間に合わない. そこで, 半分全列挙というテクニックを用いて求める.
- $A$ を前半の $\left \lfloor \frac{N}{2} \right \rfloor$ 項と後半の $\left \lceil \frac{N}{2} \right \rceil$ 項に分け, それぞれ $U,V$ とする.
- $U$ における可能な $2^{\lfloor \frac{N}{2} \rfloor}$ 通りの部分和を列挙して, この結果を列 $X$ とする. $V$ においても同様にして, 結果を列 $Y$ とする.
- $X$ の各元 $x$ に対して, $x \leq T$ であるとき, $x+y \leq T$ を満たす最大の $Y$ の元 $y$ を二分探索で求める.
このようにすると計算量 $O(\frac{N}{2}2^{N/2})=O(N2^{N/2})$ で求めることができ, $N \leq 40$ という制約下では高速である.