SRM606 Div2 500をPythonで解いてみた
今回はちゃんと本番に参加しました。
500の問題文はこちらから。
問題の内容をざっくり説明すると、
- エリーちゃんとクリスちゃんは1~10億の数字を使ってお遊戯をします
- クリスちゃんはある数字を思い浮かべます
- エリーちゃんはその数字を当てようと適当な数を言って質問します
- クリスチャンは思い浮かべた数字と質問された数字の差の絶対値を答えます
- このように質問した数字と差の絶対値がタプルで渡されます
- クリスちゃんの思い浮かべてる数字を推測不可能な場合は-2を返し
- 一意に推測可能であればその数を返し
- 複数推測可能であれば-1を返します
毎度のこと、分かり難くてごめんなさい。
自分の解いたコードは以下のとおり、
class EllysNumberGuessing: def in_rule(self, x, y): if 0 < x - y <= 10**9: return x - y else: return float("nan") def getNumber(self, guesses, answers): li = [] fi = guesses[0] se = answers[0] li.append(self.in_rule(fi, se)) li.append(self.in_rule(fi, -se)) for gu, an in zip(guesses, answers): temp = [] low = self.in_rule(gu, -an) high = self.in_rule(gu, an) if low in li: temp.append(low) if high in li: temp.append(high) li = temp if len(li) == 0: return -2 elif len(li) == 1: return li[0] else: return -1
実際にsubmitしたものをちょっと手直ししてあります。
内容は、
- 最初に先頭の要素から推測できる数字をリストに入れます
- ループで要素を回して、要素ごとに推測できる数を計算します
- その数が既にリスト内にあれば、新たなリスト(temp)に入れます
- ループの処理の最後にリストをtempに更新します
- ループを出たらリストの長さを見て、対応する数字を返します
という感じですね。
今回は比較的簡単な部類だったと思います。
あと、今回でレートが1024になりました。
切りの良い数字だ、やったね。