ABC184参戦記

今回のABC184の前日に出たARC108はA問題だけで終わりましたが、ちょっとレートが上がりました。
現在茶色ですが、また今回もC問題が解けなかったりするとまた灰色に戻りそうな予感がしています。

本記事は、茶色になった後に灰色に戻ったり、また茶色になったりするくらいのレベル感の私がABCのAからC問題までを、私が理解する言葉で書いていきます。
もしかすると、始めたばかりの方の役に立つかもしれないし立たないかもしれない、解説ブログです。
使用言語はPython3です。

A – Determinant

標準入出力と四則演算を問われる問題。

競技プログラミングを始めたばかりのころは、1行に2つ以上の入力を受け取るのに苦労しましたが、mapを利用するのが良いと思います。

あとは、行列式を四則演算したものをprintすればOKです。
行列式については問題文に書いているのでそのまま利用すれば良いですね。

# AtCoder Beginner Contest 184
# A - Determinant

a,b=map(int,input().split())
c,d=map(int,input().split())

print(a*d-b*c)

B – Quizzes

繰り返し処理と条件分岐が書けるかを問われる問題。

for文で繰り返し処理を実行していき、”x”の時に、今の点数から-1します。この時に、今の点数が負の数になってしまった時には0にします。

これは、

N=0
N-=1
if N<0:
    N=0
print(N)　// ->0

としてもよいのですが、以下のコードでも同じことが実現できます。

N=0
N=max(0,N-1)
print(N) // ->0

ABC183の解き方を復習している時に見つけた書き方です。
ABC183-A ReLU もこの解き方で解いている方もいらっしゃったので、それを使ってみました。

その他、”o”と”x”を違う文字列として書いてしまうなどの失敗談も聞くことがあるので、入力例をコピーして使用する。という注意点もありますかね。

あとは、上記の通り、for文と条件分岐を書けばOKです。

# AtCoder Beginner Contest 184
# B - Quizzes

N,X=map(int,input().split())
S=input()

for i in range (N):
    if S[i]=="x":
        X=max(X-1,0)
    else:
        X+=1

print(X)

C – Super Ryuma

偶奇判定の知識を問われる問題と、場合分けをしっかり考察できるかの問題。

今回もC問題解けませんでした。全然ダメでした。C問題にしては難しめの問題だったようですね。

まずは、問題文に書かれているコマの動きを理解するのに非常に苦労しました。

• a+b=c+da+b=c+d
• a−b=c−da−b=c−d
• |a−c|+|b−d|≤3

上の2つの条件は斜め移動が無制限にできる事を、3つ目はマンハッタン距離3まで動けることを示しています。

さて、斜めに移動が無制限にできるということは、チェス盤のような市松模様で塗られた白、または黒にある駒は同じ白、または黒のマスまで2手で移動できます。チェスのビショップを思い浮かべてもらうとわかりやすいと思います。
将棋の角も同じ動きをしますが、将棋盤は市松模様に塗られていないのでチェス盤の方がわかりやすいと思います。

今回の駒(超竜馬)は近場なら縦横移動も可能なので、市松模様の異なる色へも移動することが可能です。

これらのことより、任意のマスまで、3手あればたどり着くことが可能なことまではわかりました。

これらの場合分けをして考えていきます。

0手で任意のマスに到達

初期のマス(r1,c1)が(r2,c2)と同じ場合は何もしないで良いので、0回が答えになります。

1手で任意のマスに到達

初期のマス(r1,c1)から、問題文に記載の動けるマスの条件から判定してtrueになるなら1が答えになります。

2手で任意のマスに到達

2手で動ける範囲は、市松模様のゲーム盤を考えた時に、同じ色のマスの他、
1手目でマンハッタン距離3まで動いた後にもう一度、上記1手で任意のマスに到達できるかを判定して、trueになれば答えは2になります。
実装上は、まず、市松模様のゲーム盤で同じ色であることを判定するには、マス目の縦横の座標を足して2で割った余りが一致しているかを確認すればOKです。
次に1手目でマンハッタン距離3まで動いた場合の移動の配列を用意して、そこから全探索していくことで2手で任意のマスに到達できるかの判定が可能になります。

3手で任意のマスに到達

2手でいけない場合も、3手あればすべてのマスに到達できることはわかっているため、上記2手までで答えが出なければ、答えは3になります。

# AtCoder Beginner Contest 184
# C - Super Ryuma

# 動けるマスの判定関数
def canSuperRyumaMoveCell(a,b,c,d):
    if a+b==c+d:
        return True
    if a-b==c-d:
        return True
    if abs(a-c)+abs(b-d)<=3:
        return True
    else:
        return False

r1,c1=map(int,input().split())
r2,c2=map(int,input().split())

# 0手で任意のマスに到達
if (r1,c1)==(r2,c2):
    print(0)
    exit()

# 1手で任意のマスに到達
if canSuperRyumaMoveCell(r1,c1,r2,c2):
    print(1)
    exit()

# 2手で任意のマスに到達_1
if (r1+c1)%2==(r2+c2)%2:
    print(2)
    exit()

# 2手で任意のマスに到達_2
firstMove=[[-3,0],[0,-3],[3,0],[0,3],[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],[0,-2],[0,-1],[0,0],[0,1],[0,2],[1,-2],[1,-1],[1,0],[1,1],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]
# print(len(firstMove))
 ->29
for i in range (29):
    r=r1+firstMove[i][0]
    c=c1+firstMove[i][1]
    if canSuperRyumaMoveCell(r,c,r2,c2):
        print(2)
        exit()

# 2手で任意のマスに到達出来なかった場合
print(3)

今回のC問題は苦戦している方多いようで、ABの2完でもレートは下がらずに微増しました。
振り返ると落ち着いて場合分け、一部全探索して判定関数を使用すればコンテスト中に解けたかもしれないな。と思えてくるので悔しいですね。

次回以降、落ち着いて解いていけるようにメンタルも鍛えていきます。