ARC049
問題元 → Welcome to AtCoder Regular Contest 049 - AtCoder Regular Contest 049 | AtCoder
A - "強調"
概要
指定された4箇所に'"'を挟むだけ.
解法
Pythonでは文字列を作成する際に"と'の両方を使えるが,文字列中で"を使いたい時は'を,文字列中で'を使いたい場合は"で作成すればエスケープシーケンスを使う必要がなくなる.
例えば
s1 = '"""強調"""' s2 = "'''強調'''"
string.joinもいいが,python3系ではprint関数でsep='"'を指定する方がちょっとだけ楽.
(この機能,競プロですごく便利.)
S = input() A, B, C, D = list(map(int, input().split())) print(S[:A], S[A:B], S[B:C], S[C:D], S[D:], sep='"')
B - 高橋ノルム君
概要
2次元平面上に 人の高橋君がいる.にいる高橋君はへ移動するのにの時間がかかる.最も適した場所を選んだ時,全員が集合するのにかかる最小の時間は?
解法
全ての点を調べることは不可能な以上,場所を絞る必要があることはすぐに分かる.
また,一般的に,条件を満たす値そのものを求めるよりも,条件を満たす値が存在するかyes/noを求める方が簡単.
ここら辺から逆算すると,時間で集合可能な場所が存在するかを求めれば良さそうなことが分かる.
(時間でどこかしらに全員が集合可能なら,それより少し後の時間でも移動可能.単調増加であり,yes/noが切り替わる箇所は2分探索で求められる.)
また,移動時間の式から,時間内に高橋君が移動できる箇所はそれぞれ座標軸に平行な(?)矩形を描くことが分かる.
通常,重複箇所の判定は非常にややこしいものになるが,この性質を考慮すれば簡単に済む.
ここまできたらあとはコードに落とすだけ.
N = int(input()) X, Y, C = [], [], [] for _ in range(N): x, y, c = list(map(int, input().split())) X.append(x) Y.append(y) C.append(c) def check(cost): left, right = -10**5, 10**5 for x, c in zip(X, C): left = max(left, x - cost / c) right = min(right, x + cost / c) if left > right: return False left, right = -10**5, 10**5 for y, c in zip(Y, C): left = max(left, y - cost / c) right = min(right, y + cost / c) if left > right: return False return True left, right = -1, 10 ** 5 * 10 ** 3 + 1 for _ in range(100): mid = (left + right) / 2 if check(mid): right = mid else: left = mid print(right)
C - ぬりまーす
概要
全ての制約を満たすようにグラフの頂点に色を塗る.
制約は二種類ある.
- 制約1: 頂点xを塗る時,頂点yを塗っていなければならない.
- 制約2: 頂点xを塗る時,頂点yが塗られていてはいけない.
最大でいくつの頂点を塗ることができるか?
解法
何かしら簡単にする方法があるはず.
与えられる制約2の数はこれよみがしに少ないので制約1のみの場合を考える.
まず塗れない箇所を調べる方法を考える.
例えば,
- 頂点xを塗らなければ頂点yを塗れない,
- 頂点yを塗らなければ頂点zを塗れない,
- 頂点zを塗らなければ頂点xを塗れない,
のように,制約がぐるっと輪を作っている場合,どの頂点も塗ることができない.
これは有向グラフに落とし込めそうだ.
では真っ先に塗れる頂点はどこだろうか?これはグラフ上で入次数が0であるノードであることが分かる.
では次に塗れるのは?これは入次数が1,かつ,入ってくる辺の元の頂点が塗られているノード.
ではさらにその次に塗れるのは?これは入次数が2,かつ,入ってくる辺の元の頂点が全て塗られているノード.
(もしくは入次数が1,かつ,入ってくる辺の元の頂点が塗られているノード)
このステップを続けても,制約がぐるっと輪を作っている場合とは矛盾しない.
また,いずれかのステップであえて色を塗らなかった場合,最終的に塗られている頂点の数は必ず少なくなる.
かつ,(制約1のみを考えているので)ある頂点に色を塗ることで他の頂点に色が塗れなくことはない.
よって,この方法で更新が起こらなくなった時に塗られている頂点の数が塗れる頂点の最大となる.
このアルゴリズムをもう少し賢く行うと頂点数を,辺の数をとして塗れる頂点の最大を求めるのに.
ここまでくれば,制約2に関しては,
- 制約2: 頂点yを決して塗らないか、頂点xを塗る時,頂点yを塗っていなければならない.
と言い換えれば良いだけ.
以上から[tex: {O(NA2B)}].
(振り返ってみると,塗れない箇所云々は必要なかったが,メモとして残しておく.)
class Node(object): def __init__(self): self.in_degree = 0 self.cur_inputs = 0 self.dest = [] def __str__(self): return "in_degree:{}, cur_inputs:{}, dests:{}".format(self.in_degree, self.cur_inputs, self.dest) def bfs(edges, N, used): from collections import deque ret = 0 nodes = [Node() for _ in range(N)] que = deque(list(range(N))) for e in edges: nodes[e[0]].dest.append(e[1]) nodes[e[1]].in_degree += 1 while len(que) > 0: n = que.popleft() if used[n]: continue if nodes[n].in_degree > nodes[n].cur_inputs: continue ret += 1 used[n] = True for d in nodes[n].dest: nodes[d].cur_inputs += 1 que.append(d) return ret if __name__ == "__main__": from itertools import product, compress N = int(input()) A = int(input()) YX = [] for _ in range(A): x, y = map(int, input().split()) YX.append((y-1, x-1,)) UV = [] B = int(input()) for _ in range(B): u, v = map(int, input().split()) UV.append((u-1, v-1,)) ans = 0 for flags in map(list, product([0, 1], repeat=B)): edges = list(compress(UV, list(map(lambda x: x^1, flags)))) used = [False] * N for e in compress(UV, flags): used[e[0]] = True ans = max(ans, bfs(YX + edges, N, used)) print(ans)
D - すわっぷしまーす
概要
解法
解けていない.
で書けてると思うのだが...
ところで,解説(ヒント)のセグメント木に関する記述が面白い.
・たとえば、RMQ(Range minimum Query)をSegTreeでやるとどうなるか?
・[a, b]の最小値というクエリを、O(logn)個の”木の全ての葉の値の最小値”というものに分割している
今まで,RMQ(セグメント木)はをのように分割し,その途中経過を覚えておくことで更新のコストを最小限に抑える手法,のようなイメージだった.
解説の解釈の方が抽象度が高く,応用を効かせやすい.
ぜひ次回に生かしたい.
(そもそも「区間クエリ」って言葉を知らなかったり,セグメント木を知らな過ぎたとも...)
from array import array class Tree(object): def __init__(self, rank): self.rank = rank self.swap_flags = array("L", [0] * (2**rank)) def getitem(self, key): left, right = 1, 2 ** (self.rank - 1) + 1 index = 1 swap_flag = 0 while left + 1 < right: swap_flag >>= 1 swap_flag ^= self.swap_flags[index] mid = (left + right) // 2 if key < mid: index = 2 * index + (swap_flag & 1) right = mid else: index = 2 * index + ((swap_flag & 1) ^ 1) left = mid return index - 2 ** (self.rank - 1) + 1 def swap(self, a, b): def _swap(a, b, left, right, depth, index=1, swap_flag=0): if b < a or right < left: return if right < a or b < left: return if a == left and right == b: self.swap_flags[index] ^= 1 << depth return swap_flag ^= self.swap_flags[index] mid = (left + right) // 2 _swap(a, min(mid, b), left, mid, depth-1, 2*index+(swap_flag & 1), swap_flag >> 1) _swap(max(a, mid+1), b, mid+1, right, depth-1, 2*index+((swap_flag & 1) ^ 1), swap_flag >> 1) for d in range(self.rank): left, right = 2 ** d , 2 ** (d + 1) - 1 _swap(max(a, left), min(b, right), left, right, d) if __name__ == "__main__": N, Q = list(map(int, input().split())) tree = Tree(N+1) for _ in range(Q): t, a, b = list(map(int, input().split())) if t == 1: print(tree.getitem(a)) else: tree.swap(a, b)