コンテンツにスキップ

ブログ

牛客小白月赛138 D - Light up the Graph

頂点 nn 個、辺 mm 本の単純無向グラフがあります。各頂点は白か黒で塗られています(文字列 ss の ii 文字目が 0 なら白、1 なら黒)。

好きな頂点の集合を点灯させます(何も点灯させなくてもよい)。各頂点について、隣接する点灯した頂点の個数をその頂点の「値」とします。白い頂点の値の総和から黒い頂点の値の総和を引いたものを最大化する点灯のしかたを 1 つ出力してください(n,mn, m の総和はそれぞれ ≤2×105\le 2 \times 10^5)。

頂点 vv を点灯させるとき cv=1c_v = 1、させないとき cv=0c_v = 0 とします。uu が白なら wu=1w_u = 1、黒なら wu=−1w_u = -1 とおくと、最大化したい値は

∑uwu∑v∈N(u)cv\sum_{u} w_u \sum_{v \in N(u)} c_v

です(N(u)N(u) は uu に隣接する頂点の集合)。

この式は「白い頂点 uu から見て、隣の何個が点灯しているか」を数えています。これを「点灯した頂点 vv から見て、隣に白と黒が何個ずつあるか」に数え直します。辺 (u,v)(u, v) ごとに足しているだけなので、和の順番を入れ替えて

∑vcv∑u∈N(v)wu\sum_{v} c_v \sum_{u \in N(v)} w_u

と書けます。tv=∑u∈N(v)wut_v = \sum_{u \in N(v)} w_u(vv に隣接する白い頂点の個数から、黒い頂点の個数を引いたもの)とおくと、値は ∑vcvtv\sum_v c_v t_v です。

tvt_v は cc によらない定数なので、各頂点の cvc_v は独立に決められます。tv>0t_v > 0 なら点灯させ、tv<0t_v < 0 なら点灯させなければ最大になります。tv=0t_v = 0 の頂点は、どちらにしても値は変わりません。

点灯させた頂点の色は関係ないことに注意してください。値に効くのは隣の頂点の色だけです。

tvt_v は各頂点の隣接リストを一度ずつ見れば求まるので、計算量は O(n+m)O(n + m) です。

1 つ目のサンプルの頂点 1 は、隣が頂点 4(白)と頂点 5(黒)なので t1=0t_1 = 0 です。そのため、サンプル出力では点灯させていますが、点灯させなくても最大値 44 は変わりません。

Python
for _ in range(int(input())):
N,M=map(int,input().split())
S=input()
g=[[]for i in range(N)]
for _ in range(M):
u,v=map(int,input().split())
u,v=u-1,v-1
g[u].append(v)
g[v].append(u)
ans = []
for u in range(N):
t = 0
for v in g[u]:
if S[v] == "0":
t += 1
else:
t -= 1
if t > 0:
ans.append(u+1)
print(len(ans))
print(*ans)

各頂点 u について、隣接する白い頂点を +1+1、黒い頂点を −1-1 として足した t を求め、正なら点灯させています。点灯させる頂点が 00 個のときは print(*ans) が空行を出力するので、問題の出力形式どおりになります。

牛客小白月赛138 C - AND and OR

長さ nn の非負整数列 a1,…,ana_1, \dots, a_n と非負整数 kk が与えられます(2≤n≤2×1052 \le n \le 2 \times 10^5、0≤ai,k≤1090 \le a_i, k \le 10^9)。

(aiandaj)+(aioraj)=k(a_i \mathbin{\mathrm{and}} a_j) + (a_i \mathbin{\mathrm{or}} a_j) = k

を満たす 1≤i<j≤n1 \le i < j \le n があれば 1 つ出力し、なければ −1-1 を出力してください(nn の総和 ≤2×105\le 2 \times 10^5)。

実は、どんな非負整数 a,ba, b についても

(aandb)+(aorb)=a+b(a \mathbin{\mathrm{and}} b) + (a \mathbin{\mathrm{or}} b) = a + b

が成り立ちます。ビットごとに確かめると分かります。各ビットについて、aa と bb のそのビットの組み合わせは次の 3 通りです。

a,ba, b のビットANDORAND + ORa+ba + b
両方 0000000000
片方だけ 1100111111
両方 1111112222

どのビットでも AND と OR の寄与の和が aa と bb の寄与の和に一致するので、全体でも等しくなります。

したがって、問題は「ai+aj=ka_i + a_j = k となる i<ji < j を 1 つ見つけよ」という、よくある問題に言い換えられます。

(ai,i)(a_i, i) の組を値でソートしておきます。各要素 aia_i について、相手の値 k−aik - a_i が列にあるかを二分探索で調べます。見つかった相手が自分自身でなければ、そのペアが答えです。

k−ai=aik - a_i = a_i のときは、二分探索で見つかる最初の要素が自分自身になることがあります。ただ、同じ値がもう 1 つあれば、その要素を見たときに最初の要素が相手として見つかるので、取りこぼしはありません。

計算量はソートと二分探索で O(nlog⁡n)O(n \log n) です。

Python
import bisect
for _ in range(int(input())):
N, K = map(int,input().split())
A = list(map(int,input().split()))
Ai = [(A[i],i) for i in range(N)]
Ai.sort()
for i in range(N):
j = bisect.bisect_left(Ai,(K-Ai[i][0],-1))
if 0<=j<N and i!=j and K-Ai[i][0]==Ai[j][0]:
print(*sorted((Ai[i][1]+1,Ai[j][1]+1)))
break
else:
print(-1)

Ai は (値, 元の添字) の組をソートしたものです。(K-Ai[i][0],-1) で bisect_left すると、値が k−aik - a_i 以上である最初の位置が求まります。添字は 00 以上なので、第 2 要素に −1-1 を入れておけば、値が k−aik - a_i の組より必ず前に来ます。出力は i<ji < j の順にする必要があるので、元の添字をソートしてから出力しています。

牛客小白月赛138 B - Is it Palidrome?

英小文字と ? からなる長さ nn の文字列 ss があります。それぞれの ? を好きな英小文字に置き換えます。

  • どう置き換えても回文になるなら certainly
  • どう置き換えても回文にならないなら impossible
  • 回文になる置き換え方とならない置き換え方の両方があるなら possible

を出力してください(nn の総和 ≤5×105\le 5 \times 10^5)。

回文かどうかは、左右対称な位置にある文字のペア (si,sn−1−i)(s_i, s_{n-1-i})(0≤i<⌊n/2⌋0 \le i < \lfloor n/2 \rfloor)がすべて等しいかどうかで決まります。そこで、ペアを次の 3 種類に分けます。

  • どちらも英小文字で、異なる:どう置き換えてもこのペアは等しくならないので、回文にはなりません。
  • 少なくとも一方が ?:? の置き換え方しだいで、等しくすることも異なるものにすることもできます。
  • どちらも英小文字で、等しい:どう置き換えてもこのペアは等しいままです。

ペアごとの ? の置き換えは互いに独立に選べるので、答えは次のようになります。

  1. 異なる英小文字のペアが 1 つでもあれば impossible
  2. そうでなく、? を含むペアが 1 つでもあれば possible(すべてのペアを等しくすることも、そのペアだけを異なるものにすることもできる)
  3. どちらでもなければ certainly

nn が奇数のときの真ん中の文字はどのペアにも入らないので、? であっても回文かどうかに影響しません。3 つ目のサンプル xy?yx が certainly になるのはこのためです。

計算量は O(n)O(n) です。

Python
for _ in range(int(input())):
N = int(input())
S = input()
p = False
ng = False
for i in range(N//2):
if S[i] == "?":
p = True
continue
if S[N-i-1] == "?":
p = True
continue
if S[i] != S[N-i-1]:
ng = True
continue
if ng:
print("impossible")
elif p:
print("possible")
else:
print("certainly")

p は ? を含むペアがあるか、ng は異なる英小文字のペアがあるかを表します。ループを N//2 までにしているので、真ん中の文字は自然に見ないことになります。

牛客小白月赛138 A - Sleeping Time

xx 時に寝始めて、tt 時間眠ります(0≤x≤230 \le x \le 23、1≤t≤501 \le t \le 50)。起きる時刻(0 時から 23 時のどれか)を求めてください。

時計は 24 時間で一周するので、答えは (x+t) mod 24(x + t) \bmod 24 です。

tt は最大 5050 で 24 時間を超えることがありますが、 mod 24\bmod 24 をとれば何周しても正しく求まります。たとえば x=10,t=50x = 10, t = 50 なら 60 mod 24=1260 \bmod 24 = 12 です。

Python
print(sum(map(int, input().split())) % 24)

Codeforces Round 1125 (Div. 3) C - Unrequited Love

長さ nn の整数列 a1,…,ana_1, \dots, a_n があります(6≤n≤2⋅1056 \le n \le 2 \cdot 10^5、∣ai∣≤104|a_i| \le 10^4)。1≤x≤n−41 \le x \le n - 4 に対して、鍵 x,x+2,x+4x, x + 2, x + 4 の組を「トライアド xx」と呼び、その値を ax+ax+2−ax+4a_x + a_{x+2} - a_{x+4} とします。

鍵を共有せず、値が等しい 2 つのトライアドの組(順序は区別しない)の個数を求めてください(nn の総和 ≤2⋅105\le 2 \cdot 10^5)。

vx=ax+ax+2−ax+4v_x = a_x + a_{x+2} - a_{x+4} とおきます。

鍵を共有するのはどんなときか

Section titled “鍵を共有するのはどんなときか”

トライアド x<yx < y の鍵は {x,x+2,x+4}\{x, x+2, x+4\} と {y,y+2,y+4}\{y, y+2, y+4\} です。y−xy - x が奇数なら偶奇が違うので共有しません。y−x≥6y - x \ge 6 なら離れすぎていて共有しません。したがって、鍵を共有するのは y−x=2y - x = 2 または y−x=4y - x = 4 のときだけです。

鍵の共有を気にせずに、値が等しいペアをすべて数えてから、鍵を共有するペアを引きます。

  • 値が等しいペアの総数:vv をソートすると、同じ値が連続して並びます。同じ値が kk 個あれば、そこから (k2)=k(k−1)2\binom{k}{2} = \frac{k(k-1)}{2} 個のペアが作れます。
  • 鍵を共有するペア:vx=vx+2v_x = v_{x+2} となる xx の個数と、vx=vx+4v_x = v_{x+4} となる xx の個数を足したものです。

答えは前者から後者を引いたものです。計算量はソートがあるので O(nlog⁡n)O(n \log n) です。

補足:辞書で数えるとハックされる

Section titled “補足:辞書で数えるとハックされる”

vyv_y と等しい vxv_x(x<yx < y)の個数を、Counter などの辞書で数えながら左から見ていく方法も考えられます。ただ、Python でこの方法を提出したところ、PyPy でも TLE になりました(テスト 7)。

テスト 7 は、奇数番目の要素がすべて 00 の入力です。そのため奇数位置の vxv_x はすべて 00 になり、辞書のキー 00 が約 10510^5 回検索されます。一方、偶数位置の vxv_x は、キー 00 を検索するときにたどる位置をほかのキーで埋め尽くすように作られていると考えられます。Python の整数のハッシュ値は値そのものなので、キーが予測できればこのような入力を作れてしまいます。その結果、検索のたびに長い列をたどることになって TLE します。

対策としては、次のどちらかがあります。

  • 起動時に決めた乱数とキーの XOR をとってから辞書に入れる(ハックする側が衝突を狙えなくなる)
  • 上の解法のように、ハッシュを使わずにソートで数える

ここでは後者を採用しています。C++ の std::map は平衡二分木でハッシュを使わないので、辞書で数える方法でも問題ありません。

Python
from itertools import groupby
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
M = N - 4
v = [A[i] + A[i + 2] - A[i + 4] for i in range(M)]
ans = 0
for _, g in groupby(sorted(v)):
k = len(list(g))
ans += k * (k - 1) // 2
for i in range(M):
if i + 2 < M and v[i] == v[i + 2]:
ans -= 1
if i + 4 < M and v[i] == v[i + 4]:
ans -= 1
print(ans)

groupby(sorted(v)) で同じ値の並びごとに個数 k を数え、(k2)\binom{k}{2} を足しています。そのあと、位置の差が 22 と 44 で値が等しいものを引いています。

C++(std::map で数える)
#include "sh-library/base/all"
void solve() {
LL(N);
VL(A, N);
mll c;
ll ans = 0;
deque<ll> d;
rep(i, N - 4) {
ll t = A[i] + A[i + 2] - A[i + 4];
ans += c[t];
if (d.size() >= 1 && d[d.size() - 1] == t) {
ans++;
}
if (d.size() >= 3 && d[d.size() - 3] == t) {
ans++;
}
while (d.size() >= 4) {
c[d.front()]++;
d.pop_front();
}
d.push_back(t);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
LL(T);
rep(T)
solve();
}

左から順に見て、トライアド yy と組になる x<yx < y を数えています。

  • y−x≥5y - x \ge 5 の分は、c(値ごとの個数を持つ std::map)で数えます。
  • y−xy - x が 11 と 33 の分は、直近 4 個の値を持つ d で個別に確かめます。

y−xy - x が 22 と 44 のペアは鍵を共有するので数えません。

使用ライブラリ:cpp_include@6e9980e

Codeforces Round 1125 (Div. 3) B - Did Not Go to Print

文書 1,…,n1, \dots, n と、最初は空のプリンターのメモリがあります。ii 番目の操作 sis_i は次のいずれかです。

  • 1:文書 ii をメモリの一番上に積む
  • 2:メモリが空でなければ、一番上の文書を印刷してメモリから取り除く。空なら文書 ii を印刷する
  • 3:文書 ii を印刷する

すべての操作のあとで、一度も印刷されなかった文書の番号を昇順に出力してください(nn の総和 ≤2⋅105\le 2 \cdot 10^5)。

メモリは「最後に積んだものから取り出す」ので、スタックそのものです。操作を順にシミュレーションして、印刷された文書を記録すれば、残りが答えです。

  • 1:スタックに ii を push する
  • 2:スタックが空でなければ pop した文書を、空なら ii を印刷済みにする
  • 3:ii を印刷済みにする

なお、2 でスタックが空でないときは、文書 ii 自身は印刷されません。2 の操作では文書 ii はメモリにも入らないので、その文書が印刷されることはもうありません。

各操作は O(1)O(1) なので、全体で O(n)O(n) です。

Python
for _ in range(int(input())):
N = int(input())
S = input()
t = []
l = []
for i, c in enumerate(S):
if c == "1":
l.append(i)
elif c == "2":
if l:
t.append(l.pop())
else:
t.append(i)
else:
t.append(i)
ans = set(range(N)) - set(t)
print(len(ans))
print(*[i + 1 for i in sorted(ans)])

l がメモリのスタック、t が印刷された文書のリストです。文書番号は 0 始まりで持っておき、出力するときに 1 を足しています。k=0k = 0 のときは print(*[]) が空行を出力するので、そのままで大丈夫です。

Codeforces Round 1125 (Div. 3) A - In Search of Convenience

整数 x0,y0,Rx_0, y_0, R が与えられます(−10≤x0,y0≤10-10 \le x_0, y_0 \le 10、1≤R≤251 \le R \le 25)。点 (x0,y0)(x_0, y_0) からの距離がちょうど RR である格子点(座標が整数の点)を 1 つ出力してください。答えが複数あるときは、どれを出力してもかまいません。テストケースは t≤104t \le 10^4 個です。

(x0,y0)(x_0, y_0) から xx 軸の方向にちょうど RR だけずらした点 (x0−R,y0)(x_0 - R, y_0) を出力すればよいです。

RR は整数なので、この点も格子点です。距離は

(x0−(x0−R))2+(y0−y0)2=R2=R\sqrt{(x_0 - (x_0 - R))^2 + (y_0 - y_0)^2} = \sqrt{R^2} = R

となり、ちょうど RR です。

問題文の例のように (5−2)2+(5−1)2=52(5 - 2)^2 + (5 - 1)^2 = 5^2 となる点を探す必要はありません。軸に沿ってずらすだけで条件を満たせます。(x0+R,y0)(x_0 + R, y_0) や (x0,y0±R)(x_0, y_0 \pm R) でもかまいません。

Python
for _ in range(int(input())):
x, y, r = map(int, input().split())
print(x - r, y)

SamCoding Round 7 (Div. 2) K - Blueprints Washed by the Rain

正の整数の列 b1,…,bnb_1, \dots, b_n に対して、g(b)ig(b)_i を「ii より左にあって bj<bib_j < b_i を満たす jj のうち最大のもの(なければ 00)」と定めます。ある bb によって y=g(b)y = g(b) と書ける列 yy を「復元可能」と呼びます。

長さ nn の列 xx が与えられます。xx のいくつかの要素は −1-1 です。−1-1 をそれぞれ 00 以上 nn 以下の整数に置き換えて xx を復元可能にする方法の数を、109+710^9 + 7 で割った余りで求めてください(nn の総和 ≤5000\le 5000)。

bb の Cartesian Tree を考えます。最小値を根にし、頂点は中間順に添字 1,…,n1, \dots, n で並べます。値が等しい要素は、後ろにあるほうを小さいとみなします。gg の定義が真の不等号 bj<bib_j < b_i なので、こうすると「bj<bib_j < b_i」と「jj のほうが小さい(j<ij < i のとき)」が一致します。

このとき、ii の左部分木はちょうど区間 [gi+1,i−1][g_i + 1, i - 1] になります。ii の左部分木は「ii から左へ、ii より大きい要素が続く範囲」で、その左端の外側が ii より左で最も近い小さい要素、つまり gig_i だからです。

gg とツリーの形は一対一に対応します。スタックを使った Cartesian Tree の作り方で考えると分かりやすいです。

  • 根から右の子だけをたどった道(以下、右端の道)をスタックで持つ
  • ii を追加するときは、bib_i より大きい要素をスタックから pop する。pop した部分が ii の左部分木になり、ii は残ったスタックの一番上の右の子になる。最後に ii を push する

pop し終わったときのスタックの一番上が、ちょうど gig_i です(空なら 00)。そのため、各ステップで何個 pop するかは gg から決まり、ツリーの形も gg から決まります。逆に、どんな形のツリーにも、それを作る bb が存在します(例えば、根からの深さをそのまま bb にすればよいです)。

まとめると、復元可能な yy と、nn 頂点の二分木の形は一対一に対応します。全部が −1-1 のときの答えは Catalan 数 CnC_n で、サンプル 3 の 132=C6132 = C_6 と一致します。

例えば g=[0,1,2,1,0,0,6]g = [0, 1, 2, 1, 0, 0, 6] に対応するツリーの親は、[5,4,2,1,6,−,6][5, 4, 2, 1, 6, -, 6] です(6 が根)。4 の左部分木が [g4+1,3]=[2,3][g_4 + 1, 3] = [2, 3] になっていることなどが確かめられます。

この対応を使うと、問題は次のように言い換えられます。

頂点 1,…,n1, \dots, n を中間順に並べた二分木のうち、xi≠−1x_i \ne -1 であるすべての ii について「ii の左部分木がちょうど [xi+1,i−1][x_i + 1, i - 1] である」ものを数える

xi≥ix_i \ge i のときは、そのような左部分木はありえないので答えは 00 です。

固定された左部分木は独立に数えられる

Section titled “固定された左部分木は独立に数えられる”

xi≠−1x_i \ne -1 のとき、ii の左部分木 [xi+1,i−1][x_i + 1, i - 1] は、それだけで閉じた部分木です。この部分の形は、外側の形とは無関係に選べます。また外側から見ると、左部分木ごと ii に潰してしまえば、ii は「左の子を持たない頂点」 として扱えます。

そこで、左から順に頂点を見ながら、次のように列を潰していきます。

  • xi=−1x_i = -1 のとき:ii を「自由な頂点」として列の末尾に加える
  • xi≠−1x_i \ne -1 のとき:列の中から xi+1x_i + 1 以降に始まる要素をすべて取り出す。それらが ii の左部分木になるので、その形の数を答えに掛ける。そのあと、xi+1x_i + 1 から ii までをまとめて「左の子を持たない頂点」1 個として末尾に加える

列の各要素が元の列のどこから始まるかを記録しておきます。取り出す範囲の先頭が xi+1x_i + 1 から始まる要素になっていないとき、つまり xi+1x_i + 1 がすでに潰された要素の内側にあるときは、答えは 00 です。ii の左部分木の境界が、ほかの頂点の左部分木と交差してしまうからです。

最後に残った列全体の形の数も掛ければ、答えになります。

左の子を持たない頂点を含む二分木の数え上げ

Section titled “左の子を持たない頂点を含む二分木の数え上げ”

あとは「列の各要素が、自由な頂点か、左の子を持たない頂点か」が決まっているときに、中間順がその列になる二分木の数を求めればよいです。

Cartesian Tree の作り方と同じく、右端の道をスタックで持ちながら頂点を 1 個ずつ追加することにします。スタックの高さが hh のとき、次の頂点を追加する方法は次のとおりです。

  • 自由な頂点:00 個以上 hh 個以下を pop してから push するので、新しい高さは 11 以上 h+1h + 1 以下
  • 左の子を持たない頂点:pop しないで push するので、新しい高さは h+1h + 1

pop の仕方とツリーの形は一対一に対応するので、dp[h]\mathrm{dp}[h] を「スタックの高さが hh になる方法の数」とする DP で数えられます。自由な頂点の遷移は

dp′[h′]=∑h≥h′−1dp[h]\mathrm{dp}'[h'] = \sum_{h \ge h' - 1} \mathrm{dp}[h]

なので、後ろからの累積和で O(長さ)O(\text{長さ}) で計算できます。答えは最後の dp\mathrm{dp} の総和です。

各頂点はちょうど 1 回だけ、どれか 1 つの列の DP に参加します。長さ mm の列の DP は O(m2)O(m^2) なので、全体で O(n2)O(n^2) です。

Python
from bisect import bisect_left
from itertools import accumulate
MOD = 10**9 + 7
def count(flags):
dp = [1]
for f in flags:
if f:
dp = [0] + dp
else:
s = list(accumulate(reversed(dp)))
s.reverse()
dp = [0] + [v % MOD for v in s]
return sum(dp) % MOD
def solve(n, x):
ans = 1
starts = []
flags = []
for i in range(1, n + 1):
if x[i - 1] == -1:
starts.append(i)
flags.append(False)
continue
l = x[i - 1] + 1
if l > i:
return 0
k = bisect_left(starts, l)
if l < i and (k == len(starts) or starts[k] != l):
return 0
ans = ans * count(flags[k:]) % MOD
del starts[k:]
del flags[k:]
starts.append(l)
flags.append(True)
return ans * count(flags) % MOD
t = int(input())
for _ in range(t):
n = int(input())
x = list(map(int, input().split()))
print(solve(n, x))

starts は列の各要素が元の列のどこから始まるか、flags はその要素が左の子を持たない頂点かどうかです。starts は昇順なので、xi+1x_i + 1 から始まる要素を bisect_left で探しています。

count が二分木の数え上げの DP です。dp[h] はスタックの高さが h になる方法の数で、左の子を持たない頂点では高さが 1 増えるだけなので、先頭に 0 を足してずらします。自由な頂点では、後ろからの累積和をとってから先頭に 0 を足します。

SamCoding Round 7 (Div. 2) J - Lying Guard

11 以上 NN 以下の秘密の数 TT を当てるインタラクティブ問題です(N≤1018N \le 10^{18})。? i と質問すると、TT と ii の大小関係が >、<、= のいずれかで返ってきます。

ただし、答える番人はゲーム全体を通して 1 回だけ 嘘をつくことがあります。= の答えが嘘のこともあります。質問は 190190 回までです。

ふつうの二分探索で、同じ質問を 3 回ずつして多数決をとります。

嘘はゲーム全体で高々 1 回なので、同じ質問への 3 回の答えのうち、少なくとも 2 回は本当です。そのため、多数決をとれば必ず正しい答えが得られます。正しい答えだけで二分探索を進めれば、ふつうの二分探索と同じく TT が求まります。

範囲 [l,r][l, r] の真ん中 mm を聞き、> なら l=m+1l = m + 1、< なら r=m−1r = m - 1、= ならそこで終わりにします。範囲の大きさは 1 回ごとに半分以下になるので、繰り返しは ⌊log⁡21018⌋+1=60\lfloor \log_2 10^{18} \rfloor + 1 = 60 回以下です。1 回につき 3 回質問するので、合計 180180 回以下で、上限の 190190 回に収まります。

Python
from collections import Counter
N = int(input())
l = 1
r = N
while l < r:
m = (l + r) // 2
c = Counter()
for _ in range(3):
print("?", m, flush=True)
c[input()] += 1
k = c.most_common()[0][0]
if k == "=":
l = r = m
elif k == ">":
l = m + 1
else:
r = m - 1
print("!", l, flush=True)

3 回の答えを Counter で数え、most_common()[0][0] で最も多い答えを取り出しています。= のときは l = r = m としてループを抜けます。

SamCoding Round 7 (Div. 2) I - Subarrays in Range L-R

長さ nn の数列 aa と整数 L,RL, R が与えられます。連続する部分列のうち、総和が LL 以上 RR 以下のものの個数を求める問題です(n≤105n \le 10^5、−109≤ai≤109-10^9 \le a_i \le 10^9、−1014≤L≤R≤1014-10^{14} \le L \le R \le 10^{14})。aia_i は負になることもあります。

累積和を S0=0S_0 = 0、Sj=a1+⋯+ajS_j = a_1 + \cdots + a_j とすると、区間 [i+1,j][i + 1, j] の総和は Sj−SiS_j - S_i です。条件 L≤Sj−Si≤RL \le S_j - S_i \le R を SiS_i について書き直すと

Sj−R≤Si≤Sj−LS_j - R \le S_i \le S_j - L

です。したがって、各 jj について「i<ji < j で SiS_i が [Sj−R,Sj−L][S_j - R, S_j - L] に入るものの個数」を足し合わせれば答えになります。

aia_i が負になることもあるので SS は単調ではなく、しゃくとり法は使えません。そこで j=1,2,…,nj = 1, 2, \ldots, n の順に見ていき、それまでに出てきた SiS_i を、値ごとの個数として管理します。必要な操作は次の 2 つです。

  • SjS_j を 1 個追加する
  • 値が [Sj−R,Sj−L][S_j - R, S_j - L] の範囲にある SiS_i の個数を数える

SS の値は最大 101410^{14} 程度と大きいので、S0,…,SnS_0, \ldots, S_n を座標圧縮して添字にし、区間和を求めるセグメント木(または BIT)で管理します。値の範囲 [Sj−R,Sj−L][S_j - R, S_j - L] は、圧縮後の添字では二分探索で求まります。全体で O(nlog⁡n)O(n \log n) です。

C++(セグメント木)
#include "ou-library/segtree.hpp"
#include "sh-library/base/all"
void solve() {
LL(N, L, R);
VL(A, N);
ll t = 0;
sl s;
s.insert(t);
for (ll a : A) {
t += a;
s.insert(t);
}
vl v(all(s));
RSumQ<ll> seg(v.size());
ll ans = 0;
t = 0;
seg.apply(bisect_left(v, t), 1);
for (ll a : A) {
t += a;
ans += seg.prod(bisect_left(v, t - R), bisect_right(v, t - L));
seg.apply(bisect_left(v, t), 1);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

前半では累積和の値を std::set に入れ、ソート済みで重複のない v にしています(座標圧縮)。値 xx の添字は bisect_left(v, x) です。

後半では t が SjS_j で、seg.prod(bisect_left(v, t - R), bisect_right(v, t - L)) が「値が [Sj−R,Sj−L][S_j - R, S_j - L] にある SiS_i の個数」です。数えてから seg.apply(..., 1) で SjS_j を追加するので、i<ji < j のものだけが数えられます。RSumQ は区間和のセグメント木です。

使用ライブラリ:cpp_include@6c2f83f

Python(BIT)
from bisect import bisect_left, bisect_right
from itertools import accumulate
N, L, R = map(int, input().split())
A = list(map(int, input().split()))
S = [0, *accumulate(A)]
v = sorted(set(S))
M = len(v)
bit = [0] * (M + 1)
def add(i):
i += 1
while i <= M:
bit[i] += 1
i += i & -i
def count(i):
res = 0
while i:
res += bit[i]
i -= i & -i
return res
ans = 0
add(bisect_left(v, 0))
for t in S[1:]:
ans += count(bisect_right(v, t - L)) - count(bisect_left(v, t - R))
add(bisect_left(v, t))
print(ans)

C++ 版と同じ処理を BIT で書いています。count(i) は添字が ii 未満の個数なので、2 つの差が範囲内の個数になります。

SamCoding Round 7 (Div. 2) H - Mysterious Valley

NN 個の地点が一列に並び、それぞれの高さはすべて異なります。両隣より低い地点(谷)を 1 つ見つけるインタラクティブ問題です。端の地点では、外側に無限に高い山があるとみなします。

? i と質問すると地点 ii の高さが返ってきます。質問は 130130 回までで、NN は最大 101810^{18} です。

二分探索で谷を探します。

まず端を調べます。

  • h1<h2h_1 < h_2 なら、地点 11 が谷です。
  • hN−1>hNh_{N-1} > h_N なら、地点 NN が谷です。

どちらでもなければ、h1>h2h_1 > h_2(左端では下り)かつ hN−1<hNh_{N-1} < h_N(右端では上り)です。

「下り」と「上り」の間を狭める

Section titled “「下り」と「上り」の間を狭める”

ll を「hl>hl+1h_l > h_{l+1}(下り)」、rr を「hr<hr+1h_r < h_{r+1}(上り)」を満たす位置として、l=1l = 1、r=N−1r = N - 1 から始めます。

ll と rr の真ん中 mm で hmh_m と hm+1h_{m+1} を比べ、上りなら r=mr = m、下りなら l=ml = m とします。こうすれば、ll では下り、rr では上り、という状態がずっと保たれます。

r=l+1r = l + 1 になったら、hl>hrh_l > h_r かつ hr<hr+1h_r < h_{r+1} なので、地点 rr が谷です。

r−lr - l は 1 回ごとにほぼ半分になるので、繰り返しは ⌈log⁡21018⌉=60\lceil \log_2 10^{18} \rceil = 60 回以下です。1 回の繰り返しで質問するのは hmh_m と hm+1h_{m+1} の 2 つなので、最初の 4 回と合わせて 4+2×60=1244 + 2 \times 60 = 124 回以下に収まります。

Python
d = {}
def q(x):
if x not in d:
print("?", x)
d[x] = int(input())
return d[x]
N = int(input())
if N == 1:
print("!", 1)
exit(0)
if q(1) < q(2):
print("!", 1)
exit(0)
if q(N - 1) > q(N):
print("!", N)
exit(0)
l = 1
r = N - 1
while l + 1 < r:
m = (l + r) // 2
if q(m) < q(m + 1):
r = m
else:
l = m
print("!", r)

q(x) は地点 xx の高さを質問する関数で、同じ地点を 2 回質問しないように結果を d に覚えています。

問題文では出力のたびにフラッシュするように書かれていますが、Python の input() は読み込む前に標準出力をフラッシュするので、flush を書かなくても質問はジャッジに届きます。

SamCoding Round 7 (Div. 2) G - Chocolate Factory

D と M からなる長さ 2n−12n - 1 の文字列 ss が与えられます。長さ nn 以上の区間で、M をちょうど xx 個含むものが nn 個以上あるような xx を 1 つ求める問題です(n≤106n \le 10^6)。そのような xx は必ず存在します。

問題文では「nn 人の検査員がそれぞれ異なる区間を担当し、全員が同じ個数の M を検査する」という設定になっています。

たとえば n=3n = 3、s=s = MDMDM のとき、M を 22 個含む長さ 33 以上の区間は [1,3],[3,5],[1,4],[2,5][1, 3], [3, 5], [1, 4], [2, 5] の 44 個あるので、x=2x = 2 が答えです。

長さ nn 以上の区間はおよそ n22\frac{n^2}{2} 個あるので、すべて数えることはできません。そこで、条件を満たすと保証できる xx を 1 つ見つけます。

長さ nn の区間に含まれる M の個数の最大値を xx とすると、これが答えになります。

最大を達成する区間を [p,p+n−1][p, p + n - 1] とします。区間を 1 文字伸ばしたり縮めたりしても、M の個数は 00 か 11 しか変わりません。そのため、xx 以下の区間から xx 以上の区間まで 1 文字ずつ動かせば、途中に必ずちょうど xx の区間があります。

これを使って、ちょうど xx 個の区間を nn 個見つけます。

  • 左端 l<pl < p のそれぞれ(p−1p - 1 個): 右端を l+n−1l + n - 1 から p+n−1p + n - 1 まで伸ばしていきます。最初の [l,l+n−1][l, l + n - 1] は長さ nn なので M は xx 個以下、最後の [l,p+n−1][l, p + n - 1] は最大の区間を含むので xx 個以上です。途中に M がちょうど xx 個の区間があります。
  • 右端 r≥p+n−1r \ge p + n - 1 のそれぞれ(n−p+1n - p + 1 個): 左端を pp から r−n+1r - n + 1 まで縮めていきます。最初の [p,r][p, r] は最大の区間を含むので xx 個以上、最後の [r−n+1,r][r - n + 1, r] は長さ nn なので xx 個以下です。こちらも途中にちょうど xx 個の区間があります。

前者の区間は左端が pp より前、後者は左端が pp 以降なので、すべて異なります。どれも長さは nn 以上で、個数は (p−1)+(n−p+1)=n(p - 1) + (n - p + 1) = n です。

長さ nn の区間は nn 個あり、スライディングウィンドウで M の個数を更新しながら最大値を求めれば O(n)O(n) です。

Python
N = int(input())
S = input()
ans = t = S[:N].count("M")
for i in range(N - 1):
t -= S[i] == "M"
t += S[i + N] == "M"
ans = max(ans, t)
print(ans)

t が今の区間に含まれる M の個数です。区間を 1 つ右にずらすとき、左端から外れる S[i] と右端に入る S[i + N] の分だけ t を更新しています。

SamCoding Round 7 (Div. 2) F - Subarrays Divisible by K

長さ nn の数列 aa と整数 kk が与えられます。連続する部分列 al,…,ara_l, \ldots, a_r のうち、総和が kk で割り切れるものの個数を求める問題です(n≤105n \le 10^5、k≤109k \le 10^9、0≤ai≤1090 \le a_i \le 10^9)。

累積和を S0=0S_0 = 0、Si=a1+⋯+aiS_i = a_1 + \cdots + a_i とすると、区間 [l,r][l, r] の総和は Sr−Sl−1S_r - S_{l-1} です。これが kk で割り切れるのは

Sr≡Sl−1(modk)S_r \equiv S_{l-1} \pmod{k}

のときです。つまり、0≤i<j≤n0 \le i < j \le n で Si mod kS_i \bmod k と Sj mod kS_j \bmod k が等しい組 (i,j)(i, j) の個数が答えです。

j=0,1,…,nj = 0, 1, \ldots, n の順に見ていき、それまでに出てきた余りの個数を数えておけば、各 jj について「Sj mod kS_j \bmod k と同じ余りの SiS_i が前に何個あったか」がすぐに分かります。全体で O(n)O(n) です。

Python
from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))
t = 0
C = Counter()
C[0] += 1
ans = 0
for a in A:
t += a
t %= K
ans += C[t]
C[t] += 1
print(ans)

t が累積和を kk で割った余り、C が余りごとの出現回数です。最初に C[0] += 1 で S0=0S_0 = 0 の分を数えておき、各要素を足すたびに同じ余りの個数を答えに加えています。

kk は最大 10910^9 なので、配列ではなく Counter(辞書)で数えています。

SamCoding Round 7 (Div. 2) E - Park Lamps

n×mn \times m のマス目があり、マスの境界(長さ 11 の道)の中央にランプを置けます。ランプはその道を挟む 22 マスを照らします(外周の道なら 11 マスだけ)。すべてのマスを照らすのに必要なランプの最小個数を求める問題です(1≤n,m≤1051 \le n, m \le 10^5)。

答えは ⌈nm2⌉\left\lceil \frac{nm}{2} \right\rceil です。

  • これより少なくはできない: ランプ 1 個で照らせるのは高々 22 マスなので、nmnm マスを照らすには nm2\frac{nm}{2} 個以上必要です。
  • この個数で照らせる: マス目は、隣り合う 22 マスの組(ドミノ)で、高々 11 マスを残して敷き詰められます。たとえば各行を左から 22 マスずつ組にし、各行の余りは縦に 22 マスずつ組にします。各ドミノの間の道にランプを置き、残った 11 マスがあればその周りの道に 11 個置けば、⌈nm2⌉\left\lceil \frac{nm}{2} \right\rceil 個ですべてのマスを照らせます。
Python
N, M = map(int, input().split())
print((N * M + 1) // 2)

(N * M + 1) // 2 で nm2\frac{nm}{2} の切り上げを計算しています。

SamCoding Round 7 (Div. 2) C - Digitless Keyboard

nn 個の整数 a1,…,ana_1, \ldots, a_n が与えられるので、最大値と最小値の平均を切り捨てて出力する問題です(2≤n≤1052 \le n \le 10^5、−109≤ai≤109-10^9 \le a_i \le 10^9)。ただし、ソースコードのどこにも数字 0〜9 を使ってはいけません。

計算は ⌊max⁡A+min⁡A2⌋\left\lfloor \frac{\max A + \min A}{2} \right\rfloor です。問題は 22 で割るところで、// 2 と書くと数字を使ってしまいます。

そこで、22 で割って切り捨てる代わりに、右に 11 ビットシフトします。シフト量の 11 には True を使います。Python では True が整数の 11 として扱われるからです。

右シフトは負の数でも切り捨て(負の無限大方向への丸め)になるので、和が負のときもそのまま正しい答えになります。たとえば −4≫1=−2-4 \gg 1 = -2、−3≫1=−2-3 \gg 1 = -2 です。

Python
N = int(input())
A = list(map(int, input().split()))
print((max(A) + min(A)) >> True)

>> True が 22 で割って切り捨てる処理です。

SamCoding Round 7 (Div. 2) D - Perfect Number

各桁の和が 1010 になる正の整数を「完全数」と呼びます(19,28,37,…19, 28, 37, \ldots)。小さい方から kk 番目の完全数を求める問題です(1≤k≤1051 \le k \le 10^5)。

完全数を小さい順にすべて列挙し、kk 番目を出力します。

m=r+1m = r + 1 桁の完全数は、1010 個の玉と rr 本の仕切りを一列に並べたものと対応させられます。仕切りで区切られた r+1r + 1 個の区間に入っている玉の個数を、上の桁から順に並べたものが各桁の数字です。

たとえば r=2r = 2 で、1212 マスの列のうち位置 3,73, 7(00 始まり)に仕切りを置くと、各区間の玉の個数は 3,3,43, 3, 4 なので 334334 を表します。

ただし、次の 2 つに注意します。

  • 最上位の桁は 11 以上: 位置 00 に仕切りを置かなければよいので、仕切りの位置は 1,…,9+r1, \ldots, 9 + r から選びます。
  • 各桁は 99 以下: 区間に玉が 1010 個入る並べ方は数字として不正なので除きます。

桁数が少ないほど小さいので、r=1,2,…r = 1, 2, \ldots の順に列挙します。桁数が同じなら、仕切りの位置を辞書順に並べたものが数の小さい順と一致します。仕切りの位置が前にあるほど、上の桁が小さくなるからです。

r+1r + 1 桁の完全数は (9+rr)−1\binom{9 + r}{r} - 1 個あり、1111 桁(r=10r = 10)までで 184745184745 個になります。10510^5 個を超えるので、r≤10r \le 10 まで列挙すれば十分です。

Python
from itertools import combinations
ans = []
for r in range(1, 11):
for c in combinations(range(1, 10 + r), r=r):
t = 0
l = []
for x in c:
l.append(x - t)
t = x + 1
l.append(10 + r - t)
if 10 in l:
continue
ans.append(int("".join(map(str, l))))
K = int(input())
print(ans[K - 1])

combinations で仕切りの位置 c を辞書順に列挙しています。t は直前の仕切りの次の位置で、x - t が仕切りの間にある玉の個数、つまりその桁の数字です。最後の区間は列の長さ 10 + r までの玉の個数です。

桁に 10 があるものを除き、残りを数にして ans に入れていきます。

SamCoding Round 7 (Div. 2) B - Calculator

2 つの整数 a,ba, b の和を出力する問題です(−109≤a,b≤109-10^9 \le a, b \le 10^9)。ただし、ソースコードのどこにも + を使ってはいけません。

+ を書かずに足し算をすればよいので、組み込みの関数に任せます。Python なら sum に a,ba, b を渡せば和が求まります。

Python
print(sum(map(int, input().split())))

入力を整数に変換し、sum でそのまま合計しています。

SamCoding Round 7 (Div. 2) A - Percentage Calculation

商品の元の価格 PP と割引率 RR % が与えられます。割引額 D=P×R100D = P \times \frac{R}{100} と、割引後の価格 F=P−DF = P - D を、それぞれ小数点以下 2 桁で出力する問題です(1≤P≤1061 \le P \le 10^6、0≤R≤1000 \le R \le 100)。

式のとおりに計算し、小数点以下 2 桁で出力します。

P×RP \times R は整数なので、DD と FF は小数点以下 2 桁までで正確に表せる値です。浮動小数点数で計算すると誤差は出ますが、ごくわずかなので、小数点以下 2 桁に丸めれば正しい値になります。

Python
P, R = map(int, input().split())
D = P * R / 100
print(f"{D:.2f}")
print(f"{P-D:.2f}")

f"{D:.2f}" で小数点以下 2 桁に丸めて出力しています。

ABC477 E - Wheel Distance

頂点 1,…,N1, \ldots, N が重み AiA_i の辺で円環状につながり、さらに各頂点 ii が中心の頂点 N+1N+1 と重み BiB_i の辺でつながったグラフがあります。QQ 個のクエリ (S,T)(S, T) それぞれについて、頂点 SS から頂点 TT への最短経路の長さを求める問題です(N,Q≤2×105N, Q \le 2 \times 10^5)。

中心の頂点を H=N+1H = N + 1 とし、HH から各頂点への最短距離 FvF_v をダイクストラ法で求めておきます。

T=HT = H のときは、答えは FSF_S です。

T≠HT \ne H のときは、最短経路が HH を通るかどうかで場合分けします。

  • HH を通る場合: SS から HH へ行き、HH から TT へ行く経路になるので、長さは FS+FTF_S + F_T 以上です。逆に、S→HS \to H と H→TH \to T の最短経路をつなげれば長さ FS+FTF_S + F_T の経路が作れます。なので、この場合の最短は FS+FTF_S + F_T です。
  • HH を通らない場合: 円環の上だけを通るので、SS から TT へ時計回りに行くか、反時計回りに行くかの 2 通りです。AA の累積和を Gi=A1+⋯+AiG_i = A_1 + \cdots + A_i とすると、長さはそれぞれ GT−1−GS−1G_{T-1} - G_{S-1} と GN−(GT−1−GS−1)G_N - (G_{T-1} - G_{S-1}) です。

この 3 つの最小値が答えです。前処理が O(Nlog⁡N)O(N \log N)、各クエリが O(1)O(1) です。

cLay
ll@N,@Q,@A[N],@B[N],E[2N],F[N+1],G[N+1]{};int C[2N],D[2N];rep(i,N)C[i]=i,D[i]=(i+1)%N,G[i+1]=G[i]+(E[i]=A[i]),C[N+i]=i,D[N+i]=N,E[N+i]=B[i];wgraph<ll>g;g.setEdge(N+1,2N,C,D,E);g.getDist(N,F);rep(Q){ll@S--,@T--,x;if(N-T)x=F[S]+F[T],x<?=G[T]-G[S],wt(x<?=G[S]+G[N]-G[T]);else wt(F[S]);}

cLay で書いています。頂点は 0 始まりで、0,…,N−10, \ldots, N-1 が円環、NN が中心です。

C、D、E に辺の両端と重みを入れ、wgraph の setEdge で重み付き無向グラフを作り、getDist(N, F) で中心からの最短距離を F に求めています。G は AA の累積和です。

クエリでは x<?= (小さい方を代入する cLay の演算子)で 3 つの候補の最小値をとっています。N-T が 00、つまり TT が中心のときは F[S] を出力します。

Python
from heapq import heappop, heappush
from itertools import accumulate
N, Q = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
for i in range(N):
graph[i].append(((i + 1) % N, A[i]))
graph[(i + 1) % N].append((i, A[i]))
graph[i].append((N, B[i]))
graph[N].append((i, B[i]))
F = [None] * (N + 1)
pq = [(0, N)]
while pq:
d, v = heappop(pq)
if F[v] is not None:
continue
F[v] = d
for u, w in graph[v]:
if F[u] is None:
heappush(pq, (d + w, u))
acc = [0, *accumulate(A)]
ans = []
for _ in range(Q):
S, T = map(int, input().split())
S -= 1
T -= 1
if T == N:
ans.append(F[S])
else:
ans.append(min(F[S] + F[T], acc[T] - acc[S], acc[S] + acc[N] - acc[T]))
print(*ans, sep="\n")

cLay 版と同じ処理です。ダイクストラ法は heapq で書いています。

ABC477 D - Masking Tape

NN 個のマスが一列に並んでいて、はじめはすべて色 a でタイルは置かれていません。次の 2 種類のクエリを QQ 個処理したあとの、各マスの色を求める問題です(N,Q≤3×105N, Q \le 3 \times 10^5)。

  • 1 X:マス XX のタイルの有無を切り替える。
  • 2 C:タイルが置かれていないすべてのマスの色を CC に変える。

タイプ 2 のクエリのたびにタイルのないマスを全部塗り直すと、O(NQ)O(NQ) かかって間に合いません。

そこでクエリを後ろから見ていきます。各マスの最終的な色は、そのマスにタイルがなかった最後のタイプ 2 のクエリで決まります。なので、後ろから見て最初に当たった「そのマスにタイルがない時点のタイプ 2」の色が答えです。一度色が決まったマスは、それより前のクエリの影響を受けません。

具体的には次のようにします。

  1. まずクエリを前から処理して、タイルの状態だけを追い、最後の時点でタイルのないマスの集合 UU を求めます。
  2. はじめの状態を「全マスを a に塗るタイプ 2 のクエリ」とみなして先頭に加えます。
  3. クエリを後ろから処理します。
    • タイプ 2 なら、UU のマスをすべてその色に決めて、UU を空にします。
    • タイプ 1 なら、マス XX の色がまだ決まっていない場合だけ、タイルの切り替えを取り消します(UU に XX があれば除き、なければ加える)。

UU に入るのは色が決まっていないマスだけで、各マスの色が決まるのは 1 回だけです。また UU に加えられるのはタイプ 1 のクエリ 1 回につき高々 1 個なので、全体で O(N+Q)O(N + Q) 回の集合操作で済みます。

cLay
ll@N,@Q,t[Q]={97};string S(N,'!');set<ll>s;rep(i,N)s.insert(i);rep(i,1,Q+1){ll@X;if(X-1){char@C;t[i]=C;}else{ll@Y--;if(!s.insert(Y).second)s.erase(Y);t[i]=-Y;}}rrep(i,Q+1){if(t[i]>0){for(ll p:s)S[p]=t[i];s.clear();}else if(S[-t[i]]<'$')if(!s.insert(-t[i]).second)s.erase(-t[i]);}wt(S);

cLay(C++ っぽいコードを C++ に変換するツール)で書いています。ll@N のように変数名の前に @ を付けると、宣言と同時に標準入力から読み込みます。ll@Y-- は読み込んだ直後に 1 減らして 0 始まりにしています。rep(i, 1, Q + 1) は i=1,…,Qi = 1, \ldots, Q、rrep(i, Q + 1) は i=Q,…,0i = Q, \ldots, 0 のループで、wt は出力です。

t[i] に ii 番目のクエリを記録しています。タイプ 2 なら色の文字コード(正の値)、タイプ 1 なら −Y-Y (YY は 0 始まりのマス番号)を入れます。t[0] = 97 は、はじめの状態を表す「a に塗るクエリ」です。

S は色がまだ決まっていないマスを '!' にしておき、S[-t[i]] < '$' で未決定かどうかを判定しています。集合 s の切り替えは、insert が失敗したら(すでにあったら)erase する形で書いています。

Python
N, Q = map(int, input().split())
queries = [("2", "a")]
untiled = set(range(N))
for _ in range(Q):
t, x = input().split()
if t == "1":
x = int(x) - 1
if x in untiled:
untiled.remove(x)
else:
untiled.add(x)
queries.append((t, x))
ans = [""] * N
for t, x in reversed(queries):
if t == "2":
for p in untiled:
ans[p] = x
untiled.clear()
elif not ans[x]:
if x in untiled:
untiled.remove(x)
else:
untiled.add(x)
print("".join(ans))

cLay 版と同じ処理です。はじめの状態を ("2", "a") としてクエリの先頭に入れ、ans が空文字列のマスを色が未決定のマスとして扱っています。

ABC477 C - Range Search Query

文字列 S,TS, T が与えられます。QQ 個のクエリ (L,R)(L, R) それぞれについて、SS の LL 文字目から RR 文字目までの部分に TT が含まれるかを判定する問題です(∣S∣≤4×105|S| \le 4 \times 10^5、∣T∣≤10|T| \le 10、Q≤2×105Q \le 2 \times 10^5)。

SS の LL 文字目から RR 文字目までに TT が含まれるのは、TT が SS の ii 文字目から始まって出現するような ii が L≤i≤R−∣T∣+1L \le i \le R - |T| + 1 の範囲にあるときです。

そこで、前処理として SS の各位置から TT が始まるかを調べておきます。∣T∣≤10|T| \le 10 なので、各位置で愚直に比べても O(∣S∣∣T∣)O(|S||T|) で間に合います。これの累積和をとっておけば、各クエリでは区間 [L,R−∣T∣+1][L, R - |T| + 1] にある開始位置の個数が O(1)O(1) で求まり、それが 11 以上なら Yes です。

Python
Q = int(input())
S = input()
T = input()
N, M = len(S), len(T)
acc = [0] * (N + 1)
for i in range(N):
acc[i + 1] = acc[i] + S.startswith(T, i)
for _ in range(Q):
L, R = map(int, input().split())
print("Yes" if L - 1 <= R - M and acc[R - M + 1] > acc[L - 1] else "No")

acc[i] は、TT の出現のうち開始位置(0 始まり)が ii 未満のものの個数です。0 始まりで開始位置が L−1L - 1 以上 R−∣T∣R - |T| 以下の出現があるかを、acc[R - M + 1] > acc[L - 1] で調べています。R−L+1<∣T∣R - L + 1 < |T| のときは区間が空なので、先に L - 1 <= R - M で除いています。

Uiua
⋅◌⍥◡(&p⨬"No""Yes">0/-⬚0⊏-:⊜⋕⊸≠@ &sc):⊙:[2⧻]⟜(\+⌕)&sc&sc⋕&sc

⋕&sc で QQ、続く 2 つの &sc で SS と TT を読みます。

⟜(\+⌕) では、⌕ で SS の各位置から TT が始まるかの 0/1 の列を作り、\+ で累積和 PP にします。PkP_k は開始位置(0 始まり)が kk 以下の出現の個数です。⟜ で TT を残しておき、[2⧻] で [2,∣T∣][2, |T|] を作ります。:⊙: で並べ替えて、QQ の下に [2,∣T∣][2, |T|] と PP が来るようにしています。

⍥◡(…) で、[2,∣T∣][2, |T|] と PP を残したまま中の処理を QQ 回繰り返します。中の処理は次のとおりです。

  1. ⊜⋕⊸≠@ &sc でクエリを読んで [L,R][L, R] にします。
  2. -: で [L,R]−[2,∣T∣]=[L−2,R−∣T∣][L, R] - [2, |T|] = [L - 2, R - |T|] を計算します。
  3. ⬚0⊏ で PP からこの 2 か所を取り出し、/- で PR−∣T∣−PL−2P_{R - |T|} - P_{L - 2} を求めます。これが区間内にある開始位置の個数です。L=1L = 1 のときの添字 −1-1 は、⬚0 で 00 として扱っています。
  4. >0 で 11 個以上あるかを判定し、⨬"No""Yes" で文字列を選んで &p で出力します。

最後の ⋅◌ で、残しておいた [2,∣T∣][2, |T|] と PP を捨てています。

ABC477 B - Standing Outliers

数直線上に NN 人がいて、人 ii は座標 XiX_i にいます。自分以外のどの人との距離も DD 以上である人の番号を、昇順にすべて出力する問題です(N≤100N \le 100)。

N≤100N \le 100 なので、各人 ii について他の全員との距離 ∣Xi−Xj∣|X_i - X_j| を調べれば O(N2)O(N^2) で間に合います。

ソートを使うと O(Nlog⁡N)O(N \log N) にもなります。座標を昇順に並べると、ある人に最も近い人は並びで両隣のどちらかです。なので、両隣との差がどちらも DD 以上かどうかだけ調べれば十分です。同じ座標の人がいる場合は差が 0<D0 < D になるので、そのまま正しく判定できます。

Python
N, D = map(int, input().split())
X = list(map(int, input().split()))
ans = [i + 1 for i in range(N) if all(abs(X[i] - X[j]) >= D for j in range(N) if i != j)]
print(len(ans))
print(*ans)

全員の組を調べる O(N2)O(N^2) の解法です。

Uiua
≡&p+1⊚&p/+.⍜⍆(⬚1×⊂1.≥⊣:⧈-)∩(⊜⋕⊸≠@ &sc)

∩(⊜⋕⊸≠@ &sc) で 2 行を読み、それぞれ空白区切りの数値の配列にします。

⍜⍆(…) は、XX をソートしてから中の処理をし、結果を元の順番に戻します。中の処理は次のとおりです。

  1. ⧈- で隣り合う座標の差を求めます。
  2. ⊣: で 1 行目の [N,D][N, D] から DD を取り出し、≥ で各差が DD 以上かどうかの 0/1 の列にします。この列の kk 番目は、ソート後の kk 番目と k+1k+1 番目の人の間が離れているかを表します。
  3. ⊂1. で、この列を複製して片方の先頭に 11 を付けます。⬚1× で、もう片方の末尾を 11 で埋めて掛け合わせます。これで各人について「左隣とも右隣とも DD 以上離れているか」が求まります。両端の人は、いない側の隣を 11(離れている)として扱っています。

あとは /+. で人数を数えて &p で出力し、⊚ で 1 になっている位置を取り出して +1 で 1 始まりの番号にし、≡&p で出力しています。番号は 1 行に 1 つずつ出力しますが、AtCoder のジャッジは空白と改行の違いを区別しないので、これで通ります。

ABC477 A - Traffic Light

信号機の色は B(青)→ Y(黄)→ R(赤)→ B → … の順に周期的に変わります。現在の色 cc が与えられるので、次の色を出力する問題です。

"BYR" の中で cc が何番目かを調べ、同じ位置にある「次の色」を "YRB" から取り出せば答えになります。

現在の色BYR
次の色YRB
Python
print("YRB"["BYR".index(input())])
Uiua
&p⊏⊗&sc"BYR""YRB"

"YRB" と "BYR" を積み、&sc で cc を読みます。⊗ で "BYR" の中での cc の位置を求め、⊏ でその位置の文字を "YRB" から取り出して &p で出力しています。Python 版と同じ処理です。

なお、AtCoder の Uiua は最新版と ⊗(index of)の引数の順序が逆です。最新版では ⊗ の 2 つの引数が入れ替わるので、このコードはそのままでは動きません。

ABC478 F - Min-First Search

頂点 1,…,N1, \ldots, N の木 TT について、頂点 11 から始めて「訪問候補の集合 SS から番号が最小の頂点を取り出して訪問し、その未訪問の隣接頂点を SS に加える」ことを繰り返したときの訪問順を f(T)f(T) とします。順列 QQ (Q1=1Q_1 = 1) が与えられるので、f(T)=Qf(T) = Q となる木 TT の個数を 998244353998244353 で割った余りを求める問題です(N≤2×105N \le 2 \times 10^5)。

以下、添字を 00 始まりにして Q0=1Q_0 = 1 とします。

i≥1i \ge 1 について、QiQ_i を SS に加えたのは、QiQ_i より先に訪問された隣接頂点です。木なので、QiQ_i に隣接する頂点のうち QiQ_i より先に訪問されるものはちょうど 1 つで、これを QiQ_i の親 QkQ_k (k<ik < i) と呼ぶことにします。木は「各 i≥1i \ge 1 の親の選び方」と 1 対 1 に対応するので、条件を満たす親の選び方を数えればよいです。

QkQ_k を訪問した時点で QiQ_i が SS に入り、QiQ_i は ii 番目に取り出されるまで SS に残ります。その間に取り出される Qk+1,…,Qi−1Q_{k+1}, \ldots, Q_{i-1} はそのときの SS の最小値なので、すべて QiQ_i より小さくなければなりません。

そこで、QiQ_i より前にある QiQ_i より大きい要素のうち最も後ろのものの位置を pip_i とします(なければ pi=0p_i = 0)。すると親の位置 kk の条件は

pi≤k≤i−1p_i \le k \le i - 1

で、選び方は i−pii - p_i 通りです(QpiQ_{p_i} 自身は大きくても、親として先に訪問されるので構いません)。

逆に、すべての ii についてこの範囲で親を選べば、ii 番目の時点で SS に残っている他の頂点 QmQ_m (m>im > i) は、親が ii より前にあるので条件から Qi<QmQ_i < Q_m となり、QiQ_i が最小として正しく取り出されます。したがって各 ii の選び方は独立で、答えは

∏i=1N−1(i−pi)\prod_{i=1}^{N-1} (i - p_i)

です。

pip_i は「直前にある自分より大きい要素の位置」なので、

  • 区間最大値のセグメント木で min_left を使って二分探索する(O(Nlog⁡N)O(N \log N))
  • 単調スタックの要領で、直前の大きい要素へのポインタをたどる(全体で O(N)O(N))

のどちらでも求められます。

C++(セグメント木)
#include "ou-library/modint.hpp"
#include "ou-library/segtree.hpp"
#include "sh-library/base/all"
using mint = modint998244353;
void solve() {
LL(N);
VL(Q, N);
Q--;
mint ans = 1;
RMaxQ<ll> seg(Q);
rep(i, 1, N) {
ll j = seg.min_left(i, [&](ll x) { return x <= Q[i]; });
if (j)
j--;
ans *= i - j;
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

min_left(i, x <= Q[i]) で「Ql,…,Qi−1Q_l, \ldots, Q_{i-1} がすべて QiQ_i 以下になる最小の ll」を求め、その 1 つ前が pip_i です。RMaxQ は区間最大値のセグメント木です。

使用ライブラリ:cpp_include@6c2f83f

cLay(ポインタをたどる)
#define MD 998244353
ll@N,@Q[N],g[N],p;mint x=1;rep(i,1,N){p=i-1;while(p&&Q[p]<Q[i])p=g[p];g[i]=p;x*=i-p;}wt(x);

g[i] に pip_i を記録しておき、Qi−1Q_{i-1} から始めて自分より小さい間は g をたどることで pip_i を求めています。Q0=1Q_0 = 1 は最小なので、より大きい要素がなければ p=0p = 0 で止まります。

ABC478 E - lt and le

11 以上 NN 以下の整数からなる長さ NN の列 AA で、QQ 個の条件「Au≤AvA_u \le A_v」または「Au<AvA_u < A_v」をすべて満たすものがあるかを判定し、あれば 1 つ出力する問題です(N,Q≤2×105N, Q \le 2 \times 10^5)。

条件 Au≤AvA_u \le A_v、Au<AvA_u < A_v のどちらも、頂点 uu から vv への辺だと思ってグラフを作り、強連結成分(SCC)分解します。

  • 同じ SCC の中の頂点は、辺をたどって一周できるので、Au≤⋯≤AuA_u \le \cdots \le A_u となり、すべて同じ値でなければなりません。したがって、<< の辺の両端が同じ SCC にあれば No です。
  • そうでなければ、SCC をトポロジカル順に並べたときの番号(11 始まり)をそのまま AA にすれば条件をすべて満たします。異なる SCC 間の辺は必ず番号が増える向きなので << も ≤\le も満たし、同じ SCC 内の辺はすべて ≤\le なので等しい値で満たします。番号は NN 以下です。

ACL の scc_graph::scc() は成分をトポロジカル順に返すので、その添字をそのまま使えます。計算量は O(N+Q)O(N + Q) です。

本番では次の方針で提出し、AC しました。

  1. ≤\le の辺だけで SCC 分解し、同じ成分を「等しい値になるグループ」として DSU でまとめる
  2. すべての辺で SCC 分解し、異なるグループが同じ SCC に入ったら No
  3. そうでなければ SCC の番号を出力する

ところが、同じグループ(等しくなることが決まった頂点どうし)の間に << の辺がある場合を見落としていました。<< の辺で弾いていたのは u=vu = v のときだけです。たとえば

2 3
0 1 2
0 2 1
1 1 2

は A1=A2A_1 = A_2 が必要なのに A1<A2A_1 < A_2 も要求されているので答えは No ですが、本番のコードは Yes と 1 1 を出力してしまいます。テストケースにこの形がなかったため通ってしまったようです。

上の解法のように、<< の辺の両端が同じ SCC にあるかを最後に確かめれば、この場合も正しく No になります(修正版で AC を確認しました)。そもそも DSU も 2 回目の SCC も要らず、SCC 1 回で十分でした。

C++(修正版・AC)
#include "atcoder/scc"
#include "sh-library/base/all"
void solve() {
LL(N, Q);
VAL(TUV, Q, 3);
atcoder::scc_graph g(N);
for (auto &[t, u, v] : TUV) {
u--, v--;
g.add_edge(u, v);
}
auto scc = g.scc();
vl ans(N);
rep(i, scc.size()) {
for (ll x : scc[i])
ans[x] = i + 1;
}
for (auto [t, u, v] : TUV) {
if (t == 1 and ans[u] == ans[v]) {
No;
}
}
print("Yes");
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

使用ライブラリ:cpp_include@6c2f83f

C++(本番の提出・嘘解法)
#include "atcoder/dsu"
#include "atcoder/scc"
#include "sh-library/base/all"
void solve() {
LL(N, Q);
VAL(TUV, Q, 3);
atcoder::dsu h(N);
{
atcoder::scc_graph g0(N);
for (auto &[t, u, v] : TUV) {
u--, v--;
if (t == 0) {
g0.add_edge(u, v);
} else {
if (u == v) {
print("No");
return;
}
}
}
auto tmp = g0.scc();
for (auto &x : tmp) {
rep(i, 1, x.size()) {
h.merge(x[0], x[i]);
}
}
}
{
atcoder::scc_graph g(N);
for (auto &[t, u, v] : TUV) {
if (t == 0 && h.same(u, v)) {
g.add_edge(v, u);
}
g.add_edge(u, v);
}
auto tmp = g.scc();
for (auto &x : tmp) {
rep(i, 1, x.size()) {
if (h.same(x[0], x[i]))
continue;
print("No");
return;
}
}
vl ans(N);
rep(i, tmp.size()) {
for (ll a : tmp[i]) {
ans[a] = i + 1;
}
}
print("Yes");
print(ans);
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

使用ライブラリ:cpp_include@6c2f83f

ABC478 D - Range Set Insertion Query

はじめ空の集合 S1,…,SNS_1, \ldots, S_N に対して、「SL,…,SRS_L, \ldots, S_R に値 XX を追加する」という操作を QQ 回行います。最後に各 SiS_i の要素数を求める問題です(N,Q≤2×105N, Q \le 2 \times 10^5)。

SiS_i の要素数は「ii を含む区間が 1 つ以上ある値 XX の個数」です。同じ XX の区間が重なっていると、単純にいもす法で数えたときに XX を 2 回以上数えてしまうのが問題です。

そこで、値 XX ごとに区間をまとめ、重なっている区間を併合して互いに重ならない区間の集まりにしてから、いもす法で +1+1 します。こうすれば、各位置で同じ XX が数えられるのは高々 1 回です。

区間の併合は、区間を左端でソートして前から見ていき、今の区間の左端が直前にまとめた区間の右端以下なら右端を伸ばし、そうでなければ新しい区間として追加すればできます。

XX でソートしてから同じ XX ごとに処理し、計算量はソートの O(Qlog⁡Q)O(Q \log Q) といもす法の O(N)O(N) を合わせて O(N+Qlog⁡Q)O(N + Q \log Q) です。

コードでは区間を半開区間 [L−1,R)[L - 1, R) で持っているので、隣り合っているだけの区間(右端 == 次の左端)も併合されますが、和集合は変わらないので問題ありません。

Python
from operator import itemgetter
N, Q = map(int, input().split())
LRX = [tuple(map(int, input().split())) for i in range(Q)]
LRX.sort(key=itemgetter(2))
imos = [0] * (N + 1)
i = 0
while i < Q:
x = LRX[i][2]
tmp = [(LRX[i][0] - 1, LRX[i][1])]
i += 1
while i < Q and LRX[i][2] == x:
tmp.append((LRX[i][0] - 1, LRX[i][1]))
i += 1
tmp.sort()
l = []
for a, b in tmp:
if l and l[-1][1] >= a:
l[-1] = (l[-1][0], max(l[-1][1], b))
else:
l.append((a, b))
for a, b in l:
imos[a] += 1
imos[b] -= 1
for i in range(N):
imos[i + 1] += imos[i]
print(*imos[:N])

ABC478 C - Sort Subarray

長さ NN の整数列 AA の、長さ KK の連続部分列をちょうど 1 回だけ選んで昇順にソートします。その結果 AA 全体を昇順にできるかを判定する問題です(1≤K<N≤2×1051 \le K < N \le 2 \times 10^5)。

AA を昇順にソートした列を SS とします。区間 [i,i+K)[i, i + K) をソートして AA 全体が SS になるのは

  • 区間より前が SS と一致している(Aj=SjA_j = S_j, j<ij < i)
  • 区間より後ろが SS と一致している(Aj=SjA_j = S_j, j≥i+Kj \ge i + K)

のときです。このとき、区間の中の値の集まりも SS の対応する部分と一致するので、区間をソートすれば SS になります。逆に、区間の外は操作で変わらないので、この 2 つは必要です。

そこで

  • LiL_i = 先頭から ii 個がすべて SS と一致しているか
  • RiR_i = 位置 ii 以降がすべて SS と一致しているか

を前と後ろから求めておき、LiL_i かつ Ri+KR_{i+K} となる ii があるかを調べます。計算量はソートの O(Nlog⁡N)O(N \log N) です。

Python
N, K = map(int, input().split())
A = list(map(int, input().split()))
s = sorted(A)
l = [True]
for i in range(N):
l.append(l[-1] and A[i] == s[i])
r = [True]
for i in reversed(range(N)):
r.append(r[-1] and A[i] == s[i])
r.reverse()
if any(l[i] and r[i + K] for i in range(N - K + 1)):
print("Yes")
else:
print("No")
Uiua
&p⨬"Yes""No">⊣:/+>0×⍜⇌\+⟜\+≠⍆.∩(⊜⋕⊸≠@ &sc)

≠⍆. で AA とソートした列を比べ、ずれている位置を 11 にした列を作ります。⟜\+ で前からの累積和、⍜⇌\+ で後ろからの累積和を取って × で掛けると、「前にも後ろにもずれがある位置」、つまりずれている最初の位置から最後の位置までが正になります。/+>0 でその長さを数え、⊣ で取り出した KK と > で比べて、KK を超えていれば "No"、そうでなければ "Yes" を ⨬ で選んで出力しています。

ABC478 B - Topping

ii 番目のトッピングは価格 ii、嬉しさ WiW_i です。価格の総和が VV 以下になるように相異なる 3 種類を選ぶとき、嬉しさの総和の最大値を求める問題です(N≤100N \le 100)。

N≤100N \le 100 なので、3 つの組 i<j<ki < j < k を全部試しても (1003)≈1.6×105\binom{100}{3} \approx 1.6 \times 10^5 通りで間に合います。価格の総和 i+j+ki + j + k が VV 以下のものについて、嬉しさの総和の最大値を取ります。

コードでは添字を 00 始まりにしているので、価格の総和は i+j+k+3i + j + k + 3 になります。

Python
from itertools import combinations
N, V = map(int, input().split())
W = list(map(int, input().split()))
ans = 0
for i, j, k in combinations(range(N), r=3):
if i + j + k + 3 > V:
continue
ans = max(ans, W[i] + W[j] + W[k])
print(ans)
Uiua
/↥▽<⊙(+2∩(≡/+⧅<3)⇡):°⊟:∩(⊜⋕⊸≠@ &sc)

∩(⊜⋕⊸≠@ &sc) で 2 行を数値の配列として読み、°⊟ で 1 行目を NN と VV に分けます。⧅<3 で添字が増加する 3 つ組をすべて作り、≡/+ で各組の和を取ります。これを ∩ で添字 ⇡ NN と WW の両方に行い、添字の和(に 22 を足したもの)が VV 未満、つまり価格の総和が VV 以下の組だけを ▽ で残して、/↥ で最大値を取っています。

ABC478 A - Grapes

MM 粒のぶどうを、人 1,2,…,N1, 2, \ldots, N の順に 1 粒ずつ繰り返し配るとき、各人がもらう粒数を求める問題です(N≤100N \le 100、M≤104M \le 10^4)。

jj 粒目 (1≤j≤M1 \le j \le M) をもらうのは、j≡k(modN)j \equiv k \pmod N となる人 kk です。人 kk がもらう粒数は、11 以上 MM 以下で NN で割ると kk 余る(人 NN なら割り切れる)整数の個数なので

⌊M−k+NN⌋\left\lfloor \frac{M - k + N}{N} \right\rfloor

です。MM が小さいので実際に配るシミュレーションでも間に合いますが、式で一発で出せます。

コードでは i=N−ki = N - k として、i=N−1,…,0i = N - 1, \ldots, 0 の順に ⌊(M+i)/N⌋\lfloor (M + i) / N \rfloor を出力しています。

Python
N, M = map(int, input().split())
for i in reversed(range(N)):
print((M + i) // N)
Uiua
≡&p⇌⌊÷⟜(+⇡)°⊟⊜⋕⊸≠@ &sc

&sc で 1 行読み、⊜⋕⊸≠@ で空白区切りの数値にして °⊟ で NN と MM に分けます。⟜(+⇡) で M+[0,1,…,N−1]M + [0, 1, \ldots, N - 1] を作り、⌊÷ で NN で割って切り捨て、⇌ で逆順にして ≡&p で 1 行ずつ出力しています。Python 版と同じ計算です。

Blitz Round #25 E - Circles are POINTS !

平面上の nn 個の格子点からなる集合があり、そのうち 2 点は base point と呼ばれます。次の 2 種類のクエリを qq 回処理します。

  • 点 (x,y)(x, y) を集合に追加する(まだ集合にない点)
  • 点 (x,y)(x, y) を集合から削除する(集合にあり、base point ではない点)

最初の状態と各クエリの後に、集合のすべての点を通る円が描けるかを判定する問題です。

  • 2≤n≤2⋅1052 \le n \le 2 \cdot 10^5、0≤q≤2⋅1050 \le q \le 2 \cdot 10^5、∣x∣,∣y∣≤106|x|, |y| \le 10^6、テストケースの nn の総和と qq の総和はそれぞれ 2⋅1052 \cdot 10^5 以下

正確な問題文は元の問題ページを見てください。

base point を固定して円で分類する

Section titled “base point を固定して円で分類する”

base point を A,BA, B とします。A,BA, B は削除されないので常に集合にあり、すべての点を通る円があるなら、それは A,BA, B を通る円です。

base point 以外の点 PP について、

  • PP が直線 ABAB 上にあるなら、異なる 3 点が一直線上に並ぶので円は描けません
  • そうでなければ、A,B,PA, B, P を通る円がただ 1 つ決まります

したがって、答えが YES になるのは「直線 ABAB 上の点がなく、base point 以外のすべての点について A,B,PA, B, P を通る円が同じ」ときです。点を「A,B,PA, B, P を通る円」で分類して、種類が 1 種類以下かを見ればよいことになります。

円の中心の座標で分類すると浮動小数点数の誤差が気になるので、整数だけで計算できる量を使います。

AA を原点に平行移動して u=B−Au = B - A とすると、原点と uu を通る円はすべて、あるパラメータ λ\lambda を使って

∣z∣2−z⋅u=λ (u×z)|z|^2 - z \cdot u = \lambda \, (u \times z)

と書けます(⋅\cdot は内積、×\times は外積 x1y2−y1x2x_1 y_2 - y_1 x_2)。

この形に書ける理由

平面上の円は、ww を定数ベクトル、FF を定数として

∣z∣2+w⋅z+F=0|z|^2 + w \cdot z + F = 0

と書けます(中心 −w/2-w/2、半径の 2 乗 ∣w∣2/4−F|w|^2/4 - F)。

  • 原点を通るので、z=0z = 0 を代入して F=0F = 0
  • uu を通るので、z=uz = u を代入して ∣u∣2+w⋅u=0|u|^2 + w \cdot u = 0

後者について、w=−u+dw = -u + d とおくと

∣u∣2+(−u+d)⋅u=d⋅u=0|u|^2 + (-u + d) \cdot u = d \cdot u = 0

となるので、dd は uu に直交するベクトルです。uu を 90° 回したベクトルを u⊥=(−uy,ux)u^\perp = (-u_y, u_x) とすると、uu に直交するベクトルは u⊥u^\perp の実数倍なので、d=−λ u⊥d = -\lambda\, u^\perp (λ∈R\lambda \in \mathbb{R}) と書けます。よって

w=−u−λ u⊥w = -u - \lambda\, u^\perp

です。これを代入し、u⊥⋅z=uxzy−uyzx=u×zu^\perp \cdot z = u_x z_y - u_y z_x = u \times z を使うと

∣z∣2−z⋅u=λ (u×z)|z|^2 - z \cdot u = \lambda\, (u \times z)

になります。

どの λ\lambda でも w≠0w \ne 0 なので半径の 2 乗 ∣w∣2/4|w|^2/4 は正で、本物の円になります。また、円が決まれば係数 ww が決まり、ww から λ\lambda が決まります。つまり、A,BA, B を通る円と実数 λ\lambda は 1 対 1 に対応します。

z=P−Az = P - A を代入して λ\lambda について解くと

λ=(P−A)⋅(P−B)(B−A)×(P−A)\lambda = \frac{(P - A) \cdot (P - B)}{(B - A) \times (P - A)}

です。円と λ\lambda は 1 対 1 に対応するので、2 点について A,BA, B とそれぞれを通る円が同じであることと、それぞれから求めた λ\lambda が等しいことは同値です。分母が 00 になるのは PP が直線 ABAB 上にあるときです。

λ\lambda は分子・分母とも整数なので、gcd で約分して分母を正にそろえた (分子, 分母) の組を辞書のキーにすれば、誤差なく分類できます。

base point 以外の点のキーの個数を Counter で持ち、追加・削除のたびに増減します。直線 ABAB 上の点はキーを None にしておけば、

  • None がない
  • キーの種類が 1 種類以下

のとき YES です。各点のキーの計算は gcd 1 回なので、座標の範囲を CC として全体で O((n+q)log⁡C)O((n + q) \log C) です。

公式解説も、base point A,BA, B を固定して各点 PP について A,B,PA, B, P を通る円を考える点は同じです。直線 ABAB 上にある点の個数と、A,B,PA, B, P の外接円の中心(外心)の集合を管理し、直線上の点がなく外心がすべて一致するときに YES としています。外心は 2 本の垂直二等分線の交点として計算しています。

Python(upsolve)
from math import gcd
from collections import Counter
for _ in range(int(input())):
n, q, a, b = map(int, input().split())
P = [tuple(map(int, input().split())) for _ in range(n)]
ax, ay = P[a - 1]
bx, by = P[b - 1]
ux, uy = bx - ax, by - ay
def key(x, y):
# λ = (P-A)・(P-B) / (B-A)×(P-A) を約分したもの。直線 AB 上なら None
num = (x - ax) * (x - bx) + (y - ay) * (y - by)
den = ux * (y - ay) - uy * (x - ax)
if den == 0:
return None
if den < 0:
num, den = -num, -den
g = gcd(num, den)
return (num // g, den // g)
cnt = Counter()
for i, (x, y) in enumerate(P):
if i != a - 1 and i != b - 1:
cnt[key(x, y)] += 1
def ok():
return None not in cnt and len(cnt) <= 1
print("YES" if ok() else "NO")
for _ in range(q):
c, x, y = input().split()
x, y = int(x), int(y)
k = key(x, y)
if c == "+":
cnt[k] += 1
else:
cnt[k] -= 1
if cnt[k] == 0:
cnt.pop(k)
print("YES" if ok() else "NO")