AtCoder Beginner Contest 118・137・122・123・126 茶Diff

AtCoder Python

前書き

AtCoder Beginner Contest 118・137・122・123・126 茶Diffを解きました。

C問題（ABC118）

  • 難易度：茶
  • 時間：10分

体力最小のモンスターで残っているモンスターの体力を削りまくります。
例えば全てのモンスターの体力が偶数なら、どんなに攻撃を繰り返しても全てのモンスターの体力は奇数になることはないし、
それが3の倍数であっても同様です。

「体力が低いモンスターの体力分」だけ「体力が高いモンスターの体力」を削るのはユークリッド互除法に近く、全ての最大公約数を求めれば解けると結論づけました。

N=int(input())
A=list(map(int,input().split()))
import math
_num=A[0]
for i in range(1,N):
  _num=math.gcd(_num,A[i])
print(_num)

C問題（ABC137）

  • 難易度：茶
  • 時間：20分

atcoder.jp

2≤N≤10**5の文字列の中から単語のアナグラムとなっている組を探す問題です。
O（nlogn）のソートを行い、昇順文字列を連想配列のキー（昇順文字列）に格納し、昇順文字列のカウント数を値に格納します。
連想配列のキーからの値取得はO（1）で実現できます。
よってこの時点ではTLEにはなりそうになさそう？（Pypy3の場合）

2種類の組み合わせなので、昇順文字列のカウント数 n' から（n' -1 ）*（n ' ）の総和で出力できます。

N=int(input())
count,_sum={},0
for i in range(N):
  S = ''.join(sorted(list(input())))
  if S in count: count[S]+=1
  else: count[S]=1

for j in count.values():
  _sum+=j*(j-1)/2
print(int(_sum))

C問題（ABC123）

  • 難易度：茶
  • 時間：15分

atcoder.jp

定員が存在する5つの交通機関に乗せてN人の最短輸送時間を調査する問題。
ここで鍵になるのは最小定員となる交通機関。ここがボトルネックとなりますから、
wait = N を 最小定員で除した値の切り上げ値が0だと誰も待たず5分で全員到着します。
なのでwait + （5-1）で算出できます。

ただ1≤N,A,B,C,D,E≤10**15でmath.ceilをすると桁落ち・情報落ちが発生しそうなので避けるべきかもしれません。

import math
N=int(input())
lis = []
for i in range(5):
  lis.append(int(input()))
if N<=min(lis): print(5)
else: print(math.ceil(N/min(lis))+4)

C問題（ABC126）

  • 難易度：茶
  • 時間：15分

atcoder.jp

N面の等確率サイコロを振りながら、1≤N≤K-1の場合、2倍 or 0倍にできるコインを振り続けるゲームにて最終的にK以上の値を出せる確率を導き出す問題です。

3面サイコロの出た目が 1のとき、得点が 10以上になるためには、 4回コインを振って 4連続で表が出る必要
( 1 / 3 ) * ( 1 / 2 )** 4 = 1/48

サンプル例に倣ってこのコインを振る回数を式変形で導き出してやるとあとは確率の総和で解けます。

import math,sys
N,K=map(int,input().split())
count=0
for i in range(N):
  if (i+1)<K: 
    count+=(1/N)*0.5**math.ceil(math.log(K/(i+1),2))
  else:
    count+=((N-K+1)/N)
    break
print(count)

C問題（ABC122）

  • 難易度：茶
  • 時間：30分

atcoder.jp

長さ1≤N≤10**5の文字列Sに対して[l:r]の区間に部分文字列が含まれているかをQ（1≤Q≤10**5）回行う問題です。
普通に解けばTLEになります。

なので工夫した点としては・・・
累積和配列を駆使して、N個の要素配列に部分文字列が何個確認できたか、i 番目時点での累積を格納します。

ACAC → 0.1 , 1.0 , 1.1 , 2.0

l : r = 1 : 3 → round(1.1) - round(0.1) = 1
l : r = 2 : 3 → round(1.1) - round(1.0) = 0

上記のように'AC'文字列途中の要素に0.1を格納します。
これにより[ l : r ]の区間での文字列 ' AC ' をカウントする際に、境界に部分文字列の一部を含んでいたとしても、部分文字列数を調査できます。
アイデア自体はすぐに思いついたのですが境界条件の処理に手こずりWAを出してしまいました。

import math
N,Q=map(int,input().split())

S=input()
lis=[0 for i in range(N)]
count=0
for i in range(1,N):
  if S[i-1]+S[i]=='AC':
    count+=0.1
    lis[i-1]=count
    count+=0.9
    lis[i]=count
  lis[i]=count

for i in range(Q):
  l,r=map(int,input().split())
  count=int(round(lis[r-1],0)-round(lis[l-1],0))
  print(count)