目的

Atcoderで上を目指すべく頑張っている中でABC221を解いたので、解説してみる
- pypy7.3を使って解いている

A問題

考察

問題文通りに解けば良い

実装

A, B = map(int, input().split())
print(pow(32, A-B))

結果

無事に解けた

B問題

atcoder.jp

考察

問題文通りに解けば良い
S, Tが同じならばYes
そうでなければ、一文字ずつ入れ替えて都度比較
- 同じになればYes
- ならなければNo

実装

S = input()
T = input()

flag = False

if S == T:
    flag = True
else:
    for i in range(1, len(T)):
        t = list(T)
        t[i-1] = T[i]
        t[i] = T[i-1]
        if list(S) == t:
            flag = True
            break

if flag:
    print("Yes")
else:
    print("No")

結果

無事に解けた

C問題

atcoder.jp

考察

力技で全探索した

なんとなく、Nを分解して、差が最も小さいようにできれば最大値が取れそう
- というものの、どうすればいいかパッと分からず・・・
Nは10^9以下の整数 なので、高々10桁の整数と考えると力技でもいけるのでは？と思った
- combinations で、Nのうちからいくつか整数の組み合わせを選ぶ
  - 1個以上選び、N-1個まで選ぶ
- 選ばれなかった数、選んだ数、それぞれで permutations を使い、並び替える
  - このとき、先頭に0がくる場合を防ぐことに注意する
- あとは、それぞれ計算し、最大値を保持する

実装

4重ループではあるが、時間内に間に合った

計算量が読みきれなかったが、ダメなら再度考えようと、割り切って提出
- 10 * 10Ci(max 10C5) * len(n)! * len(c)!
  - n, cが大きい時は階乗の計算は重くなるが、組み合わせは軽くなるので、なんとかなるのかな？と思った
    - 9! = 362880 なので、これに10かけても 10^7 台なのでなんとかなるかなという感覚

from itertools import combinations, permutations

N = list(input())

ans = 0

for i in range(1, len(N)):
    for c in combinations(N, i):
        n = N.copy()
        for j in range(len(c)):
            n.remove(c[j])
        for p1 in permutations(n):
            for p2 in permutations(c):
                a = int("".join(p1))
                b = int("".join(p2))
                if len(p1) == len(str(a)) and len(p2) == len(str(b)):
                    ans = max(ans, a*b)

print(ans)

結果

解説はスマートで、最大値をexactに求めるので、非常に高速だった・・・賢い！

無事に解けた

D問題

方針は大枠あってるものの、解けず(欲張ってE も解き出したのも敗因)

atcoder.jp

考察

最初はDPで解こうとしたが、A,Bの最大値(10⁹)の大きさを見て断念
各日付で何人ログインしているか、数え上げれば良さそうだけど、A,Bが大きく確実にTLEする
いもす法を考える
- 何となく、こんな感じで解くんだろうな〜と思ったがうまく使えず時間切れ
- ここじゃないけど、座標で+1, -1 したりした問題を解いた気がしたのでそんな雰囲気で解けそうな気はしてた

imoz.jp

解説みる

ログイン日(A)、ログアウト日(A+B)を保持し、sortし、前から順番に処理していけば良い
- ログインしたら cnt+=1 ログアウトしたら cnt-=1 して、k人がログインしている日数を保持しているlistを更新する
- 日数は、ログイン、ログアウトした日を保持して、sortした配列dateを用いて計算する
  - ログイン日数 = date[i+1] - date[i]

f:id:kazu_0716:20211003021611p:plain — ABC221 D メモ

実装

N = int(input())
date = []

for _ in range(N):
    A, B = map(int, input().split())
    date.append((A, 1))
    date.append((A+B, -1))
date.sort(key=lambda x: x[0])

ans = [0]*N
cnt = 0
for i in range(len(date)-1):
    cnt += date[i][1]
    if cnt == 0:
        continue
    ans[cnt-1] += date[i+1][0] - date[i][0]

print(*ans)