AtCoder Beginner Contest 197(Sponsored by Panasonic)参加記(~E問題)
D問題みたいな数学問題もっと出してもいいんですよ
B - Visibility
むずくない?
マスから始めて、上下左右の4方向に向かって探索する。もし探索途中に#
が出現したら、それより奥のマスは障害物で遮られて見えないので探索をやめる。この個数をカウントしたものが答え。
計算量は、入力がボトルネックで。探索自体はである。
C - ORXOR
「長さの数列を1つ以上の空でない連続した区間に分ける」、つまり、各要素の間に区切りを入れるか・入れないかを独立に選択する方法は全部で通り。制約よりは最大でもなので、全パターンを試しても間に合う。こういう、「選ぶか」「選ばないか」の2択をいくつか選択するような状況の全探索にはbitを活用する。(bit全探索という)
C++では、ORの計算はa|b
、XORの計算はa^b
と書くことで簡単に計算できる。
計算量は、。
D - Opposite
正多角形の座標のうち、一番離れている2点の座標が与えられる。は偶数なので、この正多角形の中心の座標がわかる。
また、正多角形の隣り合う頂点は、正多角形の中心から見てちょうどだけ回転している。2次元平面状の座標を回転させるには、回転行列を用いるとよい。具体的には、
を用いればよい。ググると出てくる。
答えが小数になるため、誤差に注意。
計算量は、。
E - Traveler
色のボールを回収するとき、現在の座標をとすると、
・負の方向に進んでから正の方向に進む
・正の方向に進んでから負の方向に進む
という2通りの行動以外は最適な行動ではない。(引き返した分の時間が損であり、引き返さなくてもすべてのボールを回収できる行動が存在するため。)
つまり各色のボール群を回収する際は上記の2通りの行動のうちどちらかを選んで行動する。この時点で全通りを試すとの計算量となり、実行時間制限に間に合わない。
ここで、ある色までのボールを回収し終えた時点での座標は、その色のボール群のうち一番座標が小さいボールがあった位置か一番座標が大きいボールがあった位置かのどちらかである。それまでの行動を考慮しなくても、前の段階での終了時の座標を全通り試すだけで最適解が求まる。これを、動的計画法(DP)という。
よって、ひとつ前の色の座標の候補(2通り)と、ボールを回収するときの行動パターン(2通り)の全パターンを試して最適なものを選択していけばよい。
計算量は、。
感想
EのDPは比較的簡単な方の部類だと思うのだが、コンテスト中は嘘の貪欲を書いていた。強くなりたい…!