0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

AtCoder Beginner Contest 245 A~D 4完記事

Last updated at Posted at 2022-03-27

アルゴリズムの学習改善のための自身の備忘録及び学習の一環として記事を書くことにしました.
読んでくれた方で何かありましたら気兼ねなくコメントしてください.お待ちしております.

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.py
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)$となり,より高速に判定出来る.

サンプルコード

b.py
N=int(input())
A=list(map(int,input().split()))
for i in range(N+1):
    if i in A:
        continue
    print(i)
    exit()

高速に判定

b.py
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$は存在する.
何も取り得ない時は存在が認められない.

サンプルコード

c.py
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$の範囲外参照をしないよう注意したい.

サンプルコード

d.py
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)
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?