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

,

C,Dで忙しくて開けなかった問題。EなのにC,Dより簡単だった。

E. Hexagons

解法

原点を中心とする同心の六角形上をぐるぐる回る。 まず何周目かを二分探索し、どの辺の上にいるか、その辺の上でどの位置にいるかを求めれば、座標が計算できる。

実装

#!/usr/bin/env python3
def binsearch(p, l, r): # (l,r], return the smallest n which p holds
    while l+1 != r:
        m = (l + r) // 2
        if p(m):
            r = m
        else:
            l = m
    return r
n = int(input())
if n == 0:
    print(0, 0)
else:
    i = binsearch(lambda i: n <= 3*i*(i+1), 0, 10**18)
    acc = 3*(i-1)*i
    j = binsearch(lambda j: n <= acc + i*(j+1), -1, 6)
    k = n - acc - i*j - 1
    dy = [ 0, 2,  2,  0, -2, -2 ]
    dx = [ 2, 1, -1, -2, -1,  1 ]
    y = dy[(j+1)%6] + dy[j]*(i-1) + dy[(j+2)%6]*k
    x = dx[(j+1)%6] + dx[j]*(i-1) + dx[(j+2)%6]*k
    print(x, y)