ABC314の解説

ABC314のA～D問題の解説を書いてみました。

いろいろと忙しくて、書くのが遅くなってしまい、次のABCの日に公開することになりました...　今回も、解説には全く自信がありません…でも、分からなくなった時に公式の解説を見る前にヒントとしてみる分にはいいかもしれないですね！

A問題　3.14

この問題にはいろいろな解き方があると思いますが、今回は自分のやった方法一つだけを紹介してみます。
この問題の制約では、最大で小数第100位までを出力することになりますが、すでに問題文に円周率小数第100位までの値がのっているので、それをコピーし、リストに入れて、それを入力の値に合わせていい感じに出力すればACが出ます。

また、Nの値は１～100までなので、必ず最初の「3.1」の部分は出力することになるので、ここを先に出力してもいいかもしれませんね。

（説明が雑な気がします…ごめんなさい）

Pythonの例

s="1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"
s=list(s)
print("3.",end='')
n=int(input())
for i in range(n):
  print(s[i],end='')
print()

B問題　Roulette

この問題では、「X」に賭けていた人全員を出力するのではなく、その中で賭けていた目の数が少ない人を出力する必要があります。
ですから、まず先に「X」に駆けていた人の番号と、その人の賭けていた値の数を格納する二次元リストを作成し、その後ソートしてあげることによって、賭けていた目の数の最小が分かります。

↓このような二次元配列にしてあげることによって、ソートしたときにうまくいきます。

[[賭けていた値の数,その人の番号],[賭けていた値の数,その人の番号],[賭けていた値の数,その人の番号].......]

Pythonの例（全然参考にならないコードだと思います…）

n=int(input())
rotti=[[] * 1 for i in range(n)]
ans=[]
for i in range(n):
  c=int(input())
  rotti[i]=list(map(int,input().split()))
x=int(input())
for i in range(n):
  if x in rotti[i]:
    ans.append([len(rotti[i]),i+1])
ans=sorted(ans)
if len(ans)==0:
  print(0)
  print()
  exit()
rotti=[ans[0][1]]
mae=ans[0][0]
for i in range(1,len(ans)):
  if mae==ans[i][0]:
    rotti.append(ans[i][1])
print(len(rotti))
print(*rotti)

C問題　Rotate Colored Subsequence

これは特別なアルゴリズムは必要なく、ただ実装するだけの問題です。

…ごめんなさい。これ以上の説明が思いつきませんでした…許して😢

Pythonの例

n,m=map(int,input().split())
s=list(input())
c=list(map(int,input().split()))
rotti=[[] * 1 for i in range(n)]
for i in range(len(s)):
  rotti[c[i]-1].append(s[i])

amount=[-1]*n
for i in range(len(c)):
  if amount[c[i]-1]==-1:
    print(rotti[c[i]-1][len(rotti[c[i]-1])-1],end='')
    amount[c[i]-1]+=1
  else:
    print(rotti[c[i]-1][amount[c[i]-1]],end='')
    amount[c[i]-1]+=1
print()

D問題　LOWER

この問題では、愚直に実装してしまうとTLEになってしまいます。ですからなにかいいアルゴリズムを考える必要があります。
この問題では、各文字に対して以下のような二通りの状態があります（なんか言葉が変な気がするけど…）。

・その要素が変更されたときと大文字、小文字が同じ。
・すべての要素を一斉に大文字か小文字に変更されたときの状態と同じ。

ですから、各要素に対してどちらの状態であるかを記録しておけば大丈夫です。
（僕の場合は、すべての要素を一斉に大文字、小文字に変えるクエリにあってない要素の番号をSet型に格納しました）

Pythonの例

t=int(input())
s=list(input())
n=int(input())
amount=-1
irane=set()
for i in range(n):
  a=list(input().split())
  if a[0]=="1":
    s[int(a[1])-1]=a[2]
    irane.add(int(a[1])-1)
  else:
    irane=set()
    if a[0]=="2":
      amount=0
    else:
      amount=1
if amount==-1:
  for i in range(len(s)):
    print(s[i],end='')
  print()
  exit()
for i in range(len(s)):
  hako=s[i]
  if i in irane:
    print(hako,end='')
  else:
    if amount==0:
      print(hako.lower(),end='')
    else:
      print(hako.upper(),end='')
print()

最後までよんでくれてありがとうございました！自分で見返しても思うのですが、やっぱり説明が下手くそだったり、例として載せているコードが全く参考にならなそうな気がしたり、とにかく全然よくないきがします…
それでも最後まで読んでくれてありがとうございました！

↓自分の書いたページをまとめているところ
rotti-coder.hatenablog.com