PYTHON
CHR_Virtual_10の解説的なやつ
公開日:
2022/04/09
CHR_Virtual_10の解説的なやつ

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 Y $ は互いに素ではないので、$ Y $は1から50までの素数(15個)をいい感じにかけ合わせた数になります。
考えられる組み合わせを全探索する時は、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を任意のルンルン数とした時、

10×n+nmod10+1,10×n+nmod10,10×n+nmod101 10 \times n + n mod 10 + 1, 10 \times n + n mod 10, 10 \times n + n mod 10 - 1
を追加すれば良い。
けど、一の位が0の時は $$ 10 \times n + n mod 10 - 1
9の時は9の時は
10 \times n + n mod 10 + 1 $$ がルンルン数になりません。注意しましょう(私は9の時を忘れてました)

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="")
loading...