3匹の猫

みみねこの競プロ精進メモ

AtCoder Beginner Contest 197(Sponsored by Panasonic)参加記(~E問題)

D問題みたいな数学問題もっと出してもいいんですよ
f:id:mmnkblog:20210328022948p:plain

A - Rotate

文字列で受け取ってもいいが、文字変数を3つ用意して入力順と出力順を入れ替えた方がシンプルに書ける。

計算量は、O(1)

B - Visibility

むずくない?

マス(X, Y)から始めて、上下左右の4方向に向かって探索する。もし探索途中に#が出現したら、それより奥のマスは障害物で遮られて見えないので探索をやめる。この個数をカウントしたものが答え。

計算量は、入力がボトルネックO(HW)。探索自体はO(H+W)である。

C - ORXOR

「長さNの数列を1つ以上の空でない連続した区間に分ける」、つまり、各要素の間に区切りを入れるか・入れないかを独立に選択する方法は全部で2^{N-1}通り。制約よりNは最大でも20なので、全パターンを試しても間に合う。こういう、「選ぶか」「選ばないか」の2択をいくつか選択するような状況の全探索にはbitを活用する。(bit全探索という)
C++では、ORの計算はa|b、XORの計算はa^bと書くことで簡単に計算できる。

計算量は、O(N2^N)

D - Opposite

正多角形の座標のうち、一番離れている2点の座標が与えられる。Nは偶数なので、この正多角形の中心の座標がわかる。
また、正多角形の隣り合う頂点は、正多角形の中心から見てちょうど\dfrac{2\pi}{N}だけ回転している。2次元平面状の座標を回転させるには、回転行列を用いるとよい。具体的には、

\begin{pmatrix}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{pmatrix}
\begin{pmatrix}
x\\
y
\end{pmatrix}=
\begin{pmatrix}
x\cos \theta -y\sin \theta \\
x\sin \theta + y\cos \theta
\end{pmatrix}
を用いればよい。ググると出てくる。
答えが小数になるため、誤差に注意。

計算量は、O(1)

E - Traveler

iのボールを回収するとき、現在の座標をxとすると、
・負の方向に進んでから正の方向に進む
・正の方向に進んでから負の方向に進む
という2通りの行動以外は最適な行動ではない。(引き返した分の時間が損であり、引き返さなくてもすべてのボールを回収できる行動が存在するため。)

つまり各色のボール群を回収する際は上記の2通りの行動のうちどちらかを選んで行動する。この時点で全通りを試すとO(2^N)の計算量となり、実行時間制限に間に合わない。
ここで、ある色までのボールを回収し終えた時点での座標は、その色のボール群のうち一番座標が小さいボールがあった位置か一番座標が大きいボールがあった位置かのどちらかである。それまでの行動を考慮しなくても、前の段階での終了時の座標を全通り試すだけで最適解が求まる。これを、動的計画法(DP)という。

よって、ひとつ前の色の座標の候補(2通り)と、ボールを回収するときの行動パターン(2通り)の全パターンを試して最適なものを選択していけばよい。

計算量は、O(N)


感想

EのDPは比較的簡単な方の部類だと思うのだが、コンテスト中は嘘の貪欲を書いていた。強くなりたい…!