読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

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

Facebook Hacker Cup 2017 Qualification Round

皆さま明けましておめでとうございます。

1/7から開催されていたFacebook Hacker Cupの予選ラウンドに参加(通過)したメモです。
今回は全てPythonで書いてみました。


全部解いたけど、3問のうち1問でもACなら通過らしいです。
Facebookのお友達勢は全員通過の模様)

Progress Pie (25点)

Progress Pie | Facebook Hacker Cup 2017 Qualification Round

近傍が同一色であると保証されている(=ボーダーライン上の点は来ない)という制約があるので割と楽。

# a1.py
import math


def is_black(P, X, Y):
    if P == 0:
        return False

    p_theta = math.pi * 2 * P / 100

    dx, dy = Y-50, X-50
    point_r, point_theta = math.hypot(dx, dy), math.atan2(dy, dx)
    if point_r > 50:
        return False

    if point_theta < 0:
        point_theta += math.pi * 2

    return point_theta <= p_theta


def main():
    T = int(raw_input())
    assert 1 <= T <= 1000

    for t in range(1, 1+T):
        assert 1 <= t <= T

        P, X, Y = map(int, raw_input().split(' '))
        assert 0 <= P <= 100
        assert 0 <= X <= 100
        assert 0 <= Y <= 100

        print 'Case #%d: %s' % (t, 'black' if is_black(P, X, Y) else 'white')


if __name__ == '__main__':
    main()
テスト。

いちおう全ての組み合わせ(0 ≦ P, X, Y ≦ 100)について試した上でsubmitした。

#!/usr/bin/env nosetests -s -v -d
# test_a1.py
from a1 import is_black

import math


def _test(P, whites=None, blacks=None):
    if whites:
        for white in whites:
            # print white
            X, Y = map(int, white.split(' '))
            assert is_black(P, X, Y) == False
    if blacks:
        for black in blacks:
            # print black
            X, Y = map(int, black.split(' '))
            assert is_black(P, X, Y) == True


def test_always():
    for P in range(101):
        # four corners are always white
        _test(P, whites=('0 0', '100 0', '100 100', '0 100'))
        # outside
        _test(P, whites=('51 100', '86 86', '100 51', '86 14', '51 0', '14 14', '0 51', '14 86'))

        # center, center+e must be white only when P==0
        if P == 0:
            _test(0, whites=('50 50', ))
            _test(0, whites=('50 51', ))
        else:
            _test(P, blacks=('50 50', ))
            _test(P, blacks=('50 51', ))


def test_p0():
    _test(0, whites=('50 55', '55 55', '55 50', '55 45', '50 45', '45 45', '45 50', '45 55'))
    _test(0, whites=('50 99', '85 85', '99 50', '85 15', '50 1', '15 15', '1 50', '15 85'))


def test_p50():
    _test(50, blacks=('50 55', '55 55', '55 50', '55 45'),  # '50 45',
              whites=('45 45', '45 50', '45 55'))
    _test(50, blacks=('50 99', '85 85', '99 50', '85 15'),  # '50 1',
              whites=('15 15', '1 50', '15 85'))

def test_p100():
    _test(100, blacks=('50 55', '55 55', '55 50', '55 45', '50 45', '45 45', '45 50', '45 55'))
    _test(100, blacks=('50 99', '85 85', '99 50', '85 15', '50 1', '15 15', '1 50', '15 85'))


