ABC175参戦記

1週間ぶりのABC。

今日はPCを新調(中古ですけど・・・)して、いろいろセッティングしていたのですが、やりたいことが順調に行っていたので、その調子でABCも順調に解けると良いな。と思って臨んだABC175。

ここ最近ずっとC問題がコンテスト中に解けていないですが、今回は解けるのか！？

A – Rainy Season

標準入出力と、if文の問題。

3文字からなる文字列を受け取って、Rが連続する回数によって出力内容を分岐させる問題。

3文字で、文字の種類は2つなので、すべての組み合わせを考えても2**3の8通り。
これらすべてをif文で書いてもOKですが、
私は、Rが3回連続する(RRR)の場合、Rが2つ連続する2通り(RRS or SRR)の場合、Rが一つもない場合(SSS)、その他(Rが連続するのは1回)という分け方をしました。

# AtCoder Beginner Contest 175
# A - Rainy Season

S=input()
if S=="RRR":
    print(3)
    exit()
if S=="SRR" or S=="RRS":
    print(2)
    exit()
if S=="SSS":
    print(0)
    exit()
else:
    print(1)

下に、この問題の文字数が可変の場合、制約がきつくなった場合に対応するコードも記載しています。

B – Making Triangle

for文での全探索を書けるかの確認と、三角形の成立条件を問われる問題。

問題を見た瞬間に、「精進で似たものを解いたことがあるな。」と思った問題でした。

ABC143-D Triangles

それにもかかわらず、解くのに50分かかりました・・・

三角形の成立する条件は、各辺の長さをa,b,cとした時に、以下の条件が成り立つことです。(数学的な証明はこちらを参考にしてください。)

• a+b>c
• b+c>a
• c+a>b

a<=b<=cであれば、a+b>cの条件のみを確認すれば良いことになるので、判定が楽になります。

「同じ長さのものがあったらNG」の条件部分を書くのに苦戦していました。
序盤はここの条件を読み取れていなくて、サンプルが合わなく、泣きそうになっていました。
サンプルが合わなくて、与えられた配列をソートしたらダメだと無駄な勘違いしていたり、いろいろと迷走していましたね・・・。

「同じ長さのものがあったらNG」という条件については、
各辺の長さを短いほうからa,b,cとした時に、
a<b<c
となれば良いことに気づくのにものすごい時間を要しました。

コンテスト中に通したコードはこちら。
3辺を選択した後、無理やりa<=b<=cにしています。

# AtCoder Beginner Contest 175
# B - Making Triangle


N=int(input())
L=list(map(int,input().split()))

ans=0

for i in range (N):
    for j in range (i+1,N):
        for k in range (j+1,N):
            a=min(L[i],L[j],L[k])
            c=max(L[i],L[j],L[k])
            b=(L[i]+L[j]+L[k]-a-c)
            if a+b>c and a<b<c:
                ans+=1

print(ans)

この問題は、上記の通り、過去の精進でもう少し制約が厳しいものを解いているので、もう少し早く解きたかったです。

この問題も制約がきつくなった場合にも対応できるコードを下に書いています。

C – Walking Takahashi

割り算(商と剰余)と、偶奇判定の問題。

今回もC問題解けませんでした。惜しいところまで行ったのですが、WAが5ケースあってコンテスト中に解けませんでした。
コンテスト後、少し見直して提出したらあっさりACしました。
B問題で時間かかってしまって、焦っていたので、焦らずに解けるようにしたいですね。

この問題は、以下のように読み替えるとイメージしやすいです。
(最近こどもとスゴロクで遊んだからだと思います。)

ゴールまでのマス目がXあるスゴロクを、Dしか目が出ないサイコロをK回ふって一人で遊びます。
K回サイコロを振った時に、ゴールまでの距離はいくつですか？
ただし、ゴールを超える目が出た際には戻るものとして、ゴールについたとしてもK回までサイコロをふらないといけません。

距離(マス目)はXで、正負は関係ないため、もしもXがマイナスの値だった場合も絶対値で正の数字に直します。

K回サイコロを振って、ゴールを目指しますが、K回振ってもゴールまでたどり着けない場合は、X-(K*D)がゴールまでの距離で、その数が答えになります。

