本記事は、AtCoder Beginner Contest 462 (ABC462) に参加した際の、A〜E問題の復習と解答の備忘録です。コンテスト中に考えた解法の方針や、提出したPythonのコードについて整理しています。

A - Secret Numbers /

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: None

配点 : 100 点

問題文

英小文字と数字のみからなる文字列 $S$ が与えられます。

$S$ から数字である文字だけを取り出し、元の順序のまま並べた文字列を求めてください。

制約

$S$ は英小文字と数字のみからなる長さ 1 以上 50 以下の文字列

自分の解答の方針

一文字づつ数字かどうかを判定し、数字のみを配列に入れて出力する。
提出の時には数字かどうかの判定は0-9のどれかに含まれているかを調べたが、解説ではPythonは isdigit() で数値かどうかを調べられるらしい。

提出したコード

S = list(input())
T = []
for i in range(len(S)):
    if S[i] in ["1","2","3","4","5","6","7","8","9","0"]:
        T.append(S[i])
print("".join(T))

B - Gift /

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: None

配点 : 200 点

問題文

人 1 から人 $N$ の $N$ 人がギフトを送り合いました。
人 $i$ は人 $A_{i,1}, A_{i,2}, \dots, A_{i,K_i}$ の $K_i$ 人にギフトを送りました。

$i=1,2,\dots,N$ に対し、人 $i$ にギフトを送った人を全て求めてください。

制約

$2 \le N \le 100$
$1 \le K_i \le N-1$
$1 \le A_{i,1} < A_{i,2} < \dots < A_{i,K_i} \le N$
$A_{i,j} \neq i$
入力される値は全て整数

自分の解答の方針

辞書に人 $i$ と、その人にギフトを送った人の番号をリストとして持つことを考える。
入力で受け取った、ギフトを送った人と送られた人すべてに対して辞書に登録し、結果を出力する。

提出したコード

N = int(input())
dct = dict()
for i in range(N):
    dct[i+1] = []

for i in range(N):
    A = list(map(int,input().split()))
    for j in range(1,A[0]+1):
        dct[A[j]].append(i+1)
for i in range(N):
    print(" ".join([str(len(dct[i+1]))]+list(map(str,dct[i+1]))))

C - Not Covered Points /

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: None

配点 : 300 点

問題文

2 次元平面上に点 1 から点 $N$ の $N$ 個の点があります。点 $i$ $(1 \le i \le N)$ の座標は $(X_i, Y_i)$ です。ここで、 $X, Y$ はそれぞれ $(1,2,\dots,N)$ の順列であることが保証されます。

左下の頂点を $(0,0)$ 、右上の頂点を $(X_i, Y_i)$ とする $x$ 軸に平行な辺と $y$ 軸に平行な辺のみからなる長方形の内部（辺上を含まない）に点 1 から点 $N$ までの $N$ 個の点をどれも含まないような $i$ の個数を求めてください。

制約

$1 \le N \le 3 \times 10^5$
$1 \le X_i, Y_i \le N$
$X, Y$ はそれぞれ $(1,2,\dots,N)$ の順列
入力される値は全て整数

自分の解答の方針

端から考えたいので、初めに $X$ についてソートする。
$X$ が小さい順に見ていったとき、現在の点が作る長方形の内部にほかの点が含まれるかどうかは、、これまでに走査した（$X$座標が自身より小さい）点の中に、自身より $Y$ 座標が小さい点が存在するかどうかで分かる。
なので、 $Y$ の最小値を保持しながら $X$ を増やしていくことで点を含むかどうかを判定しながら調べることができる。

提出したコード

N = int(input())
points = [list(map(int,input().split())) for _ in range(N)]
points.sort()
# print(points)
height = N+1
count = 0
for i in range(1,N+1):
    if points[i-1][1] < height:
        count += 1
        height = points[i-1][1]
print(count)

D - Accomplice /

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: None

配点 : 400 点

問題文

とある館で殺人事件が起きました。犯人の候補は $N$ 人おり、彼らを人 1、人 2、 $\dots$ 、人 $N$ と呼びます。
人 $i$ は時刻 $S_i$ に館に入り、時刻 $T_i$ に館を出て、ほかの時刻には出入りしませんでした。

犯行について以下のことが分かっています。

犯人はちょうど 2 人いる。
犯行はある整数時刻 $x$ に開始し、 $D$ 単位時間かけて行われ、時刻 $x+D$ に完了した。
犯人は 2 人とも犯行開始から犯行完了まで常に館にいた。（犯行開始と同時に館に入ったり、犯行完了と同時に館を出たりしたかもしれない。）

$N$ 人の犯人候補の中に犯人が 2 人ともいると仮定したとき、 2 人の犯人と犯行開始時刻の組としてありうるものは何通りあるでしょうか。ここで、 2 人の犯人には順番を付けません。

制約

$2 \le N \le 2 \times 10^5$
$1 \le S_i \le T_i \le 10^6$
$1 \le D \le 10^6$
入力される値は全て整数

自分の解答の方針

