自己分析 #2。【ABC201を振り返る】

こんにちは、こんばんは。現役<font color="brown">茶色</font>コーダーの<b>Rute</b>です。
今回は自己分析2回目ということで、<b>ABC201</b>を振り返りたいと思います。
#1.結果
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530417/6390da09-0757-5cc2-24f8-7422ef8b0062.png)

レーティングは<b>-10</b>という結果に。2完早解きで、Cの解答者数がそこまで多くなかったことから、マイナスの幅を抑えることが出来ました。

#2 各問題考察
## 2.1 A問題「Tiny Arithmetic Sequence」
Difficulty: <font color = "grey"> 12</font>

ソートして<b>A[2] - A[1] = A[1] - A[0]</b>を検証すれば良いです。

<details><summary>Python3での解答例</summary><div>

```{ABC201A.py}
A = list(map(int,input().split()))
A.sort()
if (A[2]-A[1]) == (A[1]-A[0]):
    print("Yes")
else:
    print("No")
```


</div></details>

または、Pythonの標準ライブラリである`itertools.permutations`を用いて$A$の全ての順列について全通り条件を満たすか判定する、という方法でも良さそうです。

<details><summary>Python3での解答例2</summary><div>

```{ABC201A.py}
from itertools import permutations
A = list(map(int,input().split()))
X = list(permutations(A))
f = 0
for i in X:
    i = list(i)
    for j in range(3):
        if i[2]-i[1] == i[1] - i[0]:
            f += 1
if f >= 1:
    print("Yes")
else:
    print("No")
```


</div></details>


## 2.2 B問題「Do you know the second highest mountain?」
Difficulty : <font color = "grey"> 32</font>

この問題は、各$S_i,T_i$を入れたリストを昇順ソートして、ソートした数列における最後から2番目の値における$T_i$を出力すれば良いです。
ただ、個人的な解法としては、$S_i = -S_i$というように再定義し、その条件のもとで昇順ソートして、ソートした数列における2番目の値における$T_i$を出力する、という解法を行いました。
いずれにせよ、計算量は$O(NlogN)$なのですが。
(<font color = "Grey">解答例に`collections`がimportされていますが、`collections`を使わずとも解くことが出来たので無視して下さい。)
<details><summary>Python3での解答例</summary><div>

```{ABC201B.py}
import collections
d = []
N = int(input())
for i in range(N):
    S = input().split()
    d.append([-int(S[1]),S[0]])
d.sort()
print(d[1][1])
```


</div></details>

これは他の方もSNSで発言されていたと思いますが、過去に同類の問題がABCに出題されたことがあります。

>AtCoder Beginner Contest 128 「Guidebook」<br>https://atcoder.jp/contests/abc128/tasks/abc128_b

この問題のDificultyは<font color="grey">350</font>と、灰色上位のレベルでした。
確かにこの問題における「名前順にソートし、名前が同じ場合は 点数が高いものでソートすればよい」というものが今回のB問題と似ていたのは事実なのですが、明らかにDifficultyが落ちています。
(今回の問題は$S_i$のみを考慮し、さらに$S_i \neq S_j (i \neq j)$という制約があったため、それでDifficultyが下がったのかもしれないですが)

## 2.3 C問題「Secret Number」
Difficulty : <font color="Brown">439</font>
この問題は、最初組み合わせの問題かと思って様々なことを考えました。
事実、組み合わせでも解けるらしいですが、<b>全探索</b>で解けることを気づかず90分間椅子を暖めていました...
▼解説ACしました。
<details><summary>Python3での解答例</summary><div>

```{ABC201C.py}
S = list(input())
ans = 0
if S.count("o") >= 5:
    print(0)
else:
    zettai = S.count("o")
    zettai_number = []
    if zettai >= 1:
        for i in range(10):
            if S[i] == "o":
                zettai_number.append(i)
        for i in range(0,10000):
            K = str(i).zfill(4)
            f = 0
            out = 0
            checked = [0 for i in range(zettai)]
            for j in range(4):
                if S[int(K[j])] == "o":
                    checked[zettai_number.index(int(K[j]))] += 1
                elif S[int(K[j])] == "?":
                    continue
                else:
                    out += 1
                    break
            if out == 0 and min(checked) >= 1:
                ans += 1
        print(ans)
    else:
        for i in range(0,10000):
            K = str(i).zfill(4)
            out = 0
            for j in range(4):
                if S[int(K[j])] == "?":
                    continue
                else:
                    out += 1
                    break
            if out == 0:
                ans += 1
        print(ans)
```


</div></details>

## 2.4 D問題「Game in Momotetsu World」
Difficulty : <font color="#00C0C0">1317</font>
この問題は、幅優先探索で考えた方が良いのかな...と思ったのですが、解説を見たところDPだったようです。
DP未履修なのでそりゃー解けませんよ。って感じ。
▼解説ACしました
<details><summary>Python3での解答例</summary><div>

```{ABC201D.py}
H,W = map(int,input().split())
dp = [[0 for i in range(W+1)]for j in range(H+1)]
grid = [list(input())for i in range(H)]
def f(a,b):
    #範囲外のマスを参照した場合
    if H - 1 < a or W - 1 < b:
        return 0
    #青マスの場合
    elif grid[a][b] == "+":
        return 1
    #赤マスの場合
    else:
        return -1
#降順に調べる(H-1,H-1),(H-1,H-2),..
for i in range(H-1,-1,-1):
    #行全探索
    for j in range(W-1,-1,-1):
        #列全探索
        if j == W - 1:
            #下にしか行けない
            if ((i + j)%2):
                dp[i][j] = dp[i+1][j] - f(i+1,j)
            else:
                dp[i][j] = dp[i+1][j] + f(i+1,j)
            continue
        if i == H - 1:
            #右にしかいけない
            if ((i + j)% 2):
                dp[i][j] = dp[i][j+1] - f(i,j+1)
            else:
                dp[i][j] = dp[i][j+1] + f(i,j+1)
            continue
        if ((i + j) % 2):
            X = dp[i+1][j] - f(i+1,j)
            Y = dp[i][j+1] - f(i,j+1)
            dp[i][j] = min(X,Y)
        else:
            X = dp[i+1][j] + f(i+1,j)
            Y = dp[i][j+1] + f(i,j+1)
            dp[i][j] = max(X,Y)
if dp[0][0] > 0:
    print("Takahashi")
elif dp[0][0] < 0:
    print("Aoki")
else:
    print("Draw")
```


</div></details>
以上、各問題の考察です。

#2 まとめ
結局、今回も<b>C問題を解けずに2完</b>でした。
このところ、<b>C問題が解けずに2完</b>という状態が続いています。今回のようなC問題を解けなかった、というのは本当に<b>発想力</b>が足りない、ということなので、初見の問題に対する発想力を鍛えていきたいと思います。
あと最近は<b>PAST本</b>を読んで精進したり、<b>茶Difficulty</b>の過去問を解いて精進しています。<b>茶Difficulty</b>をとりあえず全埋めすることを当面の目標にします。