ARC087振り返り

2完でした。3問目はよくわかっていないので、年末時間がアレば復習したいですね。（そう言って復讐する問題を無限に貯めるのは良くないですね）

C - Good Sequence

https://beta.atcoder.jp/contests/arc087/tasks/arc087_a

良い数にするために除外する数字の総数を求めます。 削れば良いパターン（規定数より多い場合）と、全て取り除くパターン（規定数より少ない場合）を総計してやれば答えが求まります。

python3のコード； https://beta.atcoder.jp/contests/arc087/submissions/1874446

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import defaultdict

def solve():
    n = int(input())
    ad = defaultdict(int)
    for i in input().split():
       ad[int(i)] += 1
    
    ans = 0
    for k, v in ad.items():
        if k > v:
            ans += v
        if v > k:
            ans += v - k
    print(ans)

if __name__=="__main__":
    solve()

D - FT Robot

https://beta.atcoder.jp/contests/arc087/tasks/arc087_b

Tが偶数回のときはX軸方向、奇数回のときはY軸方向に進むことが出来るので、行く可能性がある場所をDPライクに求めてあげると出ます。

ただ一回もTがないときのパターンと、初回に初めてTが出たときのパターンだけは注意が必要です。（そこで3WAくらいしてしまったので）

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve():
    s = input()
    xa, ya = map(int, input().split())
    xset = set([0])
    yset = set([0])

    if "T" not in s:
        print("Yes" if len(s) == xa and ya == 0 else "No")
        return

    fcnt = 0
    tcnt = 0
    for c in s:
        if "T" == c:
            if fcnt > 0:
                if tcnt % 2 == 0:
                    if tcnt == 0:
                        xset = set([x + fcnt for x in xset]) 
                    else:
                        xset = set([x + fcnt for x in xset]) | set([x - fcnt for x in xset])
                else:
                    yset = set([y + fcnt for y in yset]) | set([y - fcnt for y in yset])
            fcnt = 0
            tcnt += 1
        if "F" == c:
            fcnt += 1

    if fcnt > 0:
        if tcnt % 2 == 0:
            if tcnt == 0:
                xset = set([x + fcnt for x in xset]) 
            else:
                xset = set([x + fcnt for x in xset]) | set([x - fcnt for x in xset])
        else:
            yset = set([y + fcnt for y in yset]) | set([y - fcnt for y in yset])
    
    print("Yes" if (xa in xset) and (ya in yset) else "No")

if __name__=="__main__":
    solve()

E問題は読んでも解放が全く浮かばなかったので解説を読みながら考えようと思います。