pekempeyのブログ

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

Codeforces Round #338 (Div. 2) E. Hexagons

問題文

codeforces.com

解法

移動方向に番号を割り振る。

f:id:pekempey:20160109164209p:plain

移動方向を順番に並べてみる。

0,2,3,4,5,0,0,1,2,2,3,3,4,4,5,5,0,0,0,1,1,2,2,2,3,3,3,4,4,4,5,5,5,...

規則性のありそうな部分をグルーピングする。

0,2,3,4,5
0,0,1,2,2,3,3,4,4,5,5
0,0,0,1,1,2,2,2,3,3,3,4,4,4,5,5,5

i 番目 (0-indexed) のグループは、1 が i 回で、1 以外が i+1 回現れるため、i 番目のグループの要素数は 6i+5 である。このことから、i 番目のグループの先頭は全体で見て 3i(i+1)-i 番目にあることが分かる。 これを使うと n 回目の操作が何番目のグループなのかを二分探索で求められる。

グループを一個シミュレートする毎に 4 の方向に 1 つずれることを利用すると、n を含むグループまでを一気にシミュレートできる。 残った部分は適当にシミュレートすればいい。

Codeforces Round #338 (Div. 2) E. Hexagons

E にしては妙に簡単。