AtCoder Begginer Contest 106 C問題・典型90問（22・24・27・33問目）

AtCoder Python

前書き

AtCoder Begginer Contest 103 A〜C問題・典型90問（10問目）を解きました。

典型90問（22問目）

  • 時間：10分

各面において切り口の数が（x,y,z軸の長さの最大公約数 - 1）となれば、全てのマスが立方体になります。

import math
A,B,C=map(int,input().split())

K = math.gcd(math.gcd(A,B),C)
print(A//K+B//K+C//K-3)

典型90問（24問目）

  • 時間：8分

Aiを Ai-1 , Ai+1 する操作をK回行い、Bi に近づける問題です。
全てのiにおけるAiとBiの差の総和を計算します。この総和が上記の操作をK回（奇数 or 偶数）で実現できるかを以下の条件に従って算出します。

  • 奇偶判定で一致しているか
  • 差の総和>=Kであるか
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
count = 0
clear = 'Yes'
for i in range(N):
  if A[i]!=B[i]: count+=abs(B[i]-A[i])

if K<count: clear='No'
elif K%2!=count%2: clear='No'
print(clear)

典型90問（27問目）

  • 時間：12分

ユーザー名が重複のないように登録申請する問題です。
注意しなくてはならないのは1≤N≤10**5です。二重ループではTLEとなりますので工夫が必要です。

登録名をキーとして、その登録名がすでにカウントされているかをValueとして保持するディレクトリ型連想配列を生成します。ディレクトリ型連想配列からキーを検索するとO(1)でValueを取得できます。

つまり登録名が既に使用されているかをO(1)で調査できます。

N=int(input())
mydict={}
for i in range(N):
  s = input()
  if s in mydict.keys():
    pass
  else: print(i+1)
  mydict[s]=1

典型90問（33問目）

  • 時間：15分

縦2 * 横2の領域にLEDが二箇所以上点灯していないような点灯箇所の最大数を調査します。
縦・横の （2*2）領域の個数 + 1の積を算出します。

ただ注意しなくてはならないのは上記が該当するには、2 ≤ H,Wの場合に限ります。

import math
H,W=map(int,input().split())
if H<2 or W<2: print(H*W)
else: print(((H+1)//2)*((W+1)//2))

C問題（ABC106）

  • 時間：20分

atcoder.jp

初期文字列Sが存在し、i の数値で構成されています。
n日経過するとき、数値 i が ” i ” が （i**n）個分だけ増殖します。これが5000兆日経過した時の文字列のK番目の値を推定します。

import sys
S=input()
K=int(input())
for i,s in enumerate(S):
  if s!='1':
    print(s)
    sys.exit()
  else:
    if K<=(i+1):
      print(1)
      sys.exit()