天下一Game Battle Contest(β)

「電力供給網をデザインせよ」

日本では近年地方の過疎化が問題となっています。
そこで、某県に存在する天下一市では数年後に計画都市が建造されることになりました。

街には複数の家と発電所がグリッド状に配置され、その間を電線が通り、電力を供給します。
コウヘイ君はこの街の主要建築家として、街の電力網のデザインを任されました。
家と発電所の位置は既に決定済です。
コウヘイ君は、さらにそれらの間に電線を通すとしたらどれくらいの電力量を供給できるかを計算しました。

ところで、特殊な地理状況下にある天下一市は並行世界（パラレルワールド）の干渉を受けることで有名です。
この計画都市では電線の素材として希少金属（レアメタル）を使用していたため、複数の並行世界が同じ場所に電線を通した場合、
その並行世界の数だけ電力の供給量が減ってしまうということが事前の調査で判明しました。

困ったコウヘイ君は天下一プログラマーであるあなたに助けを求めました。
期限までに、与えられた街について総電力供給量がなるべく多くなるような電力網をデザインしてください。

問題概要

JavaScriptが無効になっているためPDFファイルへのリンクを表示します.問題概要PDF

参加マニュアル

JavaScriptが無効になっているためPDFファイルへのリンクを表示します.マニュアルPDF

API仕様

以下の5種類のAPIを使用してゲームに参加します。

GET /api/game
GET /api/stage/<game_id>
GET /api/claim/<token>/<game_id>/<edge_index>
GET /api/edges/<token>/<game_id>
GET /api/ranking/<token>/<game_id>

<token> はポータルサイトトップに記載されています。

GET `/api/game`

進行中のゲーム情報を取得するAPIです。

リクエストの例

GET /api/game

レスポンス

レスポンスは以下の形式で返却されます。

game_id
T

game_id, T は整数です。 game_id は進行中のゲームのIDを表します。進行中のゲームが存在しない場合、 game_id は -1 となります。 T はそのゲームの残り時間をミリ秒単位で表します。

レスポンスの例

1
55940

GET `/api/stage/<game_id>`

そのゲームのグラフの情報を取得します。
返却される内容はゲーム中に変化しません。

リクエストの例

GET /api/stage/1

レスポンス

レスポンスは以下の形式で返却されます。

N M
S[0] S[1] ... S[N-1]
T[0] T[1] ... T[M-1]
C[0] C[1] ... C[759]

N, M, S[i], T[i], C[i] は整数です。 S[i] は、始点と頂点 S[i] が繋がっていることを表します。 T[i] は、終点と頂点 T[i] が繋がっていることを表します。 C[i] は辺 i の容量を表します。

※ 与えられるグラフについては、問題概要もご参照ください。

制約

N は 10 以上 20 以下
M は 30 以上 50 以下
C[i] は 1 以上 10000 以下

レスポンスの例

