pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #353 (Div. 2) B. Restoring Painting

http://codeforces.com/contest/675/problem/B

問題

3x3 のグリッドがあり、a,b,c,d の値が分かっている。

?a?
b?c
?d?

また、? に入る値は 1..n であることも分かっている。

どの連続した 2x2 のグリッドを切り出しても総和が等しくなるような ? の当てはめ方は何通りあるか。

  • 1≦n≦105

解法

真ん中の値は 1..n のどれでもいいので気にしない。

左上の値を一つ決めると他の値も全部わかる。ということで、左上の値を 1..n まで全部試せばいい。

Codeforces Round #353 (Div. 2) B. Restoring Painti ...

パズルっぽくて良い問題。真ん中がどれでもいいことに気がつけば後は簡単。