Codeforces Round #418 (Div. 2) : A B C D

bの数列に出てくる数字の種類が2種類以上であれば答えはYes。
それ以外の場合、1種類の数字をaが0のところに置いてみて、
ソートした結果がaと異なればYes、同じだったらNo。

数列a, b とも n - 1個は数列qと合っているとのことなので、
重複している2個と存在しない数字1つについて考えればよい。

重複している2個のどちらかを採用しないようにして、
数列を組み立てる。その結果1~nまで1つずつ存在したら
その数列が答え。

コンテスト中に解けず。TLを見てあそっかあとなる。

memo[a to z][m] := m回塗り替えたときに得られる最大Koyomity

とすると、memoを-1で初期化し、a から zまでの文字cに対して
[l, r]の範囲で全部cで塗り替えるには何回必要かを計算して、
memo[c][何回必要か] = max(memo[c][何回必要か], r - l + 1)
とすればクエリーにO(1)で答えられる。

前処理O(|\Sigma|n^2) where \Sigma is 'a' .. 'z'、クエリO(1)

コンテスト中にACできず。終わったあとにオーバーフローと出力フォーマットのミスに気づく。

2つの円のリストを考えたとき、半径の大きい順から円を取り出してきて
一方に円を追加したときの面積差分と、もう一方に円を追加したときの面積差分を比べて、
大きくなるほうに円を追加すればよい。差分が同じ場合は、どちらに追加しても結果は同じ。

O(n^2)

直観でこう気づいたけど、これが正しい理由はイマイチ分からない。