AtCoder Beginner Contest 273 (A~D) 自分用メモ

A - A Recursive Function

再起関数を使う。
イメージがつきにくい場合は以下の図のように何か例を出して、実際に関数を追っていくと分かりやすいです。
例）$x=3$

以下のようになります。

B - Broken Rounding

※以下のコードは公式解説のものです。
これも実際に例を出して追っていくと分かりやすい。xの桁を1つずつ取り出す、四捨五入をする、4桁に戻す...みたいな流れになります。
例）$x=2052,k=2$(2回ループ)
①

②

C - (K+1)-th Largest Number

これはアルゴリズムというより問題文から意図を理解する方が難しいかもしれません。
以下はpythonでの解答例です。

import bisect

N = int(input()) 
A = list(map(int, input().split()))
A_sort = list(set(A))
A_sort.sort()
A_sort_len = len(A_sort)
l = [0 for i in range(N)]
for i in range(N):
  l[A_sort_len - bisect.bisect_right(A_sort, A[i])] += 1

for i in l:
  print(i)

以下の図を見れば「何を答えとすればいいか？」は分かると思います。
例）2 7 1 8 2 8の場合

※set()を使うことでAから重複をなくしたA_sortを作成できます。
※A_sort(1 2 7 8)の中からA[i]以上の数はいくつあるか？を求める際、二分探索を活用することで高速化できます。

D - LRUD Instructions

公式解説のコードをベースに説明します。
横方向、縦方向にそれぞれ何個壁があるかを$A$,$B$のmapに保持します。
公式解説だとそれぞれamp、bmpがそれにあたります。
以下の入力を例とします。

5 5 4 4
5
5 2
1 3
5 3
2 2
1 4
2
L 2
U 3

$A$,$B$のmapのイメージは以下のようになります。

言葉での説明が難しいので以下のイメージを見た方が理解が早いかもしれないです。
ざっくりやりたいこととしては進む方向に壁があったら、その方向に対して一番近い壁を二分探索で探し、maxやminを使ってぶつかるかどうかを確かめます。
①L 2（左に2マス進む）

②U 3（上に3マス進む）

注意

偉そうに解説書いてますが本番CもDも解けておりません泣