次に、ゴールまでひたすらサイコロを振り続けて、ゴール手前(orちょうどゴール)にたどり着くのは、X÷Dの商(q)回目で、その時の残りの距離はX÷Dの余り(r)の部分です。

ここまできたら、あとはK回まで何回残っているかを調べて、

偶数回であれば、その地点からゴールに近づいて終了することはできません。偶数回ゴールを目指して移動した時の着地点は、abs(abs(r-D)-D)となり、r<D , r>=0,D>0から、結果的にrと等しくなります。

奇数回であれば、一回ゴールに向けて進んだ(ゴールを通り越した分は戻る。)マスで、r=abs(r-D)として、残り回数が偶数回になり上記の通り、その地点から良い場所には動けません。(上記条件のr<Dの部分がr<=Dとなる場合がありますが、結果は変わりません。)

以上をコードにしていけばOKです。

# AtCoder Beginner Contest 175
# C - Walking Takahashi

X,K,D =map(int,input().split())

X=abs(X)

q=X//D
r=X%D

if K<=q:
    print(X-K*D)
    exit()

else :
    if (K-q)%2==0:
        print(r)
    else :
        print(abs(r-D))

コンテスト中に落ち着いてここまできれいに整理しきれていたら解けたと思うと悔しいですね！

次こそはC問題クリアしたいです。

毎回言っているな私・・・

Appendix ～おまけ～

A – Rainy Season (別解:文字数が可変の場合のコード)

今回はA問題ということもあり、3文字なので、すべての場合分けや、パターンを比較的簡単に書き出すことができましたが、文字数が変動する場合はすべてを書き出すのは不可能なので、それに対応するようなコードとしては、以下のようなもので対応可能です。
次のコードの計算量はO(N**2)のため、文字数が10**3くらいまでは通ると思いますが、それ以上になるとTLEします。

# AtCoder Beginner Contest 175
# A - Rainy Season

S=input()

ans=0

for i in range (len(S)):
    if S[i]=="R":
        tempans=1
        for j in range (i+1,len(S)):
            if S[i]==S[j]:
                tempans+=1
            else:
                if tempans>ans:
                    ans=tempans
                break
        else:
            if tempans>ans:
                ans=tempans
print(ans)

このコードはRが連続した部分の2個め以降は必ず結果が悪くなるので、無駄な処理をしています。
直感的にわかりやすいと思うのは上記のコードですが、文字数が多くなると実行時間が長引きます。

次のコードは文字数が10**7くらいまで耐えれるはずです。(計算量はO(N)です。)

# AtCoder Beginner Contest 175
# A - Rainy Season

S=input()

ans=0
count=0

if S[0]=="R":
    count=1

for i in range (1,len(S)):
    if S[i]=="R":
        if count>0:
            pass
        else:
            count=1
        if S[i-1]=="R":
            count+=1
        else:
            if count>ans:
                ans=count
                count=0
else:
    if count>ans:
        ans=count

print(ans)

いずれのコードも、Pythonはfor文の最後に実行するelseが便利です。

この問題の別解は、ABC139-C – Lowerを解いたことで書くことができました。

B – Making Triangle (別解:制約が10**3の場合にTLEしないコード)　

3重ループは、Nが100(10**2)までの場合は耐えられますが、1,000(10**3)ではTLEします。
Nが10**3の場合、2重ループで最長の辺になりえる数を二分探索で探します。

# AtCoder Beginner Contest 175
# B - Making Triangle

import bisect

N=int(input())
L=list(map(int,input().split()))

L.sort()

ans=0

for i in range (N):
    for j in range (i+1,N):
        if L[i]==L[j]:
            pass
        else:
            ab=L[i]+L[j]
            c=bisect.bisect_left(L,ab)
            bequalc=bisect.bisect_right(L,L[j])
            ans+=c-(bequalc)

print(ans)

上で書いたABC143-D Triangles を解くためには、この二重ループの中で二分探索する必要が出てきます。

計算量は、ソートにO(NlogN)、二重ループでO(N**2)、二分探索で(NlogN)となり、ボトルネックは二重ループ部分であることがわかります。