ZONeエナジープログラミングコンテスト “HELLO SPACE” 参加記録

A, B, D の3完0ペナ 40分でした

A - UFO襲来

長さが $12$ で固定のため、単純に調べれば OK です。

S = input(); cnt = 0
for i in range(len(S)):
    cnt += S[i:i+4] == 'ZONe'
print(cnt)

B - 友好の印

本番では切片の二分探索で解きました。今考えてみると、各障害物の座標それぞれについて、その座標と UFO の座標を通る直線の式を求めて、一番高い切片となったものが答えで良いですね。

C - MAD TEAM

解説ACです。本番では $O(N^{2})$ 解法でやってみましたが TLE でした。能力値の最大を持っている人をそれぞれ固定して残りを全探索する方針でしたが、これは嘘解法ですね。。そうでない場合も普通に作れそうです。

竸プロ典型90問でも、最大値の最小化は二分探索、というものがありますが、応用できませんでした。これを使って 0 1 にする発想は覚えておきたいです。

実装は、答えの値を二分探索で決め打ちして、各メンバーの能力がそれ以上かそうでないかを 1 0 で表現して圧縮し、3つ選んだときの組み合わせを探索する方針です。

ここで、5桁の bit で考えて実装するのがやりやすいかと思います。例えば、ある人の能力がそれぞれ [6, 7, 3, 1, 10] として、6 以上かどうかで 1 0 を振ることを考えたとき、これを 5桁の bit で見て、11001 (10進数だと25) とします。

あとは、3つの組み合わせの探索で bit の OR 演算を行い、結果 11111 になれば、二分探索で決め打ちした値は答えになり得ます。

(参考)提出コード

from itertools import combinations
import sys

input = sys.stdin.readline


def ORlist(l:list) -> int:
    res = 0
    for k in l: res = res | k
    return res


def main():
    N = int(input())
    energy = []
    for _ in range(N):
        A, B, C, D, E = map(int, input().split())
        energy.append((A, B, C, D, E))
    
    R = 10**9 + 1 # right side
    L = 1   # left side
    while True:
        if L+1 >= R:
            break
        mid = (L+R)//2
        energyset = set([])
        for ener in energy:
            A, B, C, D, E = ener
            s = 2**4*(A >= mid) + 2**3*(B >= mid) + 2**2*(C >= mid) + 2**1*(D >= mid) + 2**0*(E >= mid)
            energyset.add(s)
        energylist = list(energyset)
        flag = False
        for iters in combinations(energylist, min(3, len(energylist))):
            res = ORlist(list(iters))
            if res == 2**5-1:
                flag = True
                break
        if flag: L = mid # True
        else: R = mid # False
    print(L)


if __name__ == "__main__":
    main()

D - 宇宙人からのメッセージ

ABC199 の C問題と発想は同じです。

操作が二種類あり、そのうち「末尾に加える」は $O(1)$ でできるので良いのですが、「反転させる」操作は $O(|S|)$ かかる操作なので、実際に反転させる処理を書くと TLE になると思います。

したがって、「反転させる」が起こったら、挿入位置の方を反転させて、「先頭に加える」ようにします。末尾にも先頭にも $O(1)$ で追加したいので、collections.deque を使います。

反転しているかどうかは flag で管理しました。

また、問題文では最後に同じ文字が2文字連続したら取り除く操作をしていますが、この操作は挿入した段階で消しても変わりません。むしろ挿入段階でやった方が abba など対応しにくい形も気にせず取り除けるので、挿入段階で消してしまいます。

提出コード

from collections import deque


def main():
    S = input()
    flag = False
    ans = deque([])
    for s in S:
        if s == 'R':
            if flag: flag = False
            else: flag = True
        else:
            if flag: # 反転しているとき
                ans.appendleft(s)
                if len(ans) >= 2:
                    if ans[0] == ans[1]:
                        ans.popleft()
                        ans.popleft()
            else:
                ans.append(s)
                if len(ans) >= 2:
                    if ans[-1] == ans[-2]:
                        ans.pop()
                        ans.pop()
    if flag:
        ans.reverse()
    print(''.join(ans))


if __name__ == "__main__":
    main()

E - 潜入

後日ときます。

Xenous の精進記録

AtCoder関連他、学習したことの記録です。