AtCoder Beginner Contest 142 ／ Python

●　初学者です。（ 2019 / 9 ～ 現在３ヵ月目 ）
●　AtCoder の問題に Python で取り組んでいます。
●　ABC で４問目（茶か緑）まで解けることを目標にしています。

完全に独学なのでコードは酷いと思います。

AtCoder やってる方、お気軽にコメントくださいませ。

A - Odds of Oddness

n = int(input())

if n % 2 == 0:
   print(0.5)

else:
   print((n+1)/(2*n))

B - Roller Coaster

特に何も考えないので通った。

n,k = map(int,input().split())
h = list(map(int,input().split()))

count = 0

for i in h:
   if i >= k:
       count += 1

print(count)            

せっかく143回で二分探索をやったので使ってみた。

from bisect import bisect_left

n,k = map(int,input().split())
h = sorted(list(map(int,input().split())))

print(n - bisect_left(h,k))

二分探索を自力で書いてみた。

n,k = map(int,input().split())
h = sorted(list(map(int,input().split())))

if k > h[n-1]:
   print(0)

else:

   low = 0
   high = n-1
      
   while low < high:
          
       mid = (low + high)//2
          
       if k > h[mid]:
              
           low = mid +1
          
       else:    
              
           high = mid 

   else:
          
       print(n - low)

二分探索（自力）
二分探索（bisect）
普通に書いたやつ　　の順番。

むしろ二分探索を使って遅くなっている。

内包表記

n,k=map(int,input().split())
h=list(map(int,input().split()))
print(sum([1 for i in h if i>=k]))

３行で行けるらしい、内包表記が苦手なのを何とかしないと。

C - Go to School

辞書に入れてバリューでソートしてみた。

n = int(input())
l = list(map(int,input().split()))

L = {}

for i in range(n):
   L[i] = l[i]

sort_L = sorted(L.items(), key=lambda x:x[1])

for j in sort_L:
   print(j[0]+1, end=" ")
   

enumerate を使えばリストで簡単に書けることが判明。

n = int(input())
l = list(map(int,input().split()))

L = [0]*n

for i, order in enumerate(l,1):
   L[order-1] = i

print(*L)    

D - Disjoint Set of Common Divisors

下で調べた試し割法をそのまま使っている。
連除法に直したかったのだが、途中の条件がわからずに断念。

def prime_factorize(n):
  a = [1]
  while n % 2 == 0:
      a.append(2)
      n //= 2
  f = 3
  while f * f <= n:
      if n % f == 0:
          a.append(f)
          n //= f
      else:
          f += 2
  if n != 1:
      a.append(n)
  return a


a,b = map(int,input().split())
  
print(len(set(prime_factorize(a)) & set(prime_factorize(b))))   

試し割り法による素因数分解。

def prime_factorize(n):
   a = []
   while n % 2 == 0:
       a.append(2)
       n //= 2
   f = 3
   while f * f <= n:
       if n % f == 0:
           a.append(f)
           n //= f
       else:
           f += 2
   if n != 1:
       a.append(n)
   return a
   

print(prime_factorize(36))    

E - Get Everything

要：動的計画法
メモ：ナップサック問題

以下、参考にさせて頂きました。

典型的な DP (動的計画法) のパターンが整理されていたので python で書いてみる - わかばめにっき

難しい、12番まであるうち２番までしか読めていない。

しかし、ナップサック問題は読んだので、

ABC142　-E,F- Python 競技プログラミング Atcoder - じゅっぴーダイアリー

Python で解答を書いている方がいたので、見てみることにした。 

import sys
input = sys.stdin.readline
n,m = map(int,input().split())

dp = [float("inf")]*(1<<n)
dp[0] = 0
for _ in [0]*m:
   a,b = map(int,input().split())
   sc = 0
   for e in map(int,input().split()):
       sc += 1<<(e-1)
   
   for i in range(1<<n):
       dp[i|sc] = min(dp[i|sc],dp[i]+a)


if dp[-1] == float("inf"):
   print(-1)
else:
   print(dp[-1])

なんじゃこりゃ、全くわからん。

ビット演算子？ ｜とか << が何をしているのかさっぱりだ。

AtCoder Beginner Contest 142 参戦記 - Qiita

もう一人いらっしゃった。

def read_key():
   a, b = map(int, input().split())
   m = 0
   for c in map(int, input().split()):
       m |= 1 << (c - 1)
   return (a, m)


INF = float('inf')

N, M = map(int, input().split())
keys = [read_key() for _ in range(M)]

dp = [INF] * (1 << N)

dp[0] = 0
for i in range(M):
   a, m = keys[i]
   for j in range((1 << N) - 1, -1, -1):
       if dp[j] == INF:
           continue
       if dp[j] + a < dp[j | m]:
           dp[j | m] = dp[j] + a

if dp[(1 << N) - 1] == INF:
   print(-1)
else:
   print(dp[(1 << N) - 1])

やはり ｜と << がある。

無理。やはり E 問題は今やるべきじゃない、諦めよう。

F - Pure

もう問題が何言ってるのかわからないよね・・・

マガジン：他の回もやっていきます。

AtCoder Beginner Contest｜もやし｜note