AtCoder ARC103 E Tr/ee

内容

Atcoder ARC103 のE問題(700) Tr\eeをpythonで解いた。

問題

atcoder.jp

考えたこと

• S[i]=="1"の時に、N頂点は iとN-iに別れる-> S[i]==1ならS[N-i]==1
• 木だから葉が存在する。そこできると、1とN-1に別れるはず。-> S[1]==0

  ポイント

• 頂点のidの大きい方から追加する。(Nをrootとして、N-1,N-2,..と追加していく)
  • S[i]=="1"の時、j>iでS[j]=="1"である最小のjと辺をはる。
    • すでにN-i個が追加されているから、iとN-iに分ける辺が張れる)
  • S[i]=="0"の時、j>iでS[j]=="1"である最小のjと辺をはる。
    • これを葉にすることで、1とN-1に別れる辺が張れる
    • つまり、iとN-iには別れない。
    • S[1]=S[N-1]=1は、チェック済みなので、1とN-1に別れるのは問題ない。

実装

S=input()
N=len(S)

#1-originにする
#S[0]があるとすると、0,Nに別れることはないので、0
S="0"+S

#葉できった時に、1_(n-1)になるはず
if S[1]!="1":
    print("-1")
    exit()

# S[i]=1の時,i_(N-i)に別れる-> S[i]==S[N-i]
for s,rev_s in zip(S,reversed(S)):
    if s!=rev_s:
        print("-1")
        exit()

prev=N
for i in reversed(range(1,N)):
    print(i,prev)
    #これまでに、N-i個がすでに気に追加されている。prevとcur(i)の間できると、(i_N-i)に別れる
    if S[i]=="1":
        prev=i
    else:
        #葉になる(1_N-1)に別れるため、i_(N-i)にはならない。S[1]=S[N-1]=1は決まっている。
        pass

終わりに

• 解説AC