AtCoder Beginner Contest 184参加記（全問題）

100-200-300-0-0(1)-600(1)で1ペナ4完1200点。

A - Determinant

行列は丸括弧で与えないとダメなんじゃないの？と思いつつ解いた。ちなみに丸括弧にはいろいろな意味があるので、紛らわしさをなくすために行列は角括弧で表すことがあるらしい。ためになったね～（もう中学生）

問題文に書かれている通り、入力値から行列式の値を計算して出力する。いわゆる「問題文に答えが書いてある」のもっとも基礎的なパターンで、なんと一番早いACは13秒である。おそろしや…

計算量は、 $O(1)$ 。

B - Quizzes

それぞれのクイズが終了した時点での点数がいくつなのかを計算すればよい。持ち点が $0$ 点のときにxが来ても $0$ 点のままで、この辺りに躓くことなく実装できるかがカギとなる。

計算量は、 $O(N)$ 。

C - Super Ryuma

ぱっと見、どこから手を付けていいのか迷ってしまった。この駒の移動方法は、

「対角線上のマスへ移動」
「マンハッタン距離が3以下のマスへ移動」

の2種類の移動が組み合わさっている。ここで、「対角線上のマスへ移動」は距離に制限がないので、この移動を2回繰り返せば、移動したいマスのすぐ近くまでは絶対にいけることがわかる。この辺をしっかり議論していく。

まず、スタート地点とゴール地点が重なっている可能性がある。この場合は $0$ 手で移動できる。

次に、 $1$ 手で移動できる場合を考える。これは、問題文で示された駒の動ける範囲にゴール地点が重なっている場合のみであり、この条件を満たすかは問題文に示されたとおりの式を満たすかどうかでわかる。

よって、これら以外のマスに行くためには最低 $2$ 手必要である。ここで、先ほどの2種類の移動方法の選び方により、 $2$ 手移動する方法は以下の3通り考えられる。

「対角線上のマスへ移動」してから「対角線上のマスへ移動」する
「対角線上のマスへ移動」してから「マンハッタン距離が3以下のマスへ移動」する
「マンハッタン距離が3以下のマスへ移動」してから「マンハッタン距離が3以下のマスへ移動」する

1番の移動方法では、以下に示すように市松模様の同じ色のマスへしか移動できない。逆に、市松模様の同じ色のマス同士なら、必ず2手で移動できる。同じ色のマスであるための条件は、 $x$ 座標と $y$ 座標の和の偶奇が一致していることである。
違う色同士のマスへ移動するには、移動したいマスの1つ隣のマスを選んで2手かけて移動し、3手目に1マス隣に移動することで移動可能である。このことから、最大でも3手以内に移動可能であることがわかった。つまり、これ以外での移動方法に関して議論するとき、2手で移動できないことがわかれば十分である（2手で移動できないならこの方法で3手かけて移動するのが最短だから）。

f:id:mmnkblog:20201123002942p:plain — 1番目の移動の例：(3, 0)→(0, 9)

2番の移動方法について考える。この場合、ゴール地点とのマンハッタン距離が3以下であるようなマスへ1手で移動できるか？ということを考えればよい。斜めに移動するとき、ゴール地点とのマンハッタン距離が最短となるように移動するには、例えばゴール地点の $x$ 座標と移動先の $x$ 座標が等しくなるように移動すればよい。（証明略）
あとは、移動先のマスとゴール地点のマスのマンハッタン距離が3以下かどうか判定すれば移動できるかがわかる。

f:id:mmnkblog:20201123002946p:plain — 2番目の移動の例：(0, 0)→(5, 8)

3番の移動方法についてもしっかり考えないといけない。この移動方法は、「マンハッタン距離が6以下のマスへ移動」することと同じである。よって、スタート地点とゴール地点のマンハッタン距離が4以上6以下なら、2手で移動できる。

f:id:mmnkblog:20201123003517p:plain — 3番目の移動の例：(0, 4)→(5, 4)

ここまでの条件をすべて確認して、ようやくACが得られる。しかし、どうやら3番の移動方法を考慮していない解法でもACが得られてしまうようだ。このテストケースが抜けているのもどうかと思うが、嘘解法で通してしまった人はせめてこの理屈だけでも理解するようにすべきだと思う。

計算量は、 $O(1)$ 。

D - increment of coins

解けなかった。とりあえず、

$dp[i][j][k] =$ 金貨が $i$ 枚、銀貨が $j$ 枚、銅貨が $k$ 枚ある状態へ遷移する確率

というDPを思いつく。制約からも $O(ABC)$ が通るのであってるかなーと思ったが、確率を浮動小数点数型で保存すると誤差がひどすぎて正しい答えが得られず、かといって遷移する通り数を保存するとオーバーフローしてしまう。Pythonで書こうか迷って順位表を見たらE問題よりF問題の方が解かれていて、捨てた。

公式の解説を見る限りでは数値誤差でひっかけるつもりはなさそうなので、単純に考察が間違っていただけかもしれない。たぶんそうだと思う。順位表を見て正解だった。

E - Third Avenue

解けなかった。F問題を解いた後に問題を読んだが、言い訳をすると時間が足りなかった。
問題自体はよくあるグリッド上の迷路の最短距離を求めるもので、テレポーターによる瞬間移動をどう実装するかが肝である。BFSをベースに実装し、テレポーターがあるマスを事前にメモしておくことですぐテレポート先を参照できるようにした。また、同じ種類のテレポーターを2回以上使う必要はないので、1度使った同じ種類のテレポーターは使えないようにした。
これであっていると思って提出したのだが、2ケースだけWAが出ている。原因はわからない。

F - Programming Contest

これはいわゆる「部分和問題」というやつで、集合の中からいくつか整数を取ってきたときの和に関する問題をまとめてこう呼ぶ。解法もいろいろあって、制約から決めることが多い（諸説あり）。

全探索して解いたときの計算量は、 $N$ 個ある整数それぞれに対して、「取る」か「取らない」かを決めていくので、選び方は $2^N$ 通り。このうち $T$ 以下で最大のものを探すだけなので、計算量は $O(2^N)$ となる。今回の制約の最大値 $N=40$ を代入して概算すると、 $2^{40} \fallingdotseq 10^{12}$ となるため実行時間制限に間に合わない。

ここで、半分全列挙と呼ばれるテクを使うことで、計算量を $O(N2^{\frac{N}{2}})$ にすることができる。詳しいやり方はググるべし。
ざっくり方針を述べる。40個の整数を20個ずつに分けてそれぞれの選び方をすべて試す。前半の集合から得られた部分和を $A$ として、後半の集合の部分和の中から $T-A$ 以下のうち最大のものを二分探索で探す。これらの最大値が答えとなる。