ABC321の解説

ABC321のA~D問題の解説

ちなみにサンプルのコードは毎度のことながらクソコードです。ごめんなさい…

A問題　321-like Checker

この問題は、入力を前から順番に見ていって、減少していないところがないか確認していって、その結果を出力すればよいです。

Pythonの例

n=list(input())
check=0
for i in range(len(n)-1):
  if n[i]<=n[i+1]:
    check=1
    break
if check==0:
  print("Yes")
else:
  print("No")

B問題　Cutoff

やり方によっては、計算することによって答えを求めることもできると思いますが、ぼくは考えるのが面倒だったので、全探索することにしました。

一つのラウンドでは０〜１００点までしか取ることができないので、その中を全探索します。引数をNラウンド目のスコアとして最終結果がX以上になるかどうかを判定する関数などをつくって判定していくのが便利だと思います。

０〜１００点の順番で探索していくので、いちばん最終結果がX以上になる値が答えとなる値の最終点となります。

Pythonの例

n,x=map(int,input().split())
a=list(map(int,input().split()))


def rotti(a):
  a=sorted(a)
  count=sum(a)
  return count-a[0]-a[len(a)-1]

check=0
for i in range(0,101):
  a.append(i)
  if rotti(a)>=x:
    saisyou=i
    check=1
    break
  a.pop()
if check==0:
  print(-1)
else:
  print(saisyou)

C問題　321-like Searcher

この問題は、コンテスト中、自分は全く解き方が思いつきませんでした…ですので、何重ループもして321like Numberをすべて生成する…ということをしていました。

実際のところはそんな変なことをする必要がなく、もっといい方法がありました。

その方法は「bit全探索」です。

最初に"9876543210"というふうに単調減少になるように数字を並べ、そこからbit全探索を行います。
このとき、10桁のbitを生成するようにし、どの数字を使うか使わないかを0と1を使って管理するようにします。

（例えば0010101010みたいな）
→このようなときは、7531が生成されます。

このように、どんなbitを生成しても、かならず321like=numberができます（すべてを選択しないというものを除く）。

このように321like-Numberをすべて列挙し、その後ソートすればかんたんにN番目の321like-Numberを出力することができるということです。

Pythonの例

#321like-Numberを全部列挙する

s="9876543210"

bit=["0","1"]
iti=0
while len(bit[iti])<10:
  bit.append(bit[iti]+"0")
  bit.append(bit[iti]+"1")
  iti+=1
bit=bit[iti+2:len(bit)]

#スライスでiti+2を指定したのは、"0000000000"と"0000000001"(←0)を削除するため

a=[]
for i in range(len(bit)):
  box=bit[i]
  hako=""
  for ipp in range(len(s)):
    if box[ipp]=="1":
      hako=hako+s[ipp]
  a.append(int(hako))
a=sorted(a)
print(a[int(input())-1])

D問題　Set Menu

この問題は、「二分探索とか累積和で解いた！」と話していた人をおおく聞きましたが、ぼくは違う方法でやりました（たぶん）。

と、いうのも、この問題を最初に見たときに鉄則本で見た「たされた回数を記録しておく…」という解き方がぱっと思いついたからです。

そのままといえばそうなのですが、一応説明を入れてみます。

まず、Pという値がないとしましょう。つまり、どんな値段になったとしても、一つのメニューの値はAの一つの値とBの一つの値の和とする…ということにします。

このときの場合は計算は非常にかんたんです。
Aの一つの値は合計でM回足され、Bの一つの値はN回足されます。

次にこの考え方を使って、もう一度D問題を見てみます。

基本的にはこの考え方を使いたいのですが、P円を超えてしまう場合はP円にしなくてはなりません。
そこでAとBの値をあらかじめソートしておき、Aiの値で全探索します。

どういう全探索をするかというと、Bの値を二分探索します。Ai円と足して、P円を超えない範囲を探します。

そうするとAi円が何回使われるか、Bi円が何回使われるか、P円が何回使われるか…がわかります。

また、ここで一つ問題があります。というのも、Ai円が何回使われるかはかんたんに記録をつけることができますが、Bi円が何回使われるかを記録するのはめんどくさいです（例えば1~10000番目までが大丈夫だとすると、1000回の計算が必要…みたいなことです）。単純に記録をつけていってしまうとTLEしてしまうので工夫が必要です。

ここでぼくは”いもす法”という考え方（？）を使うことにしました。

ここまでの文章を見たらわかるとおりぼくは説明がめちゃくちゃ下手なのでここは流石にネットで調べてみたほうがいいと思います（ごめんなさい）。

Pythonの例

import bisect
n,m,p=map(int,input().split())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))


amount=[0]*n

imos=[]
count=0

for i in range(n):
  hako=bisect.bisect(b,p-a[i])

  count+=m-hako
  amount[i]+=hako
  imos.append(hako)

ans=count*p

for i in range(n):
  ans+=a[i]*amount[i]

amount=[0]*m
count=len(imos)
imos=sorted(imos)
iti=0
for i in range(m):
  while iti<len(imos) and i== imos[iti]:
    count-=1
    iti+=1
  amount[i]=count

for i in range(m):
  ans+=b[i]*amount[i]
print(ans)

解説はおしまいです。ぼくはD問題までしか解けなかったのです…

最後までありがとうございました！いつものことながら説明が冗長だったりして読みにくいと思いますが、少しでも参考になればうれしいです…！

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