ABC199参戦記

突然の宣伝ですが、Webアプリ作成しました。
AtCoder Find Rivals
現在のユーザ情報から、レート、最高レート、参加回数を考慮して、自分と似た状況のユーザを確認できます。

前回のPanasonicさんの協賛したABCの記事でも書きましたが、Panasonicさんの主催、協賛しているコンテストではすべてレートを下げている私は今回のABC199でレートを上げることができるでしょうか。

この記事は、茶色の下位から中位程度の私が、自分で理解した内容を書いていきます。
Python3のACコード付きです。

A – Square Inequality

標準入力とif文、比較演算子、累乗計算の利用などが出来るかを問われる問題。

Python3の標準入力は input() を利用し、1行に複数の値を受け取る場合には map() を利用するのが良いと思います。

Python3である数の二乗を計算したい場合、私が知っている方法は3つの方法があります。
例えば、10² は、

• 10*10
• 10**2
• pow(10,2)

これらの中から好きなものを選んで問題文中にある数式を判定すればOKです。
私はコンテスト中は、一番上のタイプで提出しました。

# AtCoder Beginner Contest 199（Sponsored by Panasonic）
# A - Square Inequality

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

if A*A+B*B<C*C:
    print("Yes")
else:
    print("No")

勿論、こちら(↓)でも、

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

if A**2+B**2<C**2:
    print("Yes")
else:
    print("No")

これ(↓)でもACします。

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

if pow(A,2)+pow(B,2)<pow(C,2):
    print("Yes")
else:
    print("No")

B – Intersection

問題に書かれている内容を理解し、プログラムに表現できるかを問われる問題。
または、与えられた条件に当てはまる部分を図などに書いて理解し、答えになる数を求める問題。
私は、図で書いて理解したつもりになっていましたが、サンプルが合わずに、結局imos法で解きました。

まずは、公式の解説にも書いてある通り、書いてある通りを実装して、xの取りうる値の範囲を全探索して、条件に合う個数をカウントしていく方法です。

# AtCoder Beginner Contest 199（Sponsored by Panasonic）
# B - Intersection

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

ans=0

for x in range (1,1001):
    for i in range (N):
        if x<A[i] or B[i]<x:
            break
        else:
            pass
    else:
        ans+=1
print(ans)

自分で書いていて、ちょっとわかりにくいコードになっていますが、xを全探索したコードはこういう形になると思います。

次に、条件に合うような x を考えるのに、図を書いてみます。

いろいろなパターンを書いていくと、数列Aの最大値と数列Bの最小値に挟まれている部分が答えになることがわかります。
これは、min(B)-max(A)+1で求まります。入力例2のような場合、マイナスの値になるため、その場合の答えは0になります。

以上から、次のコードでACとなります。

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
print(max(0,min(B)-max(A)+1))

私はコンテスト中に何を思ったのか、 print(max(0,min(B)-max(A)+1)) ここを print(max(0,min(B)-max(A)+2)) としてしまい、サンプルも合わず、焦ってこの方針を放棄してしまいました。

最後に、私がACした方針です。
xの取りうる範囲の配列を用意して、各ｎに対して、A[N]からB[N]までの範囲を+1していきます。
最終的に、xの取りうる範囲のうち、N回+1されている。つまり、配列の値がNになっている個数が答えになる。という方針です。

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

x=[0]*1010

for i in range (N):
    for j in range (A[i],B[i]+1):
        x[j]+=1
print(x.count(N))

上記コードでもこの制約下ではTLEしないことを確認していますが、二重ループの部分が計算量が多くなる要因となり、TLEする可能性があると思い、私はimos法を利用しました。

imos法は連続する区間にある数を足すのを複数回繰り返すときに二重ループを引き起こさずに計算できる手法です。
ABCのC問題やD問題では出てくるような手法で、B問題にはオーバーな感じも否めませんが、これで突き進みました。

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

x=[0]*1010
for a,b in zip(A,B):
    x[a]+=1
    x[b+1]-=1

ls=[0]
for i in range (len(x)):
    ls.append(ls[-1]+x[i])

print(ls[2:].count(N))

ちなみに、AとBの取りうる範囲であるxの範囲を、Nの範囲と見間違って、100で作ってRE出しました。
制約はよくよく確認しましょう！
計算量の見積もりという意味でも、必要なデータの作成という意味でも、解法の手がかりを考えるのにも制約はよく見ましょう。

C – IPFL

効率よくデータを扱うことが出来るかを問われる問題。

文字列の入れ替え、特に、前半と後半を入れ替える時に、状態をうまく管理することや、変数として持っているデータのスワップ(交換)を素早くできるかが重要な問題になります。

私はこの問題を解けませんでしたが、前半部分(head)と後半部分(tail)を別のデータにもっておき、データを交換するときは、 head,tail=tail,head とすればよいと言うのを見て解けました。

あとは、1文字入れ替えする場合は、対象となる文字をまずは解く指定して、
AとBが前半部分と後半部分のどちらに含まれているかを判断し、3つの場合分けを書けばよいことがわかります。(制約より、A<Bのため、N<Aの場合、必ずN<Bになるため。)

# AtCoder Beginner Contest 199（Sponsored by Panasonic）
# C - IPFL

N=int(input())
S=list(input())
Q=int(input())

head=S[:N]
tail=S[N:]

for _ in range (Q):
    T,A,B=map(int,input().split())
    if T==1:
        if A>N:
            swap1=tail[A-N-1]
        else:
            swap1=head[A-1]
        if B>N:
            swap2=tail[B-N-1]
        else:
            swap2=head[B-1]
        
        if A>N:
            tail[B-N-1]=swap1
            tail[A-N-1]=swap2
        else:
            if B>N:
                tail[B-N-1]=swap1
                head[A-1]=swap2
            else:
                head[B-1]=swap1
                head[A-1]=swap2
    if T==2:
        head,tail=tail,head

print(''.join(head)+''.join(tail))

というわけで、今回”も”Panasonicさんの協賛のコンテストでレートが下がりました。
しかも今までで一番減り幅も大きかったです。

• ABC186:-25
• ABC195:-26
• ABC197:-27
• ABC199:-34　←今回

悔しいので、精進します。