ABC429 B - "N-1" / C - "Odd One Subsequence" 解説（ふわふわ）

ふわふわだから　多めにみてね

B "N-1"

問題概要

長さ N の整数列 A=(A1,A2,...AN) と整数 M
Aから1個取り除いて、残りのN−1個の合計をちょうどM にできるか？

制約

• 2 ≤ N ≤ 100
• 0 ≤ M ≤ 10000
• 0 ≤ Ai ≤ 100 （整数列Aのひとつずつの要素は100まで）
• 入力される値は全て整数

考えたこと

• 1個取り除く前の合計を持っておいて、　1番目の要素からN番目の要素までひとつずつ順番に引いていく（全部試す）→ ちょうどMになるかどうか確認する

コード

Python

N,M=map(int,input().split())
A=list(map(int,input().split()))

sumA=sum(A) #Aを全部足したもの
ans="No" #いったん"No"で答えを作っておく

for i in A: #Aの中のものをiとして表示する、テストケース1だとi=3,2,3,4
  if sumA - i == M: #Aを全合計からiを引いたものがちょうどMになったら
    ans="Yes" #ansを"Yes"状態に変える
    #ここでbreakって書いてforループを抜けてもいい
    #抜けてなくてもリストの長さは100までなので、回しきっても大丈夫
print(ans)

C "Odd One Subsequence"

問題概要

長さ N の整数列 A=(A1,A2,...AN)
1 ≤ i < j < k ≤ N をみたす整数の組（ i , j , k ）で、次の条件をみたす個数

Ai , Aj , Ak が（ 2 , 2 , 1 ）とか（ 3 , 3 , 4 ）みたいになる
→ 2つ等しくて1つだけ違う

制約

• 3 ≤ N ≤ 2×10**5
• 1 ≤ Ai <= N（リストの中の数はリストの長さを超えないよ〜）

考えたこと

• 1個の方を見ようとすると時間がかかりそうなので、2個組を見つける×他の数字って感じで足したら良さそう
• 各数字が何個あるかは辞書で管理したい

コード

Python

n=int(input())
a=list(map(int,input().split()))
d={} #辞書の用意
ans=0 #答えの元を用意

#辞書に各文字の個数をカウントする
for i in a: #Aの中のものをiとして表示する、テストケース1だとi=3,2,5...
  if i not in d: #もし辞書にまだ登録されていなければ
    d[i]=1 #1個めなので、1個めだよ〜と登録
  else: #もう登録済なら
    d[i]+=1 #登録してある辞書に1足す（辞書の数値も+=1,-=1ができる）
    
# d={3: 1, 2: 3, 5: 1}
for i in d: #辞書でもこの書き方ができて、辞書の左から順番に見出しを取り出す
            #テストケース1の場合、i=3,2,5
  if d[i] >= 2: #もし見出しの値が2以上であれば
    ans+=(d[i]*(d[i]-1)//2)*(n-d[i])
    #(見出しの値)C2 =
    #見出しの値から2個選ぶ組合わせ * 見出しの値以外の残りの数字全部 を答えに足す

print(ans)