ABC073
A問題
今回はWAしなかった(ドヤ顔
文字列でs[0],s[1]調べるだけ
ソースコードは省略
B問題
最初bool配列用意して席を埋めていくトンチンカンなコードを書いた
席は連続、同じ席に二人以上座らないという制約があるので
r-l+1の総和を取れば良い
C問題
概要:以下の施行をN回繰り返す
ある整数Nを入力、すでにNが場にある場合はNを消す、ない場合はNを場に追加する
1≦N≦10^5 1≦Ai≦10^9より場にある数を検索する方法とbool配列である数が場にあるかどうかを判定する方法は使えない
setを使えば検索、追加がO(logN)で済むので間に合う
計算量はO(NlogN)
D問題
概要:r1...rRに対しての巡回セールスマン問題
今回は多重辺(AとBの街に対して2つ以上の道)があるので二点間の最短距離を入れる必要がある
次にワーシャルフロイドで任意の2点に対して最短距離を記録・更新する
最後にNext_permutationを使って全通り(たかだか8頂点なので十分間に合う)
計算量はO(N^3+R*R!)(多分
追記
今回でレート1200突破
晴れて水色コーダーになれました ヤッタネ
今日から水色コーダー!!!!!!!!!!!!!!!!!!! pic.twitter.com/0iZS0aKYbT
— l3 4 Λ/ † 4 l< 0 (@__Bactpus__) 2017年9月9日