ABC239

はじめに  

目次

C: Knight Fork

D: Prime Sum Game

E: Subtree K-th Max

C: Knight Fork

問題のページにわかりやすい図があったおかげで解けました。
図を書いてみること、実験をしてみることを心になじませます。
今回の問題では距離 の格子点(整数の組)ということで探索範囲を絞ることができます。
2回、距離 を移動してもう一方の座標に到達するかを調べます。

2回移動

#相対的な位置の一覧 (書き下せるほどの少ない例なら書いてしまう)
cand_rel_list = [(2,1),(1,2),(-2,1),(-1,2),(-2,-1),(-1,-2),(2,-1),(1,-2)] 

for cand_op in cand_rel_list:
    cand = (x1-cand_op[0]-x2,y1-cand_op[1]-y2) #1回移動
    if cand in cand_rel_list: #もう一回移動できる範囲に目標の座標があるか
        flag = True 
 
if flag:
    print('Yes')
else:
    print('No')

D: Prime Sum Game

素数とは次のような整数です．

素数（そすう、英: prime number）とは、2 以上の自然数で、
正の約数が 1 と自分自身のみであるもののことである。

素数-Wikipedia

素数を求めるには約数が存在するかを調べていけばよいです． 約数が存在するとき2つ以上の整数で表されるため の値まで調べれば約数の候補をすべて考慮することができます．

今回の問題では勝敗を決定するために素数のリストが必要になります．素数リストを作成するためにエラトステネスの篩を使用します．

エラトステネスの篩

#author: kyopro_friends

prime=[True]*201
prime[0]=False
prime[1]=False
for p in range(15):
  if prime[p]:
    for i in range(p*p,201,p):
      prime[i]=False

E: Subtree K-th Max

公式の解説に出てくる用語を調べる必要がある。

要更新 !

オイラーツアー

セグメントツリー

座標圧縮

Wavelet Matrix

参考文献

公式C解説
公式D解説
公式E解説