naoya_t@hatenablog

いわゆるチラシノウラであります

SRM623 DIV1 Medium<450> : CatchTheBeat

DIV1 Medium Random Challenge第5回。

DP, priority_queueで大きい順に見ていく(削った分は補充)

最悪ケース(6を50万にしたやつ)でTLEというか全く帰ってこないし ”Error on copying blob data” で submit&test できない それはさておき、O(N2 logN) になってないかこれ

投稿できない原因を探るべく、先にEasy<300> UniformBoard を解いてみる

可能な長方形を (NC2)x(NC2) 通り <= 1902=36100通りだし試す。その長方形の内と外のapple, pear, empty-cell をそれぞれ数えて、K手以内の移動で可能かを調べる。 最大20行のapple/pear/empty-cell数のカウント部分、ビット演算でオーダーをO(n2)からO(n)に落とした 内の空セルに外からappleを持ってくる、外の空セルに内のpearを追い出す、pearを追い出して空いたセルに残りのappleを持ってくる、的なコードを書いた→WA

ああ、1つずつ汲み出さなくちゃいけないやつが解けないわ(そりゃそうか) K手までの範囲内でセル移動の繰り返し。K=1000まで →AC

// editorial読んだ。 (e + 2p ≦ K) って何だ pearを追い出すのに +p 手 できる空間が (e+p) 、ここにappleを持ってくるのに + (e+p) 手
それで合計 e+2p か

(0,0) から (r,c) までの(2次元の)範囲で数えておいて(DPっぽい)、 それを4つ(+–+)使って求める方法。 O(1) か。


改めてMedium。今回はsubmitできた、けどやっぱりTLE

Problem: 450
Test Case: 113
Succeeded: No
Execution Time: 0 ms
Peak memory used: 0.000MB
Args:
{244373, 178204199, 594085, 160755914, 93068480, 166982, 13616, 355018071, 917519, 205776483}

Expected:
35

Received:
The code execution time exceeded the 2.000 second time limit.

Answer checking result:
null

あ、はい ここでギブアップしてEditorialを読む https://apps.topcoder.com/wiki/display/tc/SRM+623

ギザギザな経路になるが 45度傾けると、必ず上か右に行くように見える、と

LIS…

a slight variation of the Longest Increasing Subsequence (LIS) problem. とか LISはO(NlogN) で解けるから大丈夫、と

(x-y) の数列を作ってLIS?… 目から鱗

→AC (5/26 12:14)

今回学んだこと

  • (Easy) 二次元平面上の個数カウントは累積で持って(+–+)すればO(1)
  • (Med) 斜め45度で見てみる
  • LIS (longest increasing subsequence)。
ある桁の前のprefixになりうる最大長を二分探索で求める、ある長さを最短で実現できる位置を配列で持って更新しながら、で O(N logN)