Codechef June Challenge 2018 参加日記
155位/438人(Div1)だった。もう1問くらい解けそうだったが、期間中にゲームを買ってしまったのが原因でフェードアウト敗退した。
三次元の座標上に、２つの点PとQ、および球が与えられる。Pは動かないが、Qは一定の速度で動いてゆく。時間tの点Qの位置は次の式で表される(dはベクトル、Q(0)はQの初期位置)。
Q(t) = Q(0) + d*t
はじめ、点QはPから見えないことが保証されている。このとき、点QからPが見えるようになる最小の時間を求めよ。なお、PやQが球に重なることはない。
初期状態は点Qが見えなくて、ある時間tから点Pが見えるようになるのだから、二分探索を使えば求められる。「点Qから点Pが見えるかどうか」は、Q->Pベクトルが球に交差する、と言い換えればよい。あとは初等幾何の問題。
https://www.codechef.com/viewsolution/18726175
n行m列のグリッドが与えれ、各セルにはタイプa[i,j]の花が咲いている。最大2種類の花を選び、その花のみ咲いている連続するセルを選択するとき、その最大面積を求めよ。上下左右のいずれかでセルが接するとき、その2セルは連続しているとする。
1 <= n, m <= 2000
1 <= a[i, j] <= 4x10^6
本番はむりやり通したが嘘解法。Editorialの貪欲解は、
１）あるセルと、そのセルの右または下のセルを選ぶ
２）その2つのセルにある色のみを選んでBFSしていく
を、すべてのセルに対して行っている。ただし、同じ集合が重複しないように、「現在のセルからある方向に遷移したことがあるか」をもって、もしあるならば無視するようにしている。これは自分の解とほぼ同じなのだが、重複を無視する部分が位置+色組み合わせでHashSetに入れて判断していたため、TLEになってしまっていた。方向だけなら配列で持てるので間に合う。
https://s3.amazonaws.com/codechef_shared/download/Solutions/JUNE18/editorialist/TWOFL.cpp
(Editorial解)
