西瓜の備忘録

競プロとかで気づいたこととか考察を書き留めるためのブログ

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突破

晴れて水色コーダーになれました ヤッタネ