AtCoder ABC166
2020-05-03(日)に行われたAtCoderBeginnerContest166の問題をA問題から順に考察も踏まえてまとめたものとなります．
後半ではDEFの問題を扱います．前半はこちら．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF
D問題 I hate Factorization
問題文
$A^5−B^5=X$を満たす整数の組$(A,B)$をひとつ示してください。 ただし、与えられる$X$に対して、条件を満たす整数の組$(A,B)$が存在することが保証されています。
制約
・$1 \leq X \leq 10^9$
・$X$は整数である。
・条件を満たす整数の組$(A,B)$が存在する。
問題を読んで，どんな$X$にも条件を満たす整数の組$(A,B)$が存在すると思ってしまいました（数弱過ぎた…）．
いろいろなパターンの$X$を実装したプログラムに入力しても出力がなかったので，探索範囲が足りてないのかと思い，詰みました．
コンテスト終わった後に，解説読んで，もしかしてと思い，実装したプログラム提出したら"AC"だったので，提出しておけばよかったです…
x = int(input())
flag = 0
for a in range(-200, 201):
if flag == 1:
break
for b in range(-200, 201):
if a**5 - b**5 == x:
print(a, b)
flag = 1
break
E問題 This Message Will Self-Destruct in 5s
問題文
AtCoder 王国の優秀なエージェントであるあなたは、盗まれた極秘情報が AlDebaran 王国の手に渡ることを阻止するため、取引現場であるパーティに潜入しました。
パーティには$N$人の参加者がおり、それぞれ$1$から$N$までの番号がついています。参加者$i$の身長は$A_i$です。
あなたは事前の尋問によって、極秘情報を取引するのは以下の条件を満たす$2$人組であることを知っています。
・$2$人の持つ番号の差の絶対値が、$2$人の身長の和に等しい。
$N$人の参加者のうちから$2$人を選んでペアにする方法は$\frac{N(N−1)}{2}$通りありますが、このうち上の条件を満たすペアは何通りあるでしょう？
なお、極秘情報の内容が何であるかはあなたの知るところではありません。
コンテスト参加時は，D問題に固執して，E問題の時間があまりとれず解けませんでしたが，このレベルの問題であれば解けるようになりたいです．
「E問題F問題=難しい問題」と意識してしまっていて，コンテスト中に解けるようになかなかならないです．
解説記事に書いてあることを実装し，以下のコードで無事"AC"出ました．
n = int(input())
a_list = list(map(int, input().split()))
l_dict = {}
ans = 0
for i in range(0, n):
a = a_list[i]
ri = i - a
if ri in l_dict:
ans += l_dict[ri]
li = i + a
if li in l_dict:
l_dict[li] += 1
else:
l_dict[li] = 1
print(ans)
$2$人の持つ番号の差の絶対値っていう表現に惑わされました．
よくよく考えれば，二人を選んだ時点で，$i < j$の条件を付けることができたんですね．
負のとき，絶対値の処理しないとダメなのか，難しそう．と思った時点で負けが確定してたので，難しいと思わないようにしたいです．
F問題 Three Variables Game
問題文
あるゲームでは$3$つの変数があり、それぞれ$A,B,C$で表されます。
ゲームの進行と共に、あなたは$N$回の選択に迫られます。それぞれの選択は文字列$s_i$によって示され、$s_i$が"AB"のとき、$A$と$B$のどちらかに$1$を足しもう一方から$1$を引くこと、"AC"のとき、$A$と$C$のどちらかに$1$を足しもう一方から$1$を引くこと、"BC"のとき、$B$と$C$のどちらかに$1$を足しもう一方から$1$を引くことを意味します。
いずれの選択の後にも、$A,B,C$のいずれも負の値になってはいけません。
この条件を満たしつつ$N$回すべての選択を終えることが可能であるか判定し、可能であるならそのような選択方法をひとつ示してください。
解説読んで，書いてあることをただただ実装しました．
$A+B+C=2$のときだけ，処理に気を付けないといけないのは，入力例にもないので気づくの難しい気がする．
こういう問題をコンテスト中に解けるようになりたい．
def check(s):
if dict_x[s[0]] == 0 and dict_x[s[1]] == 0:
return "NOT"
elif dict_x[s[0]] > 0 and dict_x[s[1]] == 0:
return s[1]
elif dict_x[s[0]] == 0 and dict_x[s[1]] > 0:
return s[0]
elif dict_x[s[0]] == 1 and dict_x[s[1]] == 1:
return "EVEN"
else:
if dict_x[s[0]] > dict_x[s[1]]:
return s[1]
else:
return s[0]
def update(s, mozi):
if s[1] == mozi:
dict_x[s[0]] -= 1
dict_x[s[1]] += 1
else:
dict_x[s[0]] += 1
dict_x[s[1]] -= 1
n, a, b, c = map(int, input().split())
dict_x = {"A": a, "B": b, "C": c}
s_list = []
ans_list = []
flag = 1
for i in range(0, n):
s = input()
s_list.append(s)
if a + b + c == 0:
flag = 0
elif a + b + c == 1:
for s in s_list:
x = check(s)
if x == "NOT":
flag = 0
break
else:
ans_list.append(x)
update(s, x)
elif a + b + c == 2:
i = 0
for s in s_list:
x = check(s)
if x == "NOT":
flag = 0
break
elif x == "EVEN":
if i == len(s_list) - 1:
ans_list.append(s[0])
update(s, x)
elif s == s_list[i + 1]:
ans_list.append(s[0])
update(s, x)
else:
if s[0] in s_list[i + 1]:
ans_list.append(s[0])
update(s, s[0])
else:
ans_list.append(s[1])
update(s, s[1])
else:
ans_list.append(x)
update(s, x)
i += 1
else:
for s in s_list:
x = check(s)
if x == "NOT":
flag = 0
break
elif x == "EVEN":
ans_list.append(s[0])
update(s, s[0])
else:
ans_list.append(x)
update(s, x)
if flag == 1:
print("Yes")
for ans in ans_list:
print(ans)
else:
print("No")
F問題とか自分で書いたコード見直すと，まだまだ無駄が多いなーと実感する．
後半も最後まで読んでいただきありがとうございました．