17 42
54 55 82 103 139 155 158 164 213 218 239 253 267 288 294 389 393
6 11 22 25 38 92 101 110 111 124 149 162 170 191 192 196 204 210 220 221 225 228 248 272 273 282 293 296 298 309 310 315 319 321 336 340 342 343 345 357 368 376
1133 5174 8089 6937 6209 2482 7615 3420 5803 9743 1243 3844 4483 7173 5506 4160 4902 6096 6639 9856 2862 519 7404 4173 3121 9445 3505 611 1649 2911 9418 5166 2460 8448 1326 5532 5868 1871 6970 6836 5376 1902 5303 1357 9528 3452 582 1200 8333 233 2778 3430 539 59 9000 8734 6822 2472 1375 2782 5169 2686 925 6884 6045 1442 5434 1166 5241 469 4178 296 318 5247 2364 5556 8232 2719 8283 5369 888 6227 7372 6168 2129 468 6990 9916 786 559 7346 7485 2143 2299 9796 3277 5506 8867 6795 1335 5606 5492 4012 9424 9554 6872 7676 4536 1558 3794 7483 133 5916 3715 2918 4753 4725 1097 1534 2790 7093 7332 9312 6432 9376 6565 5088 7790 3819 7140 4853 170 357 593 4032 4476 1205 8533 9380 4718 3757 1259 7974 2480 2535 9435 9873 3093 1438 9487 6715 8397 9223 5852 9343 3357 3659 2258 4044 7347 5285 8486 4363 7147 8052 3969 8505 4365 3049 3987 7611 2516 7327 3243 941 6477 6382 5576 2229 9792 65 3419 2679 6617 4011 7644 6439 552 7390 7866 3352 7327 2073 4552 2749 9573 7284 4245 1094 5624 7162 7016 9005 1307 3379 8619 7961 262 4118 3752 1817 3505 9514 2074 5381 969 3875 9780 3256 2109 4391 1225 3805 7064 7231 6214 3307 4630 2170 7393 3596 419 8929 831 5711 1542 5345 2054 2726 1837 3841 383 9321 6692 4541 6376 1858 9539 4972 6937 1691 6169 2630 3332 7205 9003 3947 2700 6907 5998 2867 1213 7559 7038 6573 4001 1562 6991 95 1527 2456 5961 4525 8675 6632 5962 9018 1933 6615 5786 9940 4125 7186 4204 4787 7737 3602 3983 3383 427 4776 597 7565 230 5809 5265 8318 2395 1564 6722 2162 1079 4555 8442 6566 6806 1017 1967 1494 9252 2963 490 514 4847 894 9173 6496 6794 2519 5811 2662 1716 9962 1037 1807 9946 818 8542 8295 1203 5359 7959 9438 1484 9719 3951 4524 5949 4638 3771 934 855 5304 7510 6953 7152 6917 3724 6220 7591 2280 1971 1146 4515 7453 2806 6300 3909 8225 5982 4641 497 4610 6075 1087 6251 9661 2784 2525 8048 8508 8587 510 5761 444 3131 2432 464 8498 3340 9464 2784 1335 4779 9984 8985 3448 9185 8694 3814 1491 265 9310 556 8635 8033 2662 6097 9310 9326 2578 132 5246 4246 735 1710 2877 3472 8628 4179 8195 1395 1920 1726 6136 7292 9828 6023 4592 3465 3472 1585 7533 4609 5037 2434 794 5140 5131 6291 3900 5490 8126 1053 3586 7714 6040 2314 2636 5924 5493 859 2617 933 3926 6142 8738 7035 2155 6694 9291 9210 8865 391 4461 8592 4961 1258 2678 5884 2193 4995 2694 472 5048 7882 4337 6499 8631 2560 6709 9617 35 4097 6295 2819 665 7433 541 4497 6345 357 6851 4582 8180 6202 9914 1010 7752 7230 9263 6031 8414 4687 8567 9132 4483 3695 8465 4988 3821 2204 2516 3601 5451 3607 9403 516 5428 5088 5143 3731 4977 4182 9039 7037 9487 5785 5472 9994 3283 5322 6242 6681 7236 7166 3106 3577 3055 8982 9894 3243 4421 3277 3710 8499 7214 5622 9978 9433 2728 5716 1446 6340 7933 2805 6896 7685 9210 7972 8858 6711 5058 1485 9696 9872 4238 2459 9189 9874 8148 34 6586 4887 6646 7748 1827 249 7807 1177 4018 6704 3253 8752 4439 7775 3926 4789 2172 1131 8606 3031 4968 8961 9829 2236 3882 9055 4122 3872 7438 9413 5701 6767 1425 7660 3147 7588 5990 9685 8873 9010 5473 4515 754 272 5322 2113 6932 9557 7092 3792 4480 2639 8711 9127 9276 3580 9006 4734 865 1615 5340 286 3901 4340 7620 6014 8941 1892 8124 1957 2184 8990 272 9965 6249 9488 5323 990 7781 2177 145 4260 6195 6821 2059 1642 3847 2591 224 2770 9441 4662 6541 3134 9389 3127 8325 3437 1225 1980 2970 5497 5114 6337 2039 8337 1589 4994 7731 2240 6383 9101 7825 8188 8993 6679 1451 197 6331 2277 2053 5964 1318 4297 8216 2403 6443 5500 9830 8094 8306 9753 2207 6015 1791 4527 7461 1601 7579 3172 7506 9027 7849 672 2356 2430 260 1224 1110 5210 8127 3518 5004 4890 7814 3175 7726 893 5513 2643 9277 1918 725 9085 9662 7600 941 4168 8923 5559 2452 7440 596 8394 279 6578 2326 6920 5321 4550 1922 2988 7475 7871 7604 9886 7899 7169 3575 9040 340 4030 9708 7140 4535 5222 3295 8477

