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問題は読んでも解放が全く浮かばなかったので解説を読みながら考えようと思います。