CodeCraftの問題を見てみる - にゃあさんの戯言日記

とりあえずkinaba師おすすめの3問を少し考えてみた。

Problem3: とりあえず2次元のsegment treeっぽいものを作れば O( (クエリー数)log(座標範囲) ) くらいで行けるかな…と思うけど、時間に間に合うかなあ...
Problem6: 縦軸横軸は独立なので分解すると、1ターンで最大k回まで取れるNimに帰着。有名な判定法を変形して、2進数にコーディングした上で $\mathbb{Z}_{k+1}$ 上の加算を使ってやれば良いと思う。自然な変形問題だからどこかに説明とか証明が転がってそう。
Problem9: 時間制限6秒っていうのが微妙。クエリを全部持ってO(K)を一回走らせるのは間に合わない…のかなあ。logくらいの加速が出来るにしては時間長すぎだしよくわからない。