GET `/api/claim/<token>/<game_id>/<edge_index>`

辺を取得するAPIです。

リクエストの例

GET /api/claim/xxxxxxxxxxxxxxxxxxxxx/1/2

※ edge_index は 0オリジンであることに注意してください。

レスポンス

レスポンスは以下の形式で返却されます。

msg

辺の取得に成功した場合、 msg は ok となります。その辺を既に取得していた場合、 msg は already_claimed となります。この API の時間制限に抵触した場合、 msg は claim_time_limit となります。

時間制限

辺を取得してから 500 ミリ秒の間、そのゲームにおいて辺を取得できません。

レスポンスの例

ok

GET `/api/edges/<token>/<game_id>`

辺の取得状況を取得するAPIです。

リクエストの例

GET /api/edges/xxxxxxxxxxxxxxxxxxxxx/1

レスポンス

レスポンスは、時間制限に抵触していない場合、以下の形式で返却されます。

ok
A[0] A[1] ... A[759]
B[0] B[1] ... B[759]

A[i], B[i] は整数です。 A[i] は、辺 i を自分を含めて A[i] 人が取得していることを表します。 B[i] は、辺 i を自分が取得しているかを表します。取得している場合は 1 、取得していない場合は 0 となります。

時間制限に抵触している場合、以下の形式で返却されます。

too_many_request

時間制限

この API は 1000 ミリ秒に 2 回に制限されます。ビジュアライザは、およそ 1000 ミリ秒に 1 回このAPIを使用するのでご注意ください。

レスポンスの例

ok
0 1 2 1 2 1 1 1 1 3 1 1 0 0 0 1 3 1 1 2 0 1 0 1 1 1 1 1 1 1 2 2 1 0 0 2 3 2 2 0 1 0 2 2 0 2 2 0 1 0 0 0 0 1 1 3 1 2 0 2 2 0 1 1 0 1 1 3 0 1 2 2 2 1 1 2 2 1 4 3 1 0 2 0 3 3 0 0 1 1 1 1 1 2 1 1 1 1 1 0 3 0 3 0 1 2 0 3 0 0 1 0 2 1 1 1 0 1 2 2 2 0 2 1 1 1 1 1 3 2 1 2 1 0 2 0 0 3 1 1 3 1 3 2 1 2 1 3 2 1 1 2 0 2 0 3 1 1 0 0 1 1 0 1 3 0 0 2 0 1 1 1 2 1 2 0 3 0 0 1 1 1 0 0 3 3 1 1 0 2 3 1 1 0 1 2 1 0 2 0 0 2 1 3 2 2 3 1 1 1 3 2 0 0 2 2 1 1 2 2 1 1 0 2 2 1 2 3 3 1 0 2 0 1 2 1 0 0 0 1 0 1 2 2 0 0 1 2 1 2 2 0 0 1 1 0 0 0 2 0 1 2 0 0 1 2 0 2 0 0 0 1 0 1 0 0 3 0 2 1 1 2 5 1 1 1 0 1 0 0 1 3 0 1 0 0 2 1 1 3 1 0 1 1 0 2 2 3 2 2 0 0 1 1 0 1 2 2 1 1 2 1 0 2 4 1 0 2 1 2 1 1 1 2 3 2 3 1 1 0 1 0 0 4 3 3 2 3 3 1 0 2 0 1 1 1 2 0 1 1 0 1 0 0 1 2 2 2 1 0 4 0 1 1 1 0 0 0 2 1 1 2 1 3 0 0 3 1 1 1 3 0 1 0 1 3 1 4 2 0 0 2 0 1 0 1 1 2 3 0 1 0 2 0 2 3 3 2 1 2 0 0 2 1 2 3 1 2 2 2 0 1 2 2 0 1 0 3 0 2 0 1 0 1 0 1 1 1 1 1 4 0 3 0 0 2 1 2 1 1 0 2 0 0 2 1 1 2 2 1 4 1 4 2 1 1 1 1 1 1 2 0 2 1 1 1 1 1 1 0 1 1 1 1 1 1 0 3 1 0 1 4 1 3 1 2 2 0 2 1 2 1 3 2 2 2 2 0 3 3 1 4 1 2 0 2 0 1 2 0 2 2 0 1 3 2 1 2 4 2 1 0 0 2 0 0 2 1 1 0 1 4 5 3 1 3 1 2 0 2 0 1 1 1 0 3 2 0 2 1 1 2 4 2 1 1 2 2 1 0 0 0 2 0 3 1 1 3 1 1 2 2 2 1 0 0 1 5 2 0 1 0 1 2 1 0 2 2 2 4 2 2 0 0 2 0 0 0 2 1 2 1 2 0 2 2 2 3 4 3 1 1 4 0 2 1 0 1 4 1 2 1 0 0 0 2 0 3 1 0 1 0 1 2 2 1 1 0 1 2 1 1 1 3 3 1 1 0 2 0 3 1 0 1 1 1 2 0 1 0 1 1 1 2 1 1 2 1 2 0 1 0 0 2 1 0 1 0 1 3 2 2 1 2 0 2 2 1 0 1 2 0 0 4 0 2 2 1 2 3 2 4 0 2 0 0 0 2 0 2 3 0 2 2 1 0 0 1 1 2 1 1 2 1 3 3 0 5 2 1 2 2 0 1 1 0 1 2 1 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

