はじめに
問題はこちら
初心者（灰色〜茶色）向けです。
A - Counting Passes
考え方
問題文通りに$A_i$が$L$以上のもののみに絞って、その長さを求めれば良いです。
私はfilterを使いました。
前々回が類題になっています。
解答例
n, l = map(int, input().split())
print(len(list(filter(lambda x: x>= l, map(int, input().split()))) ) )
B - Minimize Abs 1
考え方
数直線上の2点、$P$と$Q$の絶対値$|P-Q|$は距離を表します。
よって、どの点Yについても、$|X_i-A_i| \leq |Y-A_i|$ を満たすということは、
$X_i$は区間$[L,R]$の中に存在する整数の点の中で、数直線上の点$A_i$に最も近いことがわかります。
実は、$A_i$が$[L,R]$のどの位置にいるのかについて場合分けして考えると下記のように簡単に求まります。
- $A_i<L$
$A_i$は$[L,R]$のどの数より左側に存在するため、$A_i$に最も近い数は$L$です。 - $A_i>R$
$A_i$は$[L,R]$のどの数より右側に存在するため、$A_i$に最も近い数は$R$です。 - それ以外（$L \leq A_i \leq R$)
$A_i$は$[L,R]$の中に存在するため、$A_i$に最も近い数は$A_i$そのものです。
解答例
n,l,r = map(int, input().split())
a_n = list(map(int, input().split()))
ans = []
for a in a_n :
if a < l :
ans.append(l)
elif a > r :
ans.append(r)
else :
ans.append(a)
print(*ans)
C - Minimize Abs 2
考え方
実は、$x$を固定した時に最小になるようなyの値は$[\sqrt{D-x^2}],[\sqrt{D-x^2}]+1$のいずれかになります。
$0 < D \leq 2*10^{12} \iff 0< \sqrt{D} \leq \sqrt2 *10^6$ ですから、
各$x=0,1,2,\dots$について、上記の2つの値一つ一つ計算していき、最小値のものを出力すれば良いです。
これを考えるにあたり、非負整数$x$を固定したときに、$|x^2+y^2-D|$が最小になる整数$y$の値を考えてみます。
まず、$y$が整数でなくても良いとすれば、絶対値の最小値は0ですから、$|x^2+y^2-D|=0$を解くと、
\displaylines{
\begin{align}
& |x^2+y^2-D|=0 \\
\iff & y = \pm \sqrt{D-x^2} \\
\end{align} \\
y\geq0 \space ですから、\ y= \sqrt{D-x^2} \\
}
そのため、各$x=1,2,3,\dots,[\sqrt{D}]$について、最小値になるような$y$は$\sqrt{D-x^2}$付近の値になりそうです。
実際に $D=100$とした時の$y = \sqrt{D-x^2}$とその付近の整数値$[y]-1,[y],[y]+1$をプロットしたものが下の画像です。(xは整数でない点も含んでグラフにしています）
yが整数でなくても良いのであれば、$y=\sqrt{D-x^2}$の時最小値0になるわけですから、画像の青い線に一番近い点が最小値を与える$(x,y)$の候補です。それは、緑と黄色のどちらかの点です。
なお、前者は青の境界線の内側、後者は青の境界線の外側です。
解答例
import math
d = int(input())
x = 0
ans = 2*(10**12)
while x**2 <= 2*(10**12) :
y= int(math.sqrt(abs(d-x**2)))
ans = min(ans, abs(x**2+y**2-d), abs(x**2+(y+1)**2-d))
x+=1
print(ans)
D - Counting Ls
考え方
グラフ上の各「o」の点Xから見た時、Xを使って条件を満たす組を探すとすると、
- X以外でXと同じ列の点「o」
- X以外でXと同じ組の点「o」
を一つずつ選べば良いです。イメージとしては、Xを直角とする「o」の三角形を作成すると考えると良いと思います。
そのため、
Xを起点にする条件を満たす点の組の数 = (Xと同じ列のX以外の「o」の点の数) × (Xと同じ列のX以外の「o」の点の数)
です。
Xは直角三角形の直角の点ですから、重複して数えることはありません。
よって、「o」の点全てについて↑をそのまま数え上げればいいことになります。
解答例
n = int(input())
grid = [input() for _ in range(n)]
rows = {x:grid[x].count("o") for x in range(n)}
cols = {y:[grid[x][y] for x in range(n)].count("o") for y in range(n)}
ans = 0
for i in range(n) :
for j in range(n) :
if grid[i][j] == 'o' :
ans += (rows[i]-1)*(cols[j]-1)
print(ans)
参考文献
感想
E問題のMEX解きたかった、、、
C問題のグラフをpyplotで書きたかったのですが、気に入ったものを難しかったので諦めてスプシで書きました。
年内入緑目指して頑張ります。