A - Difference Max
はじめ，絶対値が大きいものを出力するものと勘違いしてしまいました．a, b = map(int, input().split()) c, d = map(int, input().split()) print(max(a-c, a-d, b-c, b-d))
4パターン考えてしまっていますが，不要でした．max(x)-min(y)が答えなので，b-cを出力すればよいだけでした．．．
a, b = map(int, input().split()) c, d = map(int, input().split()) print(b - c)
B - Round Down
はじめはprint(int(float(input())))
でいけるかと思ったのですが，桁の大きい数に対応できませんでした．
そこで，文字列として扱い，小数点を見つける方針で対応しました．
x = str(input()) ans = x for i in range(len(x)): if x[i] == '.': ans = x[:i] break print(ans)
上のようにループで位置を探さなくても，str.find()で対象文字列のスタート位置を取得できるようです．
x = input() dot_pos = x.find('.') if dot_pos != -1 : x = x[:dot_pos] print(x)
C - Doubled
$N$を左右に分割し，左の値を右にコピーできる方法を出力する方針を考えたのですが（左右の数字の大小関係で例外を除く必要がある），うまくできず一旦保留しました．（追記）上のアイディアで，一応できました．例外処理だらけでバグ取りが大変．．．
n = int(input()) l = len(str(n)) if l > 1: right = str(n)[l//2 + l%2:] left = str(n)[:l//2 + l%2] else: print('0') exit() if int(left) <= int(right): print(left) else: if len(left) > len(right): print(int('9'*(len(left)-1))) else: print(int(left)-1)
全探索のロジックが簡単に書けるんですね．全探索でない方法を考えてしまう傾向があります．．．公式解説のコードは以下でした．
N = int(input()) for i in range(1, 1000001): if int(str(i) * 2) > N: print(i - 1) exit()
D - Hanjo
グリッド点の集合を作って$B$点を除き，残った点が2×1の形になるか，全パターンを調べようと考えましたが，方法がわからず．．．【2021.03.28追記】AtCoder Beginner Contest 197 - 競プロはじめましたのC - ORXORを理解したので，わかりそうな気がしてきました．
まずは，公式解説を理解することを目指します．そのためには，ビット演算によるフラグ管理を理解する必要があります．これについては，次が参考になります：
ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜 - Qiita
というわけで，公式解説にコメントを加えたのが以下です．理解できました！！！2状態をビットで表すと簡単にかけるんですね．面白いです．
bitは，長方形のマス目の各行を左から順に並べたものになっています．つまり，ビット$i$の下側に対応するマス目は，$i+W$となります．
H, W, A, B = map(int, input().split()) ans = 0 # bitのi番目にタイルを配置することを考える． # (長方形タイル：A枚， 正方形タイル：B枚) def dfs(i, bit, A, B): # 全部のbitを埋めたらans+1 if i == H * W: global ans ans += 1 return # bitにi番目のフラグが立っていれば，スキップ(i+1へ) if bit >> i & 1: dfs(i + 1, bit, A, B) return # 正方形タイル(if文はゼロのときのみFalseになる) if B: # bitにi番目のフラグを立て，B-1 dfs(i + 1, bit | 1 << i, A, B - 1) # 長方形タイル(if文はゼロのときのみFalseになる) if A: # 横置き # if 「右端を表すbitでない」 and 「bitにi+1番目のフラグがない」 if i % W != W - 1 and not bit & 1 << (i + 1): # bitにi, i+1番目のフラグを立て，A-1 dfs(i + 1, bit | 1 << i | 1 << (i + 1), A - 1, B) # 縦置き # if 下のマスが存在すること(iの下のマスはi+W) if i + W < H * W: # bitにi, i+W番目のフラグを立て，A-1 dfs(i + 1, bit | 1 << i | 1 << (i + W), A - 1, B) dfs(0, 0, A, B) print(ans)
E - Filters
単純に合成関数を計算してTLEになりました．式を変形すればよいのだろうということは想像できましたが，良い方法が思いつかず．．．もうちょっと考えてみます．
def f(t, a, x): if t==1: return x+a elif t==2: return max(x, a) else: return min(x, a) N = int(input()) a = [] t = [] for i in range(N): ai, ti = map(int, input().split()) a.append(ai) t.append(ti) Q = int(input()) x = list(map(int, input().split())) for i in x: ans = f(t[0], a[0], i) for j in range(1, N): ans = f(t[j], a[j], ans) print(ans)
結局，良い方法を思いつかず，回答を見ました．
公式解説の補足をします．
まず，max，minの計算については
\begin{aligned}
&\max\bigl(a, \min(b,c)\bigr) \\
&=
\begin{cases}
\, \max\bigl(a, b\bigr) & (b\leq c) \\
\, \max\bigl(a, c\bigr) & (c < b)
\end{cases} \\
&=\min \bigl(\max\bigl(a, b\bigr), \max\bigl(a, c\bigr) \bigr)
\end{aligned}
や&\max\bigl(a, \min(b,c)\bigr) \\
&=
\begin{cases}
\, \max\bigl(a, b\bigr) & (b\leq c) \\
\, \max\bigl(a, c\bigr) & (c < b)
\end{cases} \\
&=\min \bigl(\max\bigl(a, b\bigr), \max\bigl(a, c\bigr) \bigr)
\end{aligned}
\begin{aligned}
&\min\bigl(a, \max(b,c)\bigr) \\
&=
\begin{cases}
\, \min\bigl(a, b\bigr) & (b\geq c) \\
\, \min\bigl(a, c\bigr) & (c > b)
\end{cases} \\
&=\max \bigl(\min\bigl(a, b\bigr), \min\bigl(a, c\bigr) \bigr)
\end{aligned}
などを考えればわかります．&\min\bigl(a, \max(b,c)\bigr) \\
&=
\begin{cases}
\, \min\bigl(a, b\bigr) & (b\geq c) \\
\, \min\bigl(a, c\bigr) & (c > b)
\end{cases} \\
&=\max \bigl(\min\bigl(a, b\bigr), \min\bigl(a, c\bigr) \bigr)
\end{aligned}
解説の計算結果から，
\begin{aligned}
&
\begin{cases}
\, f(x)= \min(\gamma_{1}, \max(\beta_{1}, x+\alpha_{1})) \\
\, g(x)= \min(\gamma_{2}, \max(\beta_{2}, x+\alpha_{2}))
\end{cases}
\end{aligned}
であるとき&
\begin{cases}
\, f(x)= \min(\gamma_{1}, \max(\beta_{1}, x+\alpha_{1})) \\
\, g(x)= \min(\gamma_{2}, \max(\beta_{2}, x+\alpha_{2}))
\end{cases}
\end{aligned}
\begin{aligned}
&g\bigl(f(x)\bigr)=\min(\gamma, \max(\beta, x+\alpha)) \\
&\qquad
\begin{cases}
\, \gamma=\min(\gamma_{2}, \max(\beta_{2}, \gamma_{1}+\alpha_{2})) \\
\, \beta=\max(\beta_{2}, \min(\gamma_{1} + \alpha_{2}, \beta_{1} + \alpha_{2})) \\
\, \alpha=\alpha_{1} + \alpha_{2}
\end{cases}
\end{aligned}
です．&g\bigl(f(x)\bigr)=\min(\gamma, \max(\beta, x+\alpha)) \\
&\qquad
\begin{cases}
\, \gamma=\min(\gamma_{2}, \max(\beta_{2}, \gamma_{1}+\alpha_{2})) \\
\, \beta=\max(\beta_{2}, \min(\gamma_{1} + \alpha_{2}, \beta_{1} + \alpha_{2})) \\
\, \alpha=\alpha_{1} + \alpha_{2}
\end{cases}
\end{aligned}
ここで，$g(x)=f_{i}(x)=\min(\gamma_{2}, \max(\beta_{2}, x+\alpha_{2}))$の場合は
\begin{aligned}
(\gamma_{2}, \beta_{2}, \alpha_{2})
&=
\begin{cases}
\, (\infty, - \infty, a_{i}) & (t_{i}=1) \\
\, (\infty, a_{i}, 0) & (t_{i}=2) \\
\,(a_{i}, -\infty, 0) & (t_{i}=3)
\end{cases}
\end{aligned}
と表せるので，合成後のパラメータは$a_{i}$を用いて(\gamma_{2}, \beta_{2}, \alpha_{2})
&=
\begin{cases}
\, (\infty, - \infty, a_{i}) & (t_{i}=1) \\
\, (\infty, a_{i}, 0) & (t_{i}=2) \\
\,(a_{i}, -\infty, 0) & (t_{i}=3)
\end{cases}
\end{aligned}
\begin{aligned}
\gamma&=\min(\gamma_{2}, \max(\beta_{2}, \gamma_{1}+\alpha_{2})) \\
&=
\begin{cases}
\, \gamma_{1}+a_{i} & (t_{i}=1) \\
\, \max(a_{i}, \gamma_{1})& (t_{i}=2) \\
\, \min(a_{i}, \gamma_{1}) & (t_{i}=3)
\end{cases} \\
\beta&=\max(\beta_{2}, \min(\gamma_{1} + \alpha_{2}, \beta_{1} + \alpha_{2})) \\
&=
\begin{cases}
\, \beta_{1}+a_{i} & (t_{i}=1) \\
\, \max(a_{i}, \beta_{1}) & (t_{i}=2) \\
\, \min(a_{i}, \beta_{1}) & (t_{i}=3)
\end{cases} \\
\alpha&=\alpha_{1} + \alpha_{2} \\
&=
\begin{cases}
\, \alpha_{1} + a_{i} & (t_{i}=1) \\
\, \alpha_{1} & (t_{i}=2) \\
\, \alpha_{1} & (t_{i}=3)
\end{cases} \\
\end{aligned}
と更新されます．\gamma&=\min(\gamma_{2}, \max(\beta_{2}, \gamma_{1}+\alpha_{2})) \\
&=
\begin{cases}
\, \gamma_{1}+a_{i} & (t_{i}=1) \\
\, \max(a_{i}, \gamma_{1})& (t_{i}=2) \\
\, \min(a_{i}, \gamma_{1}) & (t_{i}=3)
\end{cases} \\
\beta&=\max(\beta_{2}, \min(\gamma_{1} + \alpha_{2}, \beta_{1} + \alpha_{2})) \\
&=
\begin{cases}
\, \beta_{1}+a_{i} & (t_{i}=1) \\
\, \max(a_{i}, \beta_{1}) & (t_{i}=2) \\
\, \min(a_{i}, \beta_{1}) & (t_{i}=3)
\end{cases} \\
\alpha&=\alpha_{1} + \alpha_{2} \\
&=
\begin{cases}
\, \alpha_{1} + a_{i} & (t_{i}=1) \\
\, \alpha_{1} & (t_{i}=2) \\
\, \alpha_{1} & (t_{i}=3)
\end{cases} \\
\end{aligned}
回答例のhigh, low, addがそれぞれ$\gamma, \beta ,\alpha$に対応します．
F - Substring 2
$S$と$T$を2進数にした上で，$S$から$T$と同じ長さを切り出して差分比較（XORの1の数を数える）すればよい，という方針で作りましたがTLEでした．S = str(input()) T = str(input()) l = len(T) d = len(S) - len(T) T2 = format(int(T, 2), '#0'+str(l)+'b') ans = float('inf') for i in range(d+1): S2 = format(int(S[i:i+l], 2), '#0'+str(l)+'b') num = str(bin(int(S2, 0)^int(T2, 0))).count('1') if num < ans: ans = num print(ans)
というわけで，公式解説を見ていきます．
$S,T$の$i$文字目をそれぞれ$s[i], t[i]$とするとき
\begin{aligned}
\min \Biggl\{\sum_{j=0}^{|T|-1} s[i+j]\oplus t[j] \,\biggl|\, 0\leq i \leq |S|-|T| \Biggr\}
\end{aligned}
（$\oplus$はXOR）を求めれば良い，という方針までは同じでした．\min \Biggl\{\sum_{j=0}^{|T|-1} s[i+j]\oplus t[j] \,\biggl|\, 0\leq i \leq |S|-|T| \Biggr\}
\end{aligned}
$T$の文字列を左右反転させたもの（逆順にしたもの）を$\tilde{T}$とします．つまり，$\tilde{T}$の$i$文字目は，$\tilde{t}[i]=t[|T| - 1 - i]$です．すると，
\begin{aligned}
&\sum_{j=0}^{|T|-1} s[i+j]\oplus t[j] \\
&=\sum_{j=0}^{|T|-1} s[i+j]\oplus \tilde{t}[|T| - 1 - j] \\
&=\sum_{\substack{i\leq p \leq i+|T|-1 \\ 0\leq q \leq |T|-1\\p + q = i+|T|-1}} s[p] \oplus \tilde{t}[q]
\end{aligned}
となります．ここで，&\sum_{j=0}^{|T|-1} s[i+j]\oplus t[j] \\
&=\sum_{j=0}^{|T|-1} s[i+j]\oplus \tilde{t}[|T| - 1 - j] \\
&=\sum_{\substack{i\leq p \leq i+|T|-1 \\ 0\leq q \leq |T|-1\\p + q = i+|T|-1}} s[p] \oplus \tilde{t}[q]
\end{aligned}
\begin{aligned}
s[p] \oplus \tilde{t}[q]
&=
\begin{cases}
\, 0 & (s[p] = \tilde{t}[q]) \\
\, 1 & (s[p] \neq \tilde{t}[q])
\end{cases} \\
&=s[p](1- \tilde{t}[q]) + \tilde{t}[q](1- s[p])
\end{aligned}
なので，s[p] \oplus \tilde{t}[q]
&=
\begin{cases}
\, 0 & (s[p] = \tilde{t}[q]) \\
\, 1 & (s[p] \neq \tilde{t}[q])
\end{cases} \\
&=s[p](1- \tilde{t}[q]) + \tilde{t}[q](1- s[p])
\end{aligned}
\begin{aligned}
&\sum_{j=0}^{|T|-1} s[i+j]\oplus t[j] \\
&=\sum_{\substack{i\leq p \leq i+|T|-1 \\ 0\leq q \leq |T|-1\\p + q = i+|T|-1}} \Bigl[ s[p](1- \tilde{t}[q]) + \tilde{t}[q](1- s[p]) \Bigr]
\end{aligned}
となります．2つの項は，畳み込みの形になっています．畳み込みは，フーリエ変換の積をとり，逆フーリエ変換すれば求めることができます（畳み込みのフーリエ変換は，フーリエ変換の積）．詳しくは，次にまとめました．&\sum_{j=0}^{|T|-1} s[i+j]\oplus t[j] \\
&=\sum_{\substack{i\leq p \leq i+|T|-1 \\ 0\leq q \leq |T|-1\\p + q = i+|T|-1}} \Bigl[ s[p](1- \tilde{t}[q]) + \tilde{t}[q](1- s[p]) \Bigr]
\end{aligned}
FFTはnumpy.fft.rfftで計算できます．
ちなみに，サンプル数を$2^{n}$に選ばないとTLEになります（公式解説の以下をコメントアウト）．
siz = 1 << (siz - 1).bit_length()
