こんにちは、こんばんは。現役茶色コーダーのRuteです。
今回は自己分析2回目ということで、ABC201を振り返りたいと思います。
1.結果
レーティングは-10という結果に。2完早解きで、Cの解答者数がそこまで多くなかったことから、マイナスの幅を抑えることが出来ました。
2 各問題考察
2.1 A問題「Tiny Arithmetic Sequence」
Difficulty: 12
ソートしてA[2] - A[1] = A[1] - A[0]を検証すれば良いです。
Python3での解答例
A = list(map(int,input().split()))
A.sort()
if (A[2]-A[1]) == (A[1]-A[0]):
print("Yes")
else:
print("No")
または、Pythonの標準ライブラリであるitertools.permutationsを用いて$A$の全ての順列について全通り条件を満たすか判定する、という方法でも良さそうです。
Python3での解答例2
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")
2.2 B問題「Do you know the second highest mountain?」
Difficulty : 32
この問題は、各$S_i,T_i$を入れたリストを昇順ソートして、ソートした数列における最後から2番目の値における$T_i$を出力すれば良いです。
ただ、個人的な解法としては、$S_i = -S_i$というように再定義し、その条件のもとで昇順ソートして、ソートした数列における2番目の値における$T_i$を出力する、という解法を行いました。
いずれにせよ、計算量は$O(NlogN)$なのですが。
(解答例にcollectionsがimportされていますが、collectionsを使わずとも解くことが出来たので無視して下さい。)
Python3での解答例
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])
これは他の方もSNSで発言されていたと思いますが、過去に同類の問題がABCに出題されたことがあります。
AtCoder Beginner Contest 128 「Guidebook」
https://atcoder.jp/contests/abc128/tasks/abc128_b
この問題のDificultyは350と、灰色上位のレベルでした。
確かにこの問題における「名前順にソートし、名前が同じ場合は 点数が高いものでソートすればよい」というものが今回のB問題と似ていたのは事実なのですが、明らかにDifficultyが落ちています。
(今回の問題は$S_i$のみを考慮し、さらに$S_i \neq S_j (i \neq j)$という制約があったため、それでDifficultyが下がったのかもしれないですが)
2.3 C問題「Secret Number」
Difficulty : 439
この問題は、最初組み合わせの問題かと思って様々なことを考えました。
事実、組み合わせでも解けるらしいですが、全探索で解けることを気づかず90分間椅子を暖めていました...
▼解説ACしました。
Python3での解答例
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)
2.4 D問題「Game in Momotetsu World」
Difficulty : 1317
この問題は、幅優先探索で考えた方が良いのかな...と思ったのですが、解説を見たところDPだったようです。
DP未履修なのでそりゃー解けませんよ。って感じ。
▼解説ACしました
Python3での解答例
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")
以上、各問題の考察です。
2 まとめ
結局、今回もC問題を解けずに2完でした。
このところ、C問題が解けずに2完という状態が続いています。今回のようなC問題を解けなかった、というのは本当に発想力が足りない、ということなので、初見の問題に対する発想力を鍛えていきたいと思います。
あと最近はPAST本を読んで精進したり、茶Difficultyの過去問を解いて精進しています。茶Difficultyをとりあえず全埋めすることを当面の目標にします。