ICPC/Regional/2010C

出展 †

• ICPCアジア地区予選 東京大会 2010 問題文(AOJ)

解法 †

• 深さ優先探索
  • 距離が長い区間から長さを仮定し，条件を満たすかチェックしていく
  • i番目の街とj番目の街の距離が確定しているとき，次に長い区間は，
    • i+1番目の街とj番目の街の間
    • i番目の街とj-1番目の街の間
  • の2通りなので，それぞれの長さを仮定する．
  • 1区間の長さを決めれば1つの街の位置が確定するので，状態数はO(2^N)

回答 †

• 2010C_pes.cpp - O(N*2^N)のDFS(pes)