GET `/api/ranking/<token>/<game_id>`

特定のゲームのランキング上位を取得します。
ビジュアライザが表示するランキング情報です。

リクエスト例

GET /api/ranking/xxxxxxxxxxxxxxxxxxxxx/1

レスポンス

レスポンスは、時間制限に抵触していない場合、以下の形式で返却されます。

ok
user_id
N
U[0] P[0]
U[1] P[1]
:
U[N-1] P[N-1]
R
S

user_id, U[i] は文字列 (user_id) です。 N, R は整数です。 P[i], S は実数です。

user_id は自分の user_id です。 P[i] は、そのゲームにおける U[i] のスコアを表します。 R は自分の順位(1オリジン)を表します。順位表にまだ入っていない場合、 R は 0 となります。 S は自分のスコアを表します。

スコア計算には数秒の遅延があります。

時間制限に抵触している場合、以下の形式で返却されます。

too_many_request

制約

N は 10 以下

時間制限

この API は 1000 ミリ秒に 2 回に制限されます。ビジュアライザは、およそ 1000 ミリ秒に 1 回このAPIを使用するのでご注意ください。

レスポンス例

ok
user10080
10
user47059 1329.9749999999999
user86289 1143.375
user79607 1143.375
user77170 1143.375
user61900 1143.375
user43790 1143.375
user27781 1143
user25676 1143
user99997 941.79999999999995
user97142 941.79999999999995
15
683.83333333333

サンプルコード


#!/usr/bin/env python3
"""
辺をランダムに取得し、点数を計算するサンプルプログラムです。
実行には python3 環境が必要です。
TOKEN 変数を書き換えて実行してください。
"""

import os
import random
from typing import NamedTuple, List, Dict
from urllib.request import urlopen
import time

# ゲームサーバのアドレス
# GAME_SERVER = os.getenv('GAME_SERVER', 'https://obt.tenka1.klab.jp') # 2019-obt
GAME_SERVER = os.getenv('GAME_SERVER', 'https://practice.gbc-2020.tenka1.klab.jp') # 2020-practice

# あなたのトークン
TOKEN = os.getenv('TOKEN', 'sample')

# 頂点と辺の数
NUM_NODES = 400
NUM_EDGES = 760


def call_api(x):
    with urlopen(f'{GAME_SERVER}{x}') as res:
        return res.read().decode()