def test_everything():
    for X in range(101):
        for Y in range(101):
            _theta = math.atan2(Y-50, X-50)  # -pi .. pi
            point_theta = math.pi/2 - _theta  # -pi/2 .. 3pi/2
            if point_theta < 0:
                point_theta += math.pi * 2
            point_r = math.hypot(X-50, Y-50)

            assert 0 <= point_theta <= math.pi * 2
            assert 0 <= point_r < 71

            if point_r == 50:
                print 'this case (X=%d, Y=%d) is excluded' % (X, Y)
                continue

            for P in range(101):
                if point_r == 0:
                    assert X == 50 and Y == 50
                    if P != 100:
                        print 'this_case (X=%d, Y=%d, P=%d) is excluded' % (X, Y, P)
                        continue

                if P == 0:
                    expected = False
                elif point_r > 50:
                    expected = False
                else:
                    p_theta = math.pi * 2 * 0.01 * P
                    if point_theta == p_theta:
                        print 'this_case (X=%d, Y=%d, P=%d) is excluded' % (X, Y, P)
                        continue

                    expected = (point_theta < p_theta)

                actual = is_black(P, X, Y)
                assert actual == expected
【おまけ】他人様のコードを読んで

身につまされる。

--- a_orig/progress_pie_source.cc
+++ a/progress_pie_source.cc
@@ -30,6 +30,7 @@
     return "white";
 
   if (p >= 50) {
+    if (x >= 0) return "black";
     p -= 50;
     x *= -1;
     y *= -1;
@@ -40,9 +41,9 @@
   double t = atan2(x, y);
 
   if (t < 0.0)
-    t += M_PI;
+    t += M_PI*2;
 
-  assert(0.0 <= t && t < M_PI);
+  assert(0.0 <= t && t < M_PI*2);
 
   return t < theta ? "black" : "white";
 }

整数演算だと例えば12%が42°になる(43.2°になってほしい)。
具体的には (P, X, Y) = (12, 65, 66) で死ぬ。

--- p_orig/progress_pie_source.py
+++ p/progress_pie_source.py
@@ -9,7 +9,7 @@
 		print 'Case #%d: white' % t
 		return
 
-	p = math.radians(360 * p / 100)
+	p = math.radians(360. * p / 100)
 	q = math.atan2(x - 50, y - 50) 
 	if q < 0:
 		q = 2 * math.pi + q
【おまけ#2】

PIL(グラフィックライブラリ)で描画してピクセルの白黒を判定するってのもやってみたけどサンプルすら通らなかった。そもそも draw.pieslice() が角度に整数しか受け付けない。
f:id:n4_t:20170110145739p:plain f:id:n4_t:20170110145752p:plain f:id:n4_t:20170110145800p:plain f:id:n4_t:20170110145809p:plain f:id:n4_t:20170110145804p:plain

import math
from PIL import Image, ImageDraw

BLACK = 0
WHITE = 1

def is_black(P, X, Y):
    image = Image.new('1', (101, 101), color=WHITE)
    draw = ImageDraw.Draw(image)

    if P > 0:
        draw.pieslice([0,0,100,100], start=-90, end=-90+int(3.6*P), fill=BLACK, outline=BLACK)
    # image.show()
    return image.getpixel((X, 100 - Y)) == BLACK


def main():
    T = int(raw_input())
    for t in range(1, 1+T):
        P, X, Y = map(int, raw_input().split(' '))
        print 'Case #%d: %s' % (t, 'black' if is_black(P, X, Y) else 'white')


if __name__ == '__main__':
    main()

Lazy Loading (30点)

Lazy Loading | Facebook Hacker Cup 2017 Qualification Round

重いやつの下にいくつ(軽いやつを)隠せるか、というか
その荷物は、何個積んだ上になら置いてもよいか、というか
(こういうceilingの絡んだ割り算は苦手というか考えたくもないので下のコードの minh() みたいな事をしてる)

# b1.py

def minh(w):
    assert 1 <= w <= 100
    for h in xrange(1, 51):
        if h * w >= 50:
            return h
    assert False
    return 50


def solve(W):
    N = len(W)
    H = sorted(map(minh, W))
    head, tail = 0, N
    count = 0
    while head < tail:
        rem = tail - head + 1
        h = H[head]
        head += 1
        tail -= (h-1)
        if head <= tail:
            count += 1
    return count


