アルゴリズムの学習改善のための自身の備忘録及び学習の一環として記事を書くことにしました.
読んでくれた方で何かありましたら気兼ねなくコメントしてください.お待ちしております.
A - Good morning
問題文 概要
高橋君は$A$時$B$分，青木君は$C$時$D+1$分に起きました．早起きしたのはどちらでしょう．
制約と入力
制約
$0 \leq A \leq 23$
$0 \leq B \leq 59$
$0 \leq C \leq 23$
$0 \leq D \leq 59$
入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
$A \ \ B \ \ C \ \ D$
考察
$A>C$の時，Aoki
$A<C$の時，Takahasiとなる．
これは，hourで確定できる．
$A==C$かつ$B<D+1$の時，takahasi
$A==C$かつ$B \geq D+1$の時，Aokiとなる．
サンプルコード
A,B,C,D=map(int,input().split())
if A==C:
if B<D+1:
print("Takahashi")
else:
print("Aoki")
elif A<C:
print("Takahashi")
else:
print("Aoki")
B - Mex
問題文 概要
長さ$N$の整数列$A=(A_1,A_2,\dots ,A_N)$に含まれない最小の非負整数を求める問題です．
制約と入力
制約
$1 \leq N \leq 2000$
$0 \leq A_i \leq 2000$
入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
$N$
$A_1 \ \ \dots \ \ A_N $
考察
$0$から順に数列$A$に出てこない最小の整数を探索する．
最大探索回数は長さ＋1回で十分となる．
従って，計算量は$O(N^2)$程度となる．
$N$は$2000$程度なので十分間に合う．
数列$A$を集合$A$として扱うことで存在判定が$O(1)$で出来るので計算量は$O(N)$となり，より高速に判定出来る．
サンプルコード
N=int(input())
A=list(map(int,input().split()))
for i in range(N+1):
if i in A:
continue
print(i)
exit()
高速に判定
N=int(input())
A=set(list(map(int,input().split())))
for i in range(N+1):
if i in A:
continue
print(i)
exit()
C - Choose Elements
問題文 概要
長さ$N$の整数列$A=(A_1,\dots,A_N)$,$B=(B_1,\dots,B_N)$,$X=(X_1,\dots,X_N)$がある．
$1\leq i \leq N$で$X_i=A_iorB_i$かつ$\left\lvert X_i-X_{i-1} \right\rvert \leq K$を満たす整数列$X$の存在を判定する．
制約と入力
制約
$1 \leq N \leq 2\times 10^5$
$0 \leq K \leq 10^9$
$1\leq A_i,B_i \leq 10^9$
入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
$N \ K$
$A_1 \ \ \dots \ \ A_N $
$B_1 \ \ \dots \ \ B_N $
考察
$X_i$は$A_i$または$B_i$のいずれかで無ければ成らない．
現在の$X_i$として取り得る値をnow，$X_{i+1}$として取り得る値をnow_newとする集合として扱う．重複を考慮する必要が無いため集合として扱って問題ない．
$X_N$として取り得る値があれば整数列$X$は存在する．
何も取り得ない時は存在が認められない．
サンプルコード
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
now=set([A[0],B[0]])
for i in range(1,N):
now_new=set()
for j in now:
if abs(j-A[i])<=K:
now_new.add(A[i])
if abs(j-B[i])<=K:
now_new.add(B[i])
now=now_new
if len(now)==0:
print("No")
else:
print("Yes")
D - Polynomial division
問題文 概要
$N$次多項式$A(x)=A_Nx^N+A_{N-1}x^{N-1}+\dots + A_1x+A_0$
と
$M$次多項式$B(x)=B_Mx^M+B_{M-1}x^{M-1}+\dots +B_1x+B_0$
がある．
積を$C(x)=A(x)B(x)=C_{N+M}x^{N+M}+C_{N+M-1}x^{N+M-1}+\dots+C_1x+C_0$
と定義する．
$A(x)$と$C(x)$を与えられた時の$B(x)$を求める．
制約と入力
制約
$1 \leq N \leq 100$
$0 \leq M \leq 100$
$\left\lvert A_i\right\rvert\leq 100$
$\left\lvert C_i\right\rvert\leq 10^6$
$A_N \neq 0$
$C_{N+M} \neq 0$
条件を満たす$B_0,B_1,\dots,B_N$がただ一つ存在する．
入力
入力は以下の形式で標準入力から与えられる。
$N \ M$
$A_0 \ \ A_1 \ \dots \ A_{N-1}\ \ A_N $
$B_0 \ B_1 \ \ \dots \ \ B_{N-1} \ B_N $
考察
定数項は$\neq 0$であるが最大係数は$0$である可能性があるので定数項から求める．
$C_0=A_0\times B_0$
となるので，$B_0$は容易に求まる．
$C_1x=A_0\times B_1x +A_1x\times B_0$
となり，$B_0$が決まっているので$B_1$が決まる．
$C_2x^2=A_0\times B_2x^2+A_1x\times B_1x +A_2x^2\times B_0$
となり，$B_2$が決まる．
以降，演繹的に$B$が決まる．
$A$の範囲外参照をしないよう注意したい．
サンプルコード
N,M=map(int,input().split())
A=list(reversed(list(map(int,input().split()))))
C=list(reversed(list(map(int,input().split()))))
B=[]
for i in range(M+1):
B.append(C[i]//A[0])
for j in range(i+1):
if i+1-j>N:
continue
C[i+1]-=(A[i+1-j]*B[j])
B.reverse()
print(*B)