def main():
    while True:
        # GET /api/game
        game = call_api('/api/game')
        game_id, remining_ms = list(map(int, game.split()))
        print(f"ゲームID {game_id}")
        print(f"残り時間 {remining_ms}ms")

        if game_id < 0:
            break

        while 0 < remining_ms:
            # GET /api/stage/<game_id>
            stage_resp = call_api(f'/api/stage/{game_id}')
            stage = list(map(int, stage_resp.split()))

            num_source = stage[0]
            num_sink = stage[1]
            sources = stage[2:2 + num_source]
            sinks = stage[2 + num_source:2 + num_source + num_sink]
            caps = stage[2 + num_source + num_sink:]
            assert len(caps) == NUM_EDGES

            # 辺をランダムに選び取得します
            edge_index = random.randint(0, NUM_EDGES - 1)
            # GET /api/claim/<token>/<game_id>/<edge_index>
            claim_resp = call_api(f'/api/claim/{TOKEN}/{game_id}/{edge_index}').strip()
            print(claim_resp)
            if claim_resp == "ok":
                print(f"辺取得成功 {edge_index}")
                pass
            elif claim_resp == "game_finished":
                break
            else:
                print(f"辺取得失敗 {edge_index}")

            # 辺の取得状況を確認し、スコアを計算します
            # GET /api/edges/<token>/<game_id>
            edges_resp = call_api(f'/api/edges/{TOKEN}/{game_id}').strip().split('\n')
            if edges_resp[0] == "ok":
                claim_counts = list(map(int, edges_resp[1].split()))
                my_claims = list(map(int, edges_resp[2].split()))
                score = calculate_score(sources, sinks, caps, claim_counts, my_claims)
                print("スコア", score)

            # API制限のため少しの間待ちます
            time.sleep(0.5)


# cf. https://github.com/spaghetti-source/algorithm/blob/9cca6b826f19ed7e42dd326a4fbbb9f4d34f04d3/graph/maximum_flow_dinic.cc
INF = 1 << 50


class Edge(NamedTuple):
    src: int
    dst: int
    capacity: int
    rev: int


class Graph:
    def __init__(self, n: int):
        self.n = n
        self.adj: List[List[Edge]] = [[] for _ in range(n)]
        self.flow: Dict[Edge, int] = {}

    def add_edge(self, src: int, dst: int, capacity: int):
        e1 = Edge(src, dst, capacity, len(self.adj[dst]))
        self.adj[src].append(e1)
        self.flow[e1] = 0
        e2 = Edge(dst, src, 0, len(self.adj[src])-1)
        self.adj[dst].append(e2)
        self.flow[e2] = 0

    def max_flow(self, s: int, t: int):
        level = [0 for _ in range(self.n)]
        iter = [0 for _ in range(self.n)]

        def levelize():
            for i in range(len(level)):
                level[i] = -1
            level[s] = 0
            q = [s]
            while q:
                u, q = q[0], q[1:]
                if u == t:
                    break
                for e in self.adj[u]:
                    if e.capacity > self.flow[e] and level[e.dst] < 0:
                        q.append(e.dst)
                        level[e.dst] = level[u] + 1
            return level[t]

        def augment(u, cur):
            if u == t: return cur
            while iter[u] < len(self.adj[u]):
                e = self.adj[u][iter[u]]
                r = self.adj[e.dst][e.rev]
                if e.capacity > self.flow[e] and level[u] < level[e.dst]:
                    f = augment(e.dst, min(cur, e.capacity - self.flow[e]))
                    if f > 0:
                        self.flow[e] += f
                        self.flow[r] -= f
                        return f
                iter[u] += 1
            return 0

        flow = 0
        while levelize() >= 0:
            iter = [0 for _ in range(self.n)]
            while True:
                f = augment(s, INF)
                if f <= 0:
                    break
                flow += f
        return flow


# フローを流して点数を計算します
def calculate_score(sources, sinks, caps, claim_counts, my_claims):
    ratio = 1000

    g = Graph(NUM_NODES + 2)

    # 各始点に向けて容量無限の辺を貼る
    for source_node in sources:
        g.add_edge(NUM_NODES, source_node, INF)

    # 各終点から容量無限の辺を貼る
    for sink_node in sinks:
        g.add_edge(sink_node, NUM_NODES + 1, INF)

    # 自分が取得した辺を貼る
    for edge_index in range(NUM_EDGES):
        if not my_claims[edge_index]:
            continue
        q = edge_index // 39
        r = edge_index % 39
        if r < 19:
            v1 = 20 * q + r
            v2 = 20 * q + r + 1
        else:
            v1 = 20 * q + r - 19
            v2 = 20 * q + r - 19 + 20
        cap = caps[edge_index] * ratio // claim_counts[edge_index]
        g.add_edge(v1, v2, cap)
        g.add_edge(v2, v1, cap)

    return g.max_flow(NUM_NODES, NUM_NODES + 1) / ratio


if __name__ == "__main__":
    main()