ABC202 参戦記

AISing Programming Contest 2021（AtCoder Beginner Contest 202） - AtCoder

パフォーマンス：565(A, B, Cの3完)

レーティング：344 → 367

3完したけどどうやらC問題が大分簡単だったみたいでパフォーマンスとしてはそんなに．しかしだいぶ本番でC問題までは解けるようになってきたので少し自信になった．

A問題

すべての面は足したら7になるのでもう片方は7-a, 7-b, 7-cになる．

a,b,c = map(int, input().split())

print(21-a-b-c)

B問題

ここで少し手こずった．まず，文字を反転させるという文字を読んでいなかったこと．また，配列の値を変更させようとしたら上手く行かなかった事が挙げられる．結局，新しい空の配列を作ってそこに条件を満たす要素を順に追加していく方針で解いた．

S = list(input())
S.reverse()
a = ""
for i in range(len(S)):
 if S[i] == "0":
   a+="0"
 elif S[i] == "1":
   a+="1"
 elif S[i] == "6":
   a+="9"
 elif S[i] == "8":
   a+="8"
 elif S[i] == "9":
   a+="6"
print(a)

後で知ったことだが，PyPyでは+=連結はクソ遅いらしい．

下手したらTLEになるので，+=するのではなく，appendで要素は追加していった方が良い

C問題

愚直に計算すると2重ループになるので計算量がO(N^2)になってしまう．

これを避ける方針として，自分はCから決めた．Cを固定すると，B_Cjは一発で決まる．そのとき配列Aの中にB_Cjが何個含まれているかがすぐに決まれば良いことに気づいた．pythonにはset型があるので，これを使えばある要素が配列の中に何個含まれているのか簡単に分かる．

このように「同じ値の要素の数をカウントする」という方針はC問題では頻出なので意識したい

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
from collections import Counter
ans = 0
l = Counter(A)
for i in range(N):
 c = C[i] - 1
 b = B[c]
 ans += l[b]
print(ans)

D問題

数学問題なので行けるかと思ったが無理だった．

最初は辞書順におっていくかと思ったが計算量が爆発するので不可能なことに気づく．

次に．

a○○○・・・・

b○○○・・・

と２パターンに分けていく方針でできると思った（実際に皆さんこれでやってるぽい）が，実装にいたらなかった．またそのうち出来たらあげます．