犯行開始時間が異なると組合せとして異なるので、各時間で犯人となりうる人が何人いたかが分かればよい。
max時間分の配列を用意し、それぞれの人をみて、館内に犯行可能な人数が増える時間に +1，減る時間に -1 を記録する。
犯行可能かどうかは退館時刻と入館時刻の差が $D$ より小さいかどうかで分かる。
また、犯行可能人数が減る時間は、犯行完了と同時に館を出ることも可能なことから 退館時刻 - D + 1 とする。
この配列の累積和をとることで、各時間で犯人となりうる人が何人いたかを計算できる。
各時間に対して、犯行可能な人が $N$ 人いたとすると、 $N < 2$ の時は条件としてあっていないので組合せとしては 0 組、 $N \ge 2$ の時は $N(N-1)//2$ 組となる。
各時間の組合せをすべて足すことで答えが求まる。

提出したコード

def conbi(n):
    if n == 0 or n == 1:
        return 0
    else:
        return n*(n-1)//2

N,D = map(int,input().split())
person = [list(map(int,input().split())) for _ in range(N)]
time = [0 for _ in range(10**6+1)]
for i in range(N):
    [start,goal] = person[i]
    if goal - start < D:
        continue
    time[start] += 1
    time[goal-D+1] -= 1
# 累積和
person_count = [0 for _ in range(10**6+1)]
for i in range(1,len(person_count)):
    person_count[i] = person_count[i-1] + time[i]

count = 0
for i in range(1,len(person_count)):
    count += conbi(person_count[i])
print(count)

E - Alternating Costs /

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: None

配点 : 450 点

問題文

整数 $A, B, X, Y$ が与えられます。
二次元平面上にコマが置かれています。はじめコマは座標 $(0,0)$ にあります。

あなたは以下の操作を 0 回以上何回でも行うことができます：

今コマがある座標を $(x,y)$ として、座標 $(x-1,y), (x+1,y), (x,y-1), (x,y+1)$ のいずれかにコマを移動させる。

$k$ 回目 $(k \ge 1)$ に行う操作にかかるコストは $k$ の偶奇によって異なり、それぞれ以下の通りです：

$k$ が奇数のとき：今コマがある座標を $(x,y)$ として、座標 $(x-1,y), (x+1,y)$ に移動させる場合のコストは $A$、座標 $(x,y-1), (x,y+1)$ に移動させる場合のコストは $B$ である。
$k$ が偶数のとき：今コマがある座標を $(x,y)$ として、座標 $(x-1,y), (x+1,y)$ に移動させる場合のコストは $B$、座標 $(x,y-1), (x,y+1)$ に移動させる場合のコストは $A$ である。

コマを座標 $(X,Y)$ に移動させるために必要なコストの総和の最小値を求めてください。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1 \le T \le 2 \times 10^5$
$1 \le A, B \le 10^9$
$-10^9 \le X, Y \le 10^9$
入力される値は全て整数

自分の解答の方針

対称性から、 $X, Y$ をどちらも正として考えることができる。
すべての操作で必ずマスを移動するので、すべてのマスは偶数回移動することで到達できるマスと、奇数回移動することで移動できるマスに分類することができる。
このように考えることで、 $k$ 回目の移動のコストは現在のマスによってのみ変わると考えることができる。
コストは 2 種類しかなく、コストに大小関係があるならば、できる限り小さいコストの通り道を考える必要がある。

各マスから移動できる方向とコストを見ると、 $X, Y$ がともに増加、減少する方向（座標 $(N,N)$）には必要となるコストが 1 種類でスムーズに移動できることが分かる。
座標 $(\min(X,Y), \min(X,Y))$ から目的の $X,Y$ までを直線で移動することを考える。
座標 $(N,N)$ からの移動は必ず奇数回目の移動になるので、縦に移動する場合はコスト $B$ の回数がコスト $A$ の回数 $+ (0 \text{ or } 1)$、横に移動する場合はコスト $A$ の回数がコスト $B$ の回数 $+ (0 \text{ or } 1)$ となる。

ここから、どちらかのコストがもう一方より明らかに高い場合、コストが高いほうを低いほうで置き換えるようにする。
移動する方向とコストを見ると、ひとつ隣のマスへの移動はもう一方のコストで回り道をして 3 マス分の移動で置き換えられることが分かる。
これ以上コストを小さくすることができないので、これが答えになる。

提出したコード

T = int(input())
for _ in range(T):
    A,B,X,Y = map(int,input().split())
    X,Y = abs(X),abs(Y)
    # (min(X,Y),min(X,Y))までのコスト
    cost = 2*min(X,Y)*min(A,B)
    dist = max(X,Y) - min(X,Y)
    # 最短移動でコストBの時
    if X&lt;Y:
        A_count = dist // 2
        B_count = A_count if dist % 2 == 0 else A_count+1
    else:
        B_count = dist // 2
        A_count = B_count if dist % 2 == 0 else B_count+1
    if A &gt; B and 3*B < A:
        B_count += 3*A_count
        A_count = 0
    elif A < B and 3*A < B:
        A_count += B_count*3
        B_count = 0
    cost += A_count * A + B_count * B
    print(cost)