ARC048

問題元　→　Welcome to AtCoder Regular Contest 048 - AtCoder Regular Contest 048 | AtCoder

A - 階段の下

概要

地上[tex: {10⁹}]階，地下[tex: {10⁹}]階を持つビルがある．ただし0階は存在しない．
階から階への移動には，階段を何階分登る必要があるか？

解法

ソートしてから場合分け． 0-indexedの偉大さがわかる（？）

a, b = list(sorted(map(int, input().split())))
if a * b > 0:
    print(abs(b - a))
else:
    print(b - a - 1)

B - AtCoderでじゃんけんを

概要

N人集まって総当りでジャンケンを行う．
ただし，参加者はそれぞれレートを持っており，相手よりレートが高い場合は問答無用で勝ちとなる．
また，総当り中の手は全て固定．

解法

いわゆるTopCoderジャンケン．（元ネタを貼ろうと思ったが見つからなかった...）
愚直に総当りをすると[tex: {O(N²)}]となり間に合わない．
レートでのソート+総当り中の手が全て固定なことをを利用すると．
...のはずなのだが，通らない．辛い．

他の言語であれば通るのでよしとする（？）
おそらく，リストの各要素へのアクセスが（言語として）遅いことがネックとなっていると予想している．

indexで頑張るよりもクラスなりを作って名前でアクセスする方が頭がこんがらなくて良い．
（といつも思うのだが，本番だと少しの時間をケチってindexでのアクセスで頑張り，結局バグって後悔することが多い）

from collections import namedtuple
from itertools import islice
Player = namedtuple("Player", ["rate", "hand", "id"])
class Result:
    def __init__(self):
        self.win = 0
        self.lose = 0
        self.draw = 0

    def __str__(self):
        return "{} {} {}".format(self.win, self.lose, self.draw)

N = int(input())
players = []
for i in range(N):
    r, h = list(map(int, input().split()))
    players.append(Player(r, h-1, i))
players.sort(reverse=True)
results = [Result() for _ in range(N)]
start, end = 0, None
while start < len(players):
    end = start + 1
    while end < len(players) and players[end].rate == players[start].rate:
        end += 1
    rps = [0] * 3
    for p in islice(players, start, end):
        rps[p.hand] += 1
    for p in islice(players, start, end):
        results[p.id].draw = rps[p.hand] - 1
        results[p.id].win = rps[(p.hand + 1) % 3] + N - end
        results[p.id].lose = rps[(p.hand + 2) % 3] + start
    start = end
print(*results, sep="\n")

C - 足の多い高橋君

概要

解法

from fractions import gcd
from functools import reduce
from math import ceil
MOD = 10 ** 9 + 7
N = int(input())
L = list(sorted(set([int(input()) for _ in range(N)]), reverse=True))
ml = L.pop()
cycle = reduce(gcd, map(lambda x: x-ml, L)) if L else 0
print(pow(2, ml+int(ceil(cycle/2)), MOD))

D - たこ焼き屋とQ人の高橋君

概要

解法