【今日の精進】ARC154D - A + B > C ?

毎日格上の問題を倒すやつの2日目です。

問題リンク

atcoder.jp

問題概要

長さ の順列 が隠されてるよ。

以下の質問を高々 回まですることで、全ての要素を特定してね。

• か？

解法

の位置を特定すると良いことがあります。¹

なぜかというと、 を足しても大小関係が変わらないため、実質 という質問をすることができるからです。

これがあればあとはしめじソート²なりクイックソートなりをぶち込めば終わりです。

なので、 の位置を特定しましょう。

想定解法より筋が悪いですが、以下のような方法で特定できます。

• ピボットをランダムに決める³

• 「この数の 倍はピボットの値以上か？」という質問を残っているすべての数に対して投げ、Yesが帰ってきたら抹殺する

• すべての数が抹殺されたら、ピボットが である。でなければ、同じことを繰り返す。

こうすれば、高々 回の質問で特定することが可能です。

しめじソート部分では高々 回⁴の質問しか行われないことを考えると、やや危ないですが間に合います。

提出コード

import random

class Judge():
    def ask(self,i,j,k):
        print("?",i+1,j+1,k+1)
        return input()
    
    def answer(self,P):
        print("!",*P)

def sort(arr):
    if len(arr)==1:
        return arr
    a=sort(arr[:len(arr)//2])
    b=sort(arr[len(arr)//2:])
    ret=[]
    acnt=0
    bcnt=0
    for i in range(len(arr)):
        if len(a)==acnt:
            ret.append(b[bcnt])
            bcnt+=1
            continue
        if len(b)==bcnt:
            ret.append(a[acnt])
            acnt+=1
            continue
        if J.ask(a[acnt],one,b[bcnt])=="Yes":
            ret.append(b[bcnt])
            bcnt+=1
        else:
            ret.append(a[acnt])
            acnt+=1
    return ret

N=int(input())
J=Judge()
use=set(range(N))
one=-1
while True:
    pivot=-1
    while pivot not in use:
        pivot=random.randint(0,N-1)
    delete=set()
    for i in use:
        if i==pivot:
            delete.add(i)
            continue
        if J.ask(i,i,pivot)=="Yes":
            delete.add(i)
    if len(use)==len(delete):
        one=pivot
        break
    else:
        for i in delete:
            use.discard(i)
ans=sort(list(range(N)))
fin=[0 for i in range(N)]
for i in range(N):
    fin[ans[i]]=i+1
J.answer(fin)

Submission #45782432 - AtCoder Regular Contest 154

感想

良問！

だけど黄Diffの難易度ではなくないですかこれ。発想難易度が高すぎます。

---

1. 激うまギャグ↩
2. 別名をマージソートとも言います↩
3. 申し訳程度の悪意対策です。入力に悪意があったかは知りません。↩
4. 公式解説では見積もりが違いますが、丁寧に見積もればこうなる…はず↩