ARC048

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

A - タブの開きすぎ

概要

ブラウザのタブを開ける，閉じるのどちらかを順序に沿って回行う．
ただし，個以上のタブが開くとブラウザがクラッシュしてタブが1個の状態に戻る．
ブラウザがクラッシュした回数を求めよ．

解法

この手の問題はステートマシーンを思い浮かべながら，reduceを使って書くと楽なイメージ．
（再帰で書くとスタックオーバーフローで死ぬ）
python3で引数にtupleを入れる構文(Tuple Parameter Unpacking?)が廃止されたことを初めて知った．

www.python.org

reduceもfunctoolsに隔離されるし，lambdaを廃止する話もあったらしいし，極端だなぁ

from functools import reduce
N, L = list(map(int, input().split()))
def solve(tab_crash, c): 
    tab, crash = tab_crash
    if c == "+":
        tab = (tab % L) + 1
        return (tab, crash + (1 if tab == 1 else 0), )
    else:
        return (tab-1, crash)
print(reduce(solve, input(), (1, 0))[1])

B - 同一円周上

概要

2次元平面上に個の点が存在する．各点は格子点上に存在している．
全ての点からのマンハッタン距離が等しい，かつ，格子点上に存在する点を求めろ．

解法

なぜこれがB問題なのか...
全ての点と求める点Pのマンハッタン距離が等しいということは，点Pを中心(?)とした菱形の辺上に全ての点が並んでいるということ．
この菱形の候補を考え，点P（菱形の中心）の候補を求め，実際に条件を満たしているか判定すれば良い．
点を全て90度回転させる（+2倍に伸ばす）とわかりやすくなる．

from itertools import product
def transform(pos): # (rotate 90) + 2x
    x, y = pos
    return (x + y, -x + y)

def origin(pos):
    x, y = pos
    return ((x - y) // 2, (x + y) // 2)

def dist(pos1, pos2):
    return sum(abs(a - b) for a, b in zip(pos1, pos2))

def get(positions):
    minx = miny = float("inf")
    maxx = maxy = -float("inf")
    for x, y in positions:
        minx = min(minx, x)
        miny = min(miny, y)
        maxx = max(maxx, x)
        maxy = max(maxy, y)
    return minx, miny, maxx, maxy

def solve(positions):
    t_positions = map(transform, positions)
    minx, miny, maxx, maxy = get(t_positions)
    D = max((maxx - minx), (maxy - miny)) // 2
    P = list(product((minx + D, maxx - D), (miny + D, maxy - D)))
    for ppos in map(origin, P):
        if all(dist(pos, ppos) == D for pos in positions):
            return ppos
    raise

N = int(input())
positions = [tuple(map(int, input().split())) for _ in range(N)]
print(*solve(positions))

C - N!÷K番目の単語

概要

}]の数字を並べ替えたものを個用意する．
これを辞書順に並べたとき，番目を求めよ.

解法

部分点しか取れてない．なぜこれがC問題なのか...
このセットは全体的に難易度が高いように思う．

X番目の数列を求めるとして，この数列の先頭1番目はとなる.
すでに使った数字を考慮しながら，これを再帰的に繰り返していけば良い．
（コードでは数列の先頭番目が残っている数字の内何番目に小さいかを求めた後，実際の数列に戻している）

from itertools import compress
from functools import reduce
from math import factorial

def calc(x_order, i):
    x, order = x_order
    order.append(x // factorial(i))
    x %= factorial(i)
    return x, order

def get(order_unused_ans, i):
    order, unused, ans = order_unused_ans
    idx = order[i]
    for n in compress(range(len(unused)), unused):
        if idx == 0:
            ans.append(n)
            unused[n] = 0
            break
        idx -= 1
    return order, unused, ans


if __name__ == "__main__":
    N, K = list(map(int, input().split()))
    order = reduce(calc, range(N-1, -1, -1), (factorial(N) // K - 1, []))[1]
    ans = reduce(get, range(N), (order, [0] + [1] * N, []))[2]
    print(*ans, sep="\n")

概要

解法