AtCoder Beginner Contest 462 参加記録と解答例 (A E問題)

本記事は、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$ 座標