ABC328のA~E問題の解説

ABC328の解説

A問題　Not Too Hard

愚直な実装で通ります。
すべての要素を見ていって、もしその要素の点数がX以下だったら答えの値を格納する変数などに足していけばよいです。

Pythonの自分のコード

n,x=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for i in range(n):
  if a[i]<=x:
    ans+=a[i]
print(ans)

B問題　11/11

愚直にすべての日を見ていけばいいです。
すべての日に対して、その日はゾロ目になっているか…をチェックしていけば答えが分かります。

Pythonの自分のコード

n=int(input())
ans=0
a=list(map(int,input().split()))
for i in range(n):
  for ipp in range(a[i]):
    irane=set()
    hako=list(str(i+1))
    for k in range(len(hako)):
      irane.add(hako[k])
    hako=list(str(ipp+1))
    for k in range(len(hako)):
      irane.add(hako[k])
    if len(irane)==1:
      ans+=1
      
print(ans)

C問題　Consecutive

この問題は累積和を使います。
試しにネットとかで累積和について調べてみると、この問題と似たような問題が出てくると思います（こういう問題はかなり典型的）。

累積和を知らないという人は、この解説を見るより、ネットで調べてみたほうがわかりやすいと思います。

軽く説明しておくと、

i番目の要素までに同じ英小文字が隣あう箇所はいくつあるか…？という情報を格納した配列を作ります。

クエリで渡される　l, r　の値を使って、r番目までに隣り合う箇所の個数からl番目までに隣り合う箇所の個数を引き算してあげると答えがあっというまに求まります。

このような累積和などを使わないと、TLEになってしまいます。

Pythonの自分のコード

n,q=map(int,input().split())
rotti=[0]
s=list(input())
for i in range(1,n):
  if s[i]==s[i-1]:
    rotti.append(rotti[len(rotti)-1]+1)
  else:
    rotti.append(rotti[len(rotti)-1])
for i in range(q):
  a,b=map(int,input().split())
  print(rotti[b-1]-rotti[max(a-1,0)])

D問題　Take ABC

実はこの問題とほとんど同じ問題が前にABCで出ていて、ぼくはその問題のことを思い出し、あっという間にACを出すことができました。

でも、初見の人は結構大変だったと思います。
具体的にどんな解き方をするのかと言うと、

１　stackを用意する（普通の配列でもいい）
２　stackにSの要素を順番に追加していく
３　stackに要素を追加するたびに、stackの後ろから３文字がABCになっていないかチェックする。
→もしABCのになっていたら後ろから要素を３つけす（ABC）を消す。

…これを繰り返していけば短い時間で解くことができます。
愚直な方法で実装するとTLEになってしまうので気をつけましょう！

Pythonの自分のコード

s=list(input())
rotti=[]
count=0
for i in range(len(s)):
  rotti.append(s[i])
  count+=1
  if count>=3 and rotti[count-1]=="C" and rotti[count-2]=="B" and rotti[count-3]=="A":
    rotti.pop()
    rotti.pop()
    rotti.pop()
    count-=3
hako=""
for i in range(len(rotti)):
  hako+=rotti[i]
print(hako)

E問題　Modulo MST

この問題には色々な解き方がありますが、自分はかなり簡単な方法で解いたと思います。

例えば、全域木を作る時って、辺の数は頂点−１個でOKなんです。
これを理解すればもう大丈夫！

最初に頂点の数がNとして渡されるので、N-1個、辺を選ぶ方法をとっていけばOKです。
その選ぶ方法で全域木になっていたら最小値をどんどん更新していく…という方法をとればACが出ます。

（辺の数がN-1個だからといって必ず全域木にはならないけど、辺の数がN-1個になるグラフすべてを全探索するのは間に合うのでこの方法で良い）

辺の選び方はコンビネーションになるわけですが、PythonとかC++にはそのモジュールなどがあるので、ネットで調べてみてください（Python　組み合わせ　求め方…みたいな感じで）。

Pythonの自分のコード

from itertools import combinations
n,m,k=map(int,input().split())
line=[]
test=[]
ans=100000000000000000000000000
for i in range(m):
  test.append(i)
for i in range(m):
  line.append(list(map(int,input().split())))
box=list(combinations(test,n-1))
for apya in range(len(box)):
  hako=box[apya]
  rotti=[[]*1 for i in range(n)]
  amount=0
  for ipp in range(len(hako)):
    a=line[hako[ipp]][0]
    b=line[hako[ipp]][1]
    c=line[hako[ipp]][2]
    rotti[a-1].append(b)
    rotti[b-1].append(a)
    amount+=c
  iti=0
  stack=[1]
  irane=set([1])
  while len(stack)>iti:
    for i in range(len(rotti[stack[iti]-1])):
      if rotti[stack[iti]-1][i] in irane:
        continue
      stack.append(rotti[stack[iti]-1][i])
      irane.add(rotti[stack[iti]-1][i])
    iti+=1
  if len(irane)!=n:
    continue
  ans=min(amount%k,ans)
print(ans)

最後までありがとうございました。

rotti-coder.hatenablog.com