def main():
    T = int(raw_input())
    assert 1 <= T <= 500

    for t in range(1, 1+T):
        N = int(raw_input())
        assert 1 <= N <= 100

        W = []
        for n in range(N):
            Wi = int(raw_input())
            1 <= Wi <= 100
            W.append(Wi)

        print 'Case #%d: %s' % (t, solve(W))


if __name__ == '__main__':
    main()
テスト。
#!/usr/bin/env nosetests -s -v -d
# test_b1.py
from b1 import solve

import random
import time

def generate_W(N):
    while True:
        W = [random.randint(1, 100) for i in range(N)]
        if sum(W) >= 50:
            return W


def test_speed():
    t0 = time.time()
    for t in range(500):
        N = 100
        W = generate_W(N)
        ans = solve(W)
        # print ans,
        assert 1 <= ans <= N
    t1 = time.time()
    assert t1 - t0 < 2


def test_various_n():
    for N in range(1, 101):
        W = generate_W(N)
        ans = solve(W)
        assert 1 <= ans <= N


def test_():
    assert solve([50]) == 1
    assert solve([50, 1]) == 1
    assert solve([50, 1, 1]) == 1

    assert solve([50, 50]) == 2
    assert solve([50, 50, 1]) == 2
    assert solve([50, 50, 1, 1]) == 2
    assert solve([50, 50]) == 2
    assert solve([50, 49]) == 1
    assert solve([50, 49, 1]) == 2
    assert solve([50, 49, 1, 1]) == 2

    assert solve([49, 49]) == 1
    assert solve([49, 1]) == 1
    assert solve([49, 1, 1]) == 1

    assert solve([25, 25]) == 1
    assert solve([25, 25, 1]) == 1
    assert solve([25, 25, 1, 1]) == 2
    assert solve([25, 24, 1]) == 1
    assert solve([25, 24, 1, 1]) == 1

    assert solve([10, 10, 10, 10, 10]) == 1
    assert solve([10, 10, 10, 10, 10, 10, 10, 10, 10]) == 1
    assert solve([10, 10, 10, 10, 10, 10, 10, 10, 10, 10]) == 2
    assert solve([10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10]) == 2
【おまけ】他人様のコードを読んで
--- ns_orig/lazy_loading_source.cc
+++ ns/lazy_loading_source.cc
@@ -68,7 +68,7 @@
 		int heavy = n-1;
 
 		int ans = 0;
