AtCoder ABC257 A-DをPythonで解く

A - A to Z String 2

$N$が十分に小さいので２つの解き方があります。

• 文字列を実際に作成してそのindexを参照する方法
• $O(1)$で文字を特定する方法

注意: 文字列の結合はimmutableな変数を作成するため、$O(1)$ではありません。今回は制約が小さいので文字列を生成して間に合いますが、注意してください

実装(Python/シミュレーション)

n, x = map(int, input().split())
s = ""
for i in range(26):
    s += chr(ord("A") + i) * n
print(s[x-1])

実装(Python/O(1))

n, x = map(int, input().split())
print(chr(ord("A") + (x-1)//n))

B - 1D Pawn

そのまま実装します。

C - Robot Takahashi

イベントソートで解きます。体重を発生する時間$t$だとみなし、$(t, event)$というイベントのリストを考え、各イベントを以下の通りにします。

• event0: 子供の人数を追加する
• event1: 測定を行う
• event2: 大人の人数を追加する

event0, 2が起こった際には、それまでに発見した大人と子供の人数をインクリメントします。この時、event1の測定とは、それまでに発見した子供の数 + (大人全体の数 - それまでに発見した大人の数)とし、、求めるべき正しく判定した人数になります。

実装(Python)

import sys
import math

INF = 1 << 63
ceil = lambda a, b: (((a) + ((b) - 1)) // (b))

"""
event
0: 大人を足したい
1: 判定する
2: 子供を足したい
"""
def do():
    n = int(input())
    s = input()
    datw = list(map(int, input().split()))
    events = []
    ans = -1
    # 0 が子供、1が大人
    allotona = s.count("1")
    allkodomo = s.count("0")
    events.append( (0.5, 1) )
    events.append( (10**10, 1))
    for x in set(datw):
        events.append( (x, 1) )
        events.append((x+0.5, 1))
        #events.append((x - 0.5, 1))
    for i in range(n):
        if s[i] == "1": # otona
            events.append( (datw[i], 0) )
        elif s[i] == "0": # kodomo
            events.append( (datw[i], 2) )
    events.sort()
    #print(events)
    detectotona = 0
    detectkodomo = 0
    for t, q in events:
        if q == 0: # otona
            detectotona += 1
        elif q == 2:
            detectkodomo += 1
        elif q == 1:
            #print(t, detectkodomo, detectotona)
            x = detectkodomo + (allotona - detectotona)
            ans = max(ans, x)
        else:
            assert False
    #print(events)
    print(ans)

do()

D - Jumping Takahashi 2

ダイクストラ法で解きます。
まず、入力を処理し、$u$から$v$の移動に必要な$s_{uv}$の辺をもつ有向グラフを作ります。ここで、必要な$s_{uv}$とは、$u$, $v$のコストを視点側の$p$で割り、切り上げた値となります。

このようなグラフを作り、全点を順番に始点としてダイクストラ法を行います。

• 典型的なダイクストラ法では、次の点への到達コストを今いる点のコスト + 次の点に移る辺のコストとして更新できる点を辿っていきます。
• 今回はmax(今いる点のコスト, 次の点に移る辺のコスト)とします。これが次の点のコストを最小で更新できるなら、次の点をキューに入れ、処理していきます。

このダイクストラ法で求められるのは、ある始点から任意の点にたどり着くために必要な最小コストです。ここでのコストとは必要な"s"の最小値となります。
ある始点$i$を考えた時、この$max$はその始点からすべての点に辿り着くために必要な最小なコストに他ありません。すべての$i$についてこれを求めて$min$をとることで、題意を満たす最小の$s$が得られます。

時間計算量を見積もります。辺の数が$E=N^2$,頂点の数が$V=N$であるため、ダイクストラ法１回のコストは$O(N^2 log N)$になり、すべての$N$からの始点の計算を行いたいので、$O(N^3 log N)$になります。
空間計算量を見積もります。辺を持つのに$O(N^2)$最も多くかかり、これが空間計算量になります。

実装(Python)

import sys

input = sys.stdin.readline
from pprint import pprint

import math

INF = 1 << 63
ceil = lambda a, b: (((a) + ((b) - 1)) // (b))


def do():
    import heapq
    from collections import deque
    class dijkstra():
        INF = 2 ** 62 + 10000
        INF = float("inf")

        def __init__(self, numV):
            self.numV = numV
            self.e = [[] for _ in range(numV)]

        def makeEdge(self, s, t, cost):
            #print(s, t, cost)
            self.e[s].append((t, cost))

        def solve(self, nodeS, nodeT):
            self.cost = [self.INF] * self.numV  # cost
            self.parent = [-1] * self.numV  # parent node
            q = [(0, nodeS)]  # 初期ノード(cost 0)
            self.cost[nodeS] = 0
            heapq.heapify(q)
            while len(q) > 0:
                curcost, curnode = heapq.heappop(q)
                # print("Curcost:{0}, Curnode{1}".format(curcost, curnode))
                # 打ち切り。ゴールが明確ならここに入れる。
                # if curnode == nodeT: return
                if curcost > self.cost[curnode]:
                    continue
                for nextnode, edgecost in self.e[curnode]:
                    nextcost = max(edgecost, self.cost[curnode])
                    if self.cost[nextnode] > nextcost:
                        self.cost[nextnode] = nextcost
                        #self.parent[nextnode] = curnode
                        heapq.heappush(q, (nextcost, nextnode))

    n = int(input())
    import fractions
    from fractions import Fraction
    import math
    dat = []
    for _ in range(n):
        x, y, p = map(int, input().split())
        dat.append( (x, y, p) )
    dj = dijkstra(n)
    for u in range(n):
        x1, y1, p1 = dat[u]
        for v in range(n):
            if u == v: continue
            x2, y2, p2 = dat[v]
            # u->v
            cost = abs(x1-x2) + abs(y1-y2)
            puv = ceil(cost , p1)
            pvu = ceil(cost , p2)
            dj.makeEdge(u, v, puv)
            dj.makeEdge(v, u, pvu)
    ans = INF
    for i in range(n):
        dj.solve(i, i)
        ans = min(ans, max(dj.cost))
        #print(i, dj.cost)
    print(ans)

do()