Competitive Programing Typical 90 Problem day4

Day4.

I think my barriers of programming are gone, if I keep this training for 90 days.

Let's try 4th Problem. This one is easy one.

 

Code is below.

H, W = map(int,input().split())
#入力を受け取る
Map = 
#地図を入れるもの、かご
preprocess1 = [0 for _ in range(H)]
#H行の各行の総和を入れるかご
for i in range(H):
  temp1 = list(map(int, input().split()))
  #入力を受けつつ
  preprocess1[i] = sum(temp1)
  #総和を計算
  Map.append(temp1)

preprocess2 = [0 for _ in range(W)]
#W列の各列の総和を入れるかご
for j in range(W):
  for i in range(H):
    preprocess2[j] += Map[i][j]
    #総和を計算

New_Map = [[0] * W for _ in range(H)]
#新しい地図を作る
for i in range(H):
  for j in range(W):
    New_Map[i][j] = preprocess1[i] + preprocess2[j] - Map[i][j]
    #包除原理 |A∪B|=|A|+|B|-|A∩B| のこと。
  print(*New_Map[i])

 

  • 今回はうまく包除原理を使おうという回だった。
  • せっかくなので、包除原理について調べてみる。
  • まずはこちら
    • いくつも集合があったとき、そのすべての和集合を、積集合の塊として表す式。
    • 「総和集合=-∑(-1)^k(k個の部分積集合の総和)」
    • または、よりも、かつ、の方が扱いやすいことが多い。
      • 男、または、40歳以上
        • 男か、40歳以上の女
      • 男、かつ、40歳以上
        • 40歳以上の男
    • 二項定理による証明や、数学的帰納法による証明がある。
  • さらに、こちらのスライドをまとめてみる。
    • 包除原理の説明。
      • 和集合を積集合で表す。
      • 積集合の足し引きの規則性
        • 何個の積か、偶奇性
        • 奇数なら1、偶数なら‐1
    • オイラーのΦ関数
      • 正の整数nについて、1からnまでの自然数のうち、nと互いに素な数の個数を、Φ(n)とおく。
        • Φ(10)=4
      • nの素因数を列挙する。
      • 素因数p1で割り切れる集合、p2で割り切れる集合、・・・を用意
      • それらすべての和集合の、補集合を考える問題
      • よって、包除定理の範疇になる。
      • 少しコードを書いてみる。
N = int(input())

def get_prime_factor(n):
  temp = n
  prime_list = 
  devide = 2
  while devide <= int(n**0.5):
    if temp % devide == 0:
      prime_list.append(devide)
      while temp%devide == 0:
        temp //= devide
    devide += 1
  else:
    if temp != 1:
      prime_list.append(temp)
  return prime_list


def Euler(n):
  all_prime = get_prime_factor(n)
  m = len(all_prime)
  answer = 0
  for i in range(2**m):
    sub_prime = []
    for j in range(m):  # このループが一番のポイント
      if ((i >> j) & 1):
        sub_prime.append(all_prime[j])
    k = len(sub_prime)
    product = 1
    if k==0:
      continue
    for l in range(k):
      product *= sub_prime[l]
    answer += (-1)**(k-1)*(n//product)
  return (n-answer, all_prime)


Euler(N)
#get_prime_factor(N)

 

  • 続きから始める
    • Uncommon
      • さっきのオイラー関数の話をなんども繰り返すだけ。
      • コードはパス
    • Ball and Boxes
      • この話が、こちらのサイトの話と繋がる。
      • n人を区別のあるk個のチームに分ける場合の数
      • 10人を3つに分ける場合、
        •  3^{10} - 3 ×2^{10} + 3
        • これは、補集合の考え方を採用して、
          • 10人が3つのどれかに入る
          • 10人が2つのどれかに入る
          • 10人が1つに入る
        • の足し引きで求まる。
      •  \Sigma_{i=1}^k (-1)^{k-i} {}_kC_i i^n
      • これを、区別のないグループにすると、スターリング数になる。
        • kの階乗で割るだけ。
      • 区別のないk個以下のグループに分ける方法の数をベル数という。
      • この問題の肝は、うまく対称性を利用して、Combinationでまとめて計算できる点でうれしい。
        • これは、n個からk個選んだ集合同士の重なりの部分(intersection)の要素数が全て等しいから。
    • Lahub and Permutations
      • これは、こちらのサイトの話と関連する。
      • 攪乱順列という「1からnまでの整数を並び替えて出来る順列で、i番目がiでないもの」の個数
      •  n!\Sigma_{k=0}^n \frac{(-1)^k}{k!}
      • 漸化式や、包除原理で導出出来る。
        • i番目が被る、という集合をn個考えて、
        • その積集合を考えるのは、容易い
        • それを足し引きすれば、完結。
      • ここからは、中級編に入っていくが、今回は踏み込まないことにする。

バイバイ!