-		while (light < heavy)
+		while (light <= heavy)
 		{
 			// さらに何個必要か
 			int m = ceil(50.0/x[heavy])-1;

Fighting the Zombie (45点)

Fighting the Zombie | Facebook Hacker Cup 2017 Qualification Round

Y面のサイコロ(1..Y)をX回振った合計の分布(に±Zしたもの)を見て、勝つ確率の一番高い物の確率を表示するだけ。
最近こういうのはさくっとre.match()書くようになってる。

# c1.py
import re


def parse_spell(spell):
    mo = re.match(r'^([1-9][0-9]*)d([1-9][0-9]*)(([-+][1-9][0-9]*)?)$', spell)
    assert mo is not None
    X, Y, Z = int(mo.group(1)), int(mo.group(2)), int(mo.group(3) or '0')
    return (X, Y, Z)


def ydie_xtimes(y, x):
    """roll a Y-sided die X times, and sum the rolls"""
    total = [[0] * (1 + x*y), None]
    total[0][0] = 1
    imax = 0
    for g in xrange(x):
        g0, g1 = g % 2, (g+1) % 2
        total[g1] = [0] * (1 + x*y)
        for i in xrange(1+imax):
            base = total[g0][i]
            for j in xrange(1, 1+y):
                total[g1][i+j] += base
        imax += y

    return y**x, total[x % 2]


def rates(x, y, z):
    y_x, ls = ydie_xtimes(y, x)
    L = 1 + y*x
    assert len(ls) == L
    R = {(i+z):1.0*ls[i]/y_x for i in range(L) if ls[i] > 0}
    return R


def spell_rates(spell):
    x, y, z = parse_spell(spell)
    R = rates(x, y, z)
    return R


def solve(H, spells):
    max_score = 0
    for spell in spells:
        x, y, z = parse_spell(spell)
        R = rates(x, y, z)
        score = 0
        for n, r in R.iteritems():
            if n >= H:
                score += r
        max_score = max(max_score, score)

    return max_score


def main():
    T = int(raw_input())
    assert 1 <= T <= 1000

    for t in range(1, 1+T):
        H, S = map(int, raw_input().split(' '))
        assert 1 <= H <= 10000
        assert 2 <= S <= 10
        spells = raw_input().split(' ')
        assert len(spells) == S
        ans = solve(H, spells)
        print 'Case #%d: %.6f' % (t, ans)



if __name__ == '__main__':
    main()
テスト。

心配だったのは精度。20面のサイコロを20回振った場合の合計の分布を取って、トータルで1.0(-1e-9)になったので良しとした。

#!/usr/bin/env nosetests -s -v -d
# test_c1.py
from c1 import parse_spell, ydie_xtimes, rates, solve

def test_parse_spell():
    def _test(s, expected):
        x, y, z = parse_spell(s)
        assert 1 <= x <= 20
        assert y in (4, 6, 8, 10, 12, 20)
        assert -10000 <= z <= 10000
        assert (x, y, z) == expected

    _test('2d4', (2, 4, 0))
    _test('1d8', (1, 8, 0))

    _test('10d6-10', (10, 6, -10))
    _test('1d6+1', (1, 6, 1))

    _test('1d4+4', (1, 4, 4))
    _test('2d4', (2, 4, 0))
    _test('3d4-4', (3, 4, -4))

    _test('10d4', (10, 4, 0))
    _test('5d8', (5, 8, 0))
    _test('2d20', (2, 20, 0))

    _test('1d10', (1, 10, 0))
    _test('1d10+1', (1, 10, 1))
    _test('1d10+2', (1, 10, 2))
    _test('1d10+3', (1, 10, 3))


def test_sample_cases():
    def _test(H, _spells, expected):
        spells = _spells.split(' ')
        # xyzs = map(parse_spell, spells)
        actual = solve(H, spells)
        assert abs(actual - expected) <= 1e-6

    _test(2, '2d4 1d8', 1.0)
    _test(10, '10d6-10 1d6+1', 0.99852)
    _test(8, '1d4+4 2d4 3d4-4', 0.25)
    _test(40, '10d4 5d8 2d20', 0.0025)
    _test(10, '1d10 1d10+1 1d10+2 1d10+3', 0.4)


def test_ydie_xtimes():
    def _test(y, x, expected_y_x, expected_list):
        y_x, ls = ydie_xtimes(y, x)
        assert y_x == expected_y_x
        assert ls == expected_list
        assert len(ls) == 1 + y*x  # 5 .. 401
        assert sum(ls) == y_x

    _test(6, 1, 6, [0, 1, 1, 1, 1, 1, 1])
    _test(6, 2, 36, [0, 0, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1])


def test_rates():
    R = rates(2, 4, 1)
    assert sorted(R.keys()) == [3, 4, 5, 6, 7, 8, 9]
    R = rates(1, 6, -3)
    assert sorted(R.keys()) == [-2, -1, 0, 1, 2, 3]

    for X in range(1, 21):
        for Y in (4, 6, 8, 10, 12, 20):
            for Z in (-10000, -5000, -X*Y, 0, X*Y, 5000, 10000):
                R = rates(X, Y, Z)
                minkey, maxkey = X+Z, Y*X+Z
                assert len(R) == maxkey - minkey + 1
                assert all(minkey <= key <= maxkey for key in R.keys())
                total = sum(R.values())
                assert abs(1.0 - total) <= 1e-9