AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

天下一2013予選B B - 天下一後入れ先出しデータ構造

問題原文

atcoder.jp

解法

まともにデータを持っては間に合わないので、 (数字, 個数) というように持つ。
スタックの要素数は、↑の形式で持っても毎回舐めると間に合わないので、変数で管理するようにする。

↓のちょっとめんどくさいバージョンという感じ。
at274.hatenablog.com

実装

Q, L = map(int, input().split())
stack = []
stack_size = 0

for q in range(Q):
    query = list(input().split())
    if query[0] == 'Push':
        n, m = int(query[1]), int(query[2])
        stack_size += n
        if stack_size > L:
            print('FULL')
            exit()
        stack.append([m, n])

    elif query[0] == 'Pop':
        n = int(query[1])
        stack_size -= n
        if stack_size < 0:
            print('EMPTY')
            exit()

        while n:
            if n >= stack[-1][1]:
                n -= stack[-1][1]
                stack.pop()
            else:
                stack[-1][1] -= n
                n = 0

    elif query[0] == 'Top':
        if stack_size == 0:
            print('EMPTY')
            exit()
        print(stack[-1][0])

    elif query[0] == 'Size':
        print(stack_size)

print('SAFE')

感想

今なら茶diffがつきそうな気がする。

ARC007 C - 節約生活

問題原文

atcoder.jp

解法

sample2で貪欲の線はなくなる。

制約が小さいので「どこからテレビをつけ始めるか」のbit全探索ができる。

実装

過去にテレビを点けといたことにして、今から  N 分間ついてればOKみたいな感じにした。
modでやればよかったと後悔(まぁいいか)

from itertools import product
S = list(input())
N = len(S)

ans = float('inf')
for pattern in product([0, 1], repeat=N):
    pattern = list(pattern)
    X = [0] * (2 * N)
    for i, p in enumerate(pattern):
        if p == 0:
            continue
        for j, s in enumerate(S, start=i):
            if s == 'x':
                continue
            X[j] = 1
            if j + N < 2 * N:
                X[j + N] = 1
    if sum(X[N:]) == N:
        ans = min(ans, sum(pattern))

print(ans)

感想

推定diff1400ぐらいらしい。こういう実装問題は普通にすき。
令和ABCなら800はつきそうだなぁ。

DigitalArts 2012 B - Password

問題原文

atcoder.jp

解法

与えられたパスワードと同じものはダメ というのが少し面倒。

2種類正解候補を考えられればどちらかは必ず答えになりうる。

ということで、できるだけ z に近いものを使う場合のパスワードできるだけ a に近いものを使う場合のパスワード を計算した。

実装

ほくほく。

S = input()
P = sum([ord(s) - ord('a') + 1 for s in S])

# できるだけ z に近いものを使うように
cnt = 0
P1 = P
ans1 = []
while P1 and cnt < 20:
    p = min(P1, 26)
    ans1.append(p)
    P1 -= p
    cnt += 1

# できるだけ a に近いものを使うように
cnt = 0
P2 = P
ans2 = []
while P2 and cnt < 20:
    p = max(1, P2 - 26 * (20 - cnt - 1))
    ans2.append(p)
    P2 -= p
    cnt += 1

ans1 = ''.join([chr(ord('a') + a - 1) for a in ans1])
ans2 = ''.join([chr(ord('a') + a - 1) for a in ans2])

if P1 == 0 and ans1 != S:
    print(ans1)
elif P2 == 0 and ans2 != S:
    print(ans2)
else:
    print('NO')

感想

推定水diffらしい。令和ABCで出たら半分は通しそう。
もっとうまい方法あったら教えてください。

ABC019 D - 高橋くんと木の直径

問題原文

atcoder.jp

解法

 1 \leq N \leq 50 で、質問は100回まで。

 N 回の質問で葉を見つけ、  N 回の質問で木の直径を求めればよい。
普通に木の直径を求めるだけ。

実装

まぁ普通に。

N = int(input())

max_dist = 0
leaf = -1

for n in range(1, N + 1):
    print("? 1 {}".format(n))
    dist = int(input())
    if dist > max_dist:
        max_dist = dist
        leaf = n

max_dist = 0
for n in range(1, N + 1):
    print("? {} {}".format(leaf, n))
    dist = int(input())
    max_dist = max(max_dist, dist)

print("! {}".format(max_dist))

感想

推定水diffらしい。
実際の難しさに対してdiffが高く感じるのはインタラクティブだからかな?

ARC014 C - 魂の還る場所

問題原文

atcoder.jp

解法

とりあえず、消せる時は消してしまうのが最も得をしそうなのは明らか。

問題は消せない時。(例えば、 RG と詰めている時に、 B がきた時)

これは、 RG のうち片方が次きても消せなくなるのと同じなので、 RG のうち「より早くくる方が消せるように」B を詰めるのが最適。

〜〜〜〜〜〜〜〜〜〜 ここまでが自分の解法 〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

もっと賢い人がたくさんいた。

  1. RG とある時に B がきた場合、みるのは次の一手だけで大丈夫
    → 次が B なら 今の B は無視してよいし、 B でないなら RG であるから

  2. 答えは奇数個あるボールの種類
    1の応用で、RGとある時に B を入れた次のターンでは必ずボールを消せることがわかる。
    → 最大で RGB のような形にしかならないのなら、偶数個あるボールは全部消せる。

天才。

実装

それに比べて僕は、、、僕は、、、(まぁいいか)
アーリーリターンならぬアーリーコンティニューが僕はすきです。

from collections import deque
N = int(input())
S = input()

que = deque()
for i, s in enumerate(S):
    if len(que) == 0:
        que.append(s)
        continue

    if que[0] == s:
        que.popleft()
        continue

    if que[-1] == s:
        que.pop()
        continue

    if len(que) == 1:
        que.append(s)
        continue

    if i == N:
        que.append(s)
        continue

    for sj in S[i + 1:]:
        if sj == que[0]:
            que.append(s)
            break

        if sj == que[-1]:
            que.appendleft(s)
            break
    else:
        que.append(s)

print(len(que))

感想

かなりパズルチックで僕は好きです。
制約が  1 \leq N \leq 50 なのがDPを疑ってしまってちょっと憎らしい。

推定diff1200とからしいけど、

atcoder.jp

とあんま変わらないような気もする(↑をやってたから解けたともいえる)

Indeedなう(予選B) D - 高橋くんと数列

問題原文

atcoder.jp

解法

とりうる  (l, r) の組み合わせは  \frac{N × (N + 1)}{2} 通り。 (  l = r でも良いので)

 c について、条件を満たすものを数え上げようとすると、結局   1 ~ N のループを各  c について回したくなるし、なにより面倒なので 条件を満たさないものを数えて引く ことを考える。

条件を満たさないものは以下のように計算できる。
f:id:AT274:20200525225520j:plain

実装

先頭と末尾に番兵を置いておくと楽です。

from collections import defaultdict
N, C = map(int, input().split())
A = list(map(int, input().split()))

ALL = N * (N + 1) // 2
D = defaultdict(list)
for i, a in enumerate(A):
    D[a].append(i)
for c in range(1, C + 1):
    D[c] = [-1] + D[c] + [N]

for c in range(1, C + 1):
    ans = 0
    for i in range(len(D[c]) - 1):
        ans += (D[c][i + 1] - D[c][i]) * (D[c][i + 1] - D[c][i] - 1) // 2
    print(ALL - ans)

感想

その数を1つでも含むような〜その数を1つも含まない〜 の言い換えは受験とかでもよくみますね。

CODE FESTIVAL 2014 予選B C - 錬金術士

問題原文

atcoder.jp

解法

 S1 から「最低何文字使う必要があるか」「最大何文字使う必要があるか」を計算し、  N / 2 がその間にあれば YES

各文字種について互いに影響し合わないので個別に考えて良い。

ある文字種  xについて、 S1 から使える最大個数は、  min( S1 内の  x の個数,  S3 内の  x の個数 ) 個。
ある文字種  xについて、 S1 から使う必要がある最低個数は、  max(0,  S3 内の  x の個数 -  S2 内の  x の個数 )
個。

これらの情報を求めておいて判定すればいい。
ポイントは 厳密に1つの解を求めようとするのではなく、ざっくりと可能不可能を判定しようとする ことかなぁ。。。
上限と下限を求めておいて、その間にあるかで判定 みたいな考え方は汎用性高そう。

実装

from collections import Counter
S1 = input()
S2 = input()
S3 = input()

C1 = Counter(S1)
C2 = Counter(S2)
C3 = Counter(S3)

L, R = 0, 0
for i in range(26):
    x = chr(ord('A') + i)
    L += max(0, C3[x] - C2[x])
    R += min(C1[x], C3[x])

if L <= len(S3) // 2 <= R:
    print('YES')
else:
    print('NO')

感想

推定1300弱diffらしいけど解けなかったよ。。。
何もわからなかったのでたくさん勉強させてもらったと思おう。

雰囲気近いのは

atcoder.jp

のにぶたん解かなぁとか思ったり。