CHR_Virtual_10の解説的なやつです。
Atcoderの公式解説見たほうが良い気はするが...
最後の問題は後で書きます
1. ABC 218 A - Weather Forecast
三項演算子を使うときれいに書けます
n = int(input())
s = input()
print("Yes" if s[n - 1] == "o" else "No")
2. ARC 114 A - Not coprime
$ X_i
考えられる組み合わせを全探索する時は、bit全探索と相場が決まってるのですが、上手く書けなかったのでcombinationsを使いました。やってることはbit全探索と同じです。
from itertools import combinations
from math import gcd
n = int(input())
x = list(map(int, input().split()))
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
ans = float("inf")
for i in range(1, len(prime) + 1):
for j in combinations(prime, i):
temp = 1
for k in j:
temp *= k
for k in x:
if gcd(temp, k) == 1:
break
else:
ans = min(ans, temp)
print(ans)
3. ABC 161 D - Lunlun Number
pythonにはheapqというO(logN)で要素を挿入、最小値を取り出せる便利なデータ構造があります。(他言語だと、priority queueと呼ばれていたりする)
基本的には、nを任意のルンルン数とした時、
けど、一の位が0の時は $$ 10 \times n + n mod 10 - 1
from heapq import *
h = [_ for _ in range(1, 11)]
heapify(h)
k = int(input())
s = set()
cnt = 1
while True:
n = heappop(h)
if n in s:
continue
if cnt == k:
print(n)
exit()
s.add(n)
cnt += 1
if n % 10 != 0:
heappush(h, 10 * n + n % 10 - 1)
if n % 10 != 9:
heappush(h, 10 * n + n % 10 + 1)
heappush(h, 10 * n + n % 10)
4. 三井住友 2019 E - Colorful Hats 2
書いてみたものの、ユーザー解説の方が超絶分かりやすいので、そっちを見てください
「
最初の0は3色のどれかが入る。次の0は残りの2色。最後は1色しか無い。
先頭から1が出てきたら、それより前の0の個数分だけの選択肢がある。
次に1が出てきたら、0は1つ使われているので、それより前の0の個数-1分だけの選択肢がある。
この選択肢は全部独立に考えることができるので、組み合わせをかけ合わせる。
」
n = int(input())
a = list(map(int, input().split()))
mod = 1000000007
rgb = [0, 0, 0]
ans = 1
for i in a:
if i in rgb:
cnt = rgb.count(i)
ans *= cnt
rgb[rgb.index(i)] = i + 1
ans %= mod
else:
ans = 0
break
print(ans)
5. AGC 055 A - ABC Identity
水色は難しいですね、下のコードはよもぎ君のです。
Sを6個以下の部分列にいい感じに分解する方法は、ABC, ACB, BAC, BCA, CAB, CBAの6つしか無いから、貪欲チックに考えればいいそうです。
公式じゃないけど、具体例載ってて分かりやすい解説
# 解説AC
from collections import deque
from itertools import permutations
n = int(input())
s = input()
d = {}
for c in ["A", "B", "C"]:
for i in range(3):
d[(c, i)] = deque()
for i in range(3 * n):
d[(s[i], i // n)].append(i)
ans = [-1] * (3 * n)
cur = 1
for i, j, k in permutations([0, 1, 2]):
while len(d[("A", i)]) > 0 and len(d[("B", j)]) > 0 and len(d[("C", k)]) > 0:
ans[d[("A", i)].pop()] = cur
ans[d[("B", j)].pop()] = cur
ans[d[("C", k)].pop()] = cur
cur += 1
print(